2完。
各問題
A - mod M
まず、全てが奇数の場合(または全てが偶数)の場合は、2で割れば余りが1(または0)になるので答えは1です。そして偶数と奇数の両方を含む列の場合、2で割ると余りは0と1の2種類なので、答えは最大でも2です。
Mで割ってR余る数を列挙すると R, R + M, R + 2M, ...
なので、任意の2要素の差はMの倍数になります。
なので、Aの隣り合う要素の差がすべてMの倍数になれば、Aの全ての要素はMで割った時の余りが同じということがいえます。これはAの隣り合う要素の差のGCDを取れば確認することができます。つまり、GCDが2以上なら条件を満たすMが存在して答えは1、そうでない場合は答えは2となります。
B - dp
前から見て、d
が続いている限りはそれらを動かしても得をしないのでそのまま採用します。初めてp
が出てきたところでLをそこに固定して全探索すると通ります。
え?!
(公式解説を見ると、なぜそれが最適であるかを証明するのが問題の肝のようですね...。)
C - Lights Out on Tree
セグ木に乗せるかオイラーツアーかと思って考察しましたが、そこまで。
まとめ
Bを速く(早く)通しても得しない AtCoder、つらい。(n回目)