ARC135

3完。ここ数日元気がないのが続いていて(体が悪いわけではないと思う)、残り30分くらいで撤退してた。CとDを少し考えてわからなかった時点で初めて順位表を見て、クソ回だと確信した(問題が悪いわけではないのでそう呼ぶのはおかしいが)。Cのエスパー早解きで順位が決まってしまう。

A - Floor, Ceil - Decomposition

分かれたら独立に(積の最大化を)考えていい。4より大きかったら分割したほうがいい(これも証明はしてない)。ということはシミュレーションするだけ?いや、それは時間がかかりすぎる。出現する数はかなり限られてそう。例のメモ化再帰が浮かぶ。そこまでしなくても解けそうだが、計算量の証明とか短時間ではできそうにないし、思考停止でメモ化再帰した。一応最大ケースで動作確認。

B - Sum of Three Terms

これは素直に考えていくとすぐ解ける。フィボナッチっぽいとも思ったけど、普通に観察すればよかった。実装はけっこう時間かかった。最初の3項が決まれば全部決まる。mod 3で3本のシーケンスができて、Aの差がそのままSの差になる。最初の3つを0として全部求め、最小値が0になるようそれぞれずらす。これより小さくてはいけないが、大きくするぶんには自由。これで、形はSと同じになった。どのシーケンスに足しても全体に影響するので、1本選んでSの初項が合うように足せばいい。0未満の項があればNo。

今気づいたけど2項増えてるからそのぶんだけ自由度が増えてるんだな。

C - XOR to All

手がかりが全くない。解法がクソエスパーである覚悟を早めにしておく。各ビット位置の立ってる個数を数えておく。一応、全ビットを都合よく反転させることができるとしてサンプルが通らないことを確認しておく。張る空間の次元がどう変化するかとかを考えるが、1回目の操作(必ず0が現れる)の特殊性がよくわからない。A_1を選び次にA_2を選んだときの様子を観察していると、最初からA_2だけを選んだときと同じ結果になっている。これで解けた。1回も操作しないケースにサンプルで気づく。

D以降も全部読んだ。Dはこのシンプルな見た目でこんなに解かれないのすごいと思う。