ABCって感じだった。Aの難しさは特殊として、Eの実装とFの発想をいかに短時間で回すかというゲーム。ただDはガチで難しかった。
2回目の黄色になった。体感冷えてたのであまり嬉しくないけど、それは今回ごく自然にここまで来れたということで、いいことだと思う。
A - Very Very Primitive Game
「このE問題、簡単だけど実装面倒だなあ」みたいな問題。Aにしてはめちゃくちゃ重い。確かに簡単ではある。Cが0固定なら、「同数なら高橋君の負けね」となるし、Cが1でも同様。ただその場合分けや上手い統一方法を1分とかでやれというのが酷い。a + c > b と書いてACだったが、2分20秒かかってる。
B - Magic 3
これも見た目がD問題くらいで面白そうなんだよね。でもよく読むとB問題。サンプル親切そうではあるけど、こういうチェックサムのなさそうなコードを書くのは不安になる。
C - Bowls and Dishes
なんか難しそうだけど全探索でできる。全探索しなくてもできるのかなあと思ったけど、まあ自分の実力だと全探索するしかない。いつも変数名にkを使うところ、問題文でKが使われているのが困る。これどうしようもないよね。どっちの変数名を変えてもパフォーマンスは落ちる。1文字変数名のイメージでブーストかけてる代償として仕方ない。
D - Staircase Sequences
これはD問題らしくクソムズ。まずそういう数列があったとして、それを大きいほうへ1ずらすと、小さいほうのお尻はいくつか短くなる。このように、しゃくとりと二分探索でできそうだと思う。なんとなくサンプルをながめると、負の数が入っている。これは気づかなかった（自分で気づきたかった）。今回、かなりサンプルが親切だ。しばらく考える。数列が0を含む場合、0を中心に対称に取れるだけ取り外して残ったものは総和が同じだ。正の数だけからなる数列と、0を含む数列が対応していそうだ。つまり正の数だけと考えて2倍すればいい。
答えがどのくらい大きくなり得るかもわからない。1個ずつ数えてTLEしないか。等差数列の総和は、端の2つの平均掛ける長さだから、長さKとして式変形して、初項が正としているので K*(K+1)/2 以上にはなる。nを2倍しておいて K*(K+1) と比較すれば100万くらいには収まりそうだとわかる。よかった。数列の長さを全探索できる。式をよく見るとKを決めたら初項も決まってしまう。割り切れるかチェックしていけば、整数演算だけで条件を満たす数列の存在判定と初項がわかってしまう。なんか解けていた。難しかった。
E - Magical Ornament
順位表を見るとFのほうがだいぶ多く解かれている。基本は全完前提でEF交互に考える方針だが、Eが通せずF早解きが必要になるケースも考慮する。結果的に、Fがすぐには解けず、Eが方針はすぐ見えるけど実装に時間かかりそうで、Fを少しやって（ここでFをはさむのは、解けてる（得るものがなさそうな）Eで混乱して終了する損失が大きいため）無理ならEを片付けるという方向に。そして、Eを片付けてFをやって解けて全完した。
グラフっぽいと気づき、巡回セールスマンだと気づく。BFSをK回やれば全部の距離が求まる。ABC180Eが巡回セールスマン問題だという話題を数日前だかに見かけていた（そのとき自分の提出も少し見直した）ので、それを貼る。こっちの問題に合うよう修正。変数名が違うので n = k; とか酷い書き方をしたが、そういうのが原因でREを1回出してしまった。今思うと、TSPを関数にすればよかったか。BFSとTSPで問題を2問解かされる感じできついよね。nとkで混乱しているうえ距離が∞の場合もあるからなかなかサンプルが合わなかった。よく考えれば∞があった時点で不可能だ。ソースコードの流用でかなり時間を節約できたけど、まあそれでも重かったね。
F - Shift and Inversions
たくさん解かれているから簡単なのかと思いぐっと睨むがわからない。とりあえず例によってchokudai speedrunでググって転倒数を貼る。数列の前に同じ数列を付け足して、BITで数える動作をより左までやったりする方針をまず考える。しかし計算量がNの2乗になってはダメなので、この方針ではどうしようもないように見えるし、他の方針もなさそうに思える（同じものを2回繰り返すのがいかにもありそうな典型で、結果的にはそこではまってしまった）。少し経って、まず普通に転倒数を求めて出力するだけのプログラムを動かしてみた（当然サンプルの1行目とは合う）。そして、そこから1ずつずらしていくのを思いついた（この辺はよく覚えてない）。「この問題が解けるプログラムは、普通に転倒数を求める能力も持っている」というのは最初から頭にあった。転倒数の別の簡単な求め方なんてあるのかなあと悩んでいたが、まさか普通に求めてるだけだったとは。ずらすのは簡単で、例えば先頭が3なら転倒数への寄与は3だ（削除すると転倒数が3減る）。
