Q.古戦場とABCと艦これイベントが被るとどうなる？
A.団長･･･団員のみんな･･･すまねえ･･･
ノルマ無し走る走らないも自由の団なので特に問題ないですが。そろそろ4問解けないかなーと私は思うのでした。
結果
A,B,CはAC。Dは提出したけどAC、WA、TLE入り混じったひどい結果、後日AC。E,Fは解説見てAC。
C：Prison
とりあえず図を書けばわかりました。を見ればいいよね。
D：Integer Cards
これも図を書くと。降順にソートして比較して大きいの計N個とりゃいいねと。
考え方は良かったけどいろいろ実装ミスしたもよう。比較も無駄に多くしてたし。結局どこミスったのかわからなかったのでちょこっとやり方を変えてAC*1。テストケース公開されたら確認する。
解説の方法の方が良さそ。Aを昇順、Cを降順に並び替えて比較、高い方を選択していく。
E：Cell Distance
解説にある通りですね。
- 行と列を分けて考える
- 2点固定すると、その数は残りNxM-2マスからK-2マス選択の
通り。
- 2点の距離がdの組は
通り(列の場合)
数式にすると
これを行に対しても同じように。
うーん時間があっても思いつける気がしない。
余談
long = int*int
みたいなコード書いてint*int部がオーバーフローして死んだ。そういや計算途中は勝手に型変換してくれませんでしたね。あとmod取るタイミングやらもミスってたし案外面倒。
F：Absolute Minima
これも解説にある通り。図を書くと、傾き0になる区間、点がの最小値を与える
ことが直感的にわかるかと。
2点(偶数点)ある場合、傾き0の区間ができる。
3点(奇数点)ある場合、傾き0の点ができる。
ソートして両側をペア()として考えれば感覚をつかみやすいかも。
次の方のブログがとても分かりやすかったです。
余談
が与えられるたびにソートすると楽なので、とりあえずListにしてSortしました*2。TLE。
On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n2) operation.
まあ･･･そうなるな。
じゃあ二分探索してinsertすっか。二分探索はだから余裕やろ！
･･･約1.8秒。ぎりぎり間に合ったけど遅！
This method is an O(n) operation, where n is Count.
そういやListでinsertは単にずらしてるだけだからめっちゃ時間かかるんだっけ･･･。それにしてもでよう間に合ったな･･･。
他の人のコード読んでると、平衡二分探索木というのがよさそうですね。探索も挿入もだとか。
所感
私のなんとなくでなんとかなりそうなのはDまでっぽいかー。
