久々にストレッチをした。体が硬くなっている。

---

結局ABC288(トヨタコンの予選A)を走っていなかったので、さすがに良くないかなと思って本選前にやった。割と散々な結果だった。

A: やるだけ

B: やるだけ

C: 閉路のない最も辺数の多いグラフは木(森)なので、各連結成分について木にすればよい。連結成分をUnionFindで管理しつつ、各連結成分について辺の数を数えて(サイズ-1)との差をとる。

D: こんなの700人も解くの？解説ACした。

A[i]～A[i+k-1]にcを足すという操作は、階差数列A’をとるとA'[i]にcを足しA'[i+k]からcを引くという操作に置き換えられる。Aのことは忘れてA’での議論に置き換えるとよい。A[L]からA[R-1]まで全て0というのは、A[L]からA[R-1]まで全て0ということになる。操作を適用する範囲を適切に考えれば、A[L-1]やA[R]のことは考えなくてよい。

端から順に0にしていくことを考えると、

auto c = -A[i];
A[i]+=c;
A[i+k]-=c;

このような操作を$L\leq i < R – K + 1$についてやっていくことになる。最後に残った反対側の端($[R-K+1, R)$)だけ見ればいいことを考えるとA[i]への操作は要らない。これを考えて式変形をするとこうなる。

A[i+k]+=A[i];

これは累積和の形だ。mod Kで等しい要素を取り出して累積和をとる。

$[R-K+1, R)$が0になっているか確認するのに相当する処理をしなければならないのだがそれの添え字を求めるのがやや面倒。

S[i]=A[r]+A[K+r]+A[2*K+r]+…+A[i]が求まっているとして、Lより左の要素の影響を取り除く必要がある。mod Kでiと等しくL未満で最大の整数をjとすればS[i]-S[j]として求められる。また、mod KでLと等しい場合は初期値がA[L]になるという問題がある。これも処置する必要がある。これに気づくのにかなり時間がかかった。

階差数列を作ってmod Kで要素を分ける基本の発想は出ていたのだが、なんか階差数列ではないよくわからない何かを作った挙句数式での解析で混乱してしまった。いもす法が頭に浮かんでしまったのだがあれは実装テク寄りの技術であり、実装と解析をごっちゃにしてはいけない。解析の前に実装テクが出てくるべきではない。まず解析に集中し、そして一番使いやすい数学的道具を変なアレンジせず使うべきだった。

あと、不変量を用いた解析は頭に上ってはいたのだがうまい方針が思い浮かばず使えなかった。Twitterのnok0氏の書き込みによれば、繋がっている部分に関する不変量解析が多いので「つながっていない」ことをテーマにしていたらしい。まさにしてやられたという気分。

---

筋トレをした。今日は腕立て。