ジャンクで買ったSFCのカセットがどうも動かなかったのだが、ネット情報に従って接触部をシャーペンで塗ったら見事に動作した。内部の基板や半導体はそうそういかれるもんじゃなし、やっぱり接点なんだな。

---

ABC290に出た。

A: やるだけ

B: やるだけ

C: 要はAの部分集合のMEXになる。任意に部分集合を取ってよいならAそのものとすればよいが、部分集合の大きさは最大Kということなのでこれを考慮する。サイズKの集合のMEXの最大はKなので、min(mex(A), K)とすればよい。

D: Dp mod n=0なる最小のpだけ移動した時点でマス0に戻ってくることになり、1つずれる必要が出る。この回数はちょっと計算すれば分かるがN/gcd(D,N)となる。なお、マス0より先に別のマスでずれる必要が出ることはあり得ない。そのようなマスをm、mに1,2回目に到達する移動回数をそれぞれq1,q2とすると、マス0からq2-q1回移動した時点でマス0に再び訪れるはずで、これはマス0からq2回移動するより先のはずだからだ。

また、2回目にマス0を踏んだ時に2回ずれることはあり得ない。なぜならばその場合ずれることなくマス1を踏んでいるということになり、これはgcd(D,N)=1である場合以外ありえない。その場合1度もずれることなく全マスを踏破する。3週目以降も同じ議論が適用でき、ずれるときは必ず1回ずつになる。

ということで、何回ずれるかをceil(K/(N/gcd(D,N)))で計算でき、残りK % (N/gcd(D,N))を普通に移動すれば良いことが分かる。

E: 上手い方針が立たなかった。実験した結果、任意の$1\leq i < j \leq N$について$A_i\neq A_j$であるとき$min(i,j,N-i-1,N-j-1)$を足せばよさそうなので$O(N^2)$は出来たが、上手い高速化が出来なかった。

F: 何も分からない。

G: 終盤EFが解けず絶望していたのでワンチャンで手を出したら解けた。超気持ちいい！！！！

0~1回切断すればD以下の任意の深さpのK分木($=\sum_{i=0}^p K^i$の大きさの連結成分)が作れるので、後はそれをどう剪定するかになる。これは削る大きさ$\sum_{i=0}^p K^i-X$を出来るだけ少ない数のK分木の大きさの和で表すという話になる。これはいわゆる「ある金額を払うために使うコインの数を最小化する問題」と同じになる。
この問題で貪欲法が使える条件がなんかあったはずだが思い出せず、残り時間も少ないしサンプルは合ったので未証明で貪欲法したら通った。

---

筋トレをした。今日はスクワット。また日が空いている。