AGC056

0完緑パフォ。Bは読んだだけ。3時間楽しめたと言えばそうだが、体温を上げて集中するようなことがなかったのは残念。青に落ちたけど、レーティングはどうでもよくて自分の頭が不可逆に劣化したんじゃないかという、ぼんやりとした不安というか懸念点がある。まあ単なる相性だとは思うけどな。「レーティングはどうでもよくて」となってるのがなんかおかしいんだよなあ(普通ならめちゃくちゃに感情が動くはず)。

A - Three Cells per Row and Column

N=6はサンプルにある。Nが6の倍数ならそれを斜めにつなげるだけなので簡単。N=9は簡単に構成できる。周囲にL字を付けることで4だけ大きいものも構成できる。7と8ができれば解けたことになるが、手でやってみてもなかなかできない。7が難しいのがびっくり(出題意図が全く見えない)。4は無理そうだし、5もたぶん無理だろうなあと思ったので小さいほうはあきらめる(5はできるらしい)。

ここからは、Cをメインで考えて、ちょいちょいAのアイデアが降ってこないか見に行く感じだった。そもそも、7と8を手で作ることへ一定以上の時間をつぎ込むのはAGC中にすることではない。

残り1時間を切ってきたころだと思うが、8が手で解けて、7も解けた。これで問題が解けたことになるので実装に入る。ペイントでやっていて、それを見ながら手で打ち込むのはばからしいが他の方法も思いつかない。大体打ち込んだところで、そこからの実装もかなり時間がかかりそうであることに気づく(時間がかかりそうなこと自体には、自分の相対的な力不足を強く感じた(人と比べなければ特に力不足とは思っていない))。そもそもこれが想定解であるはずがないし、Cを考えたほうが時間の使い方としてよいと判断し、Cに集中した。

C - 01 Balanced

0101...のようにすれば条件は満たす。連結成分毎に考えていい。連結成分内で01の個数が偏ることはありえる(こういう細かい性質を、勇気を出して1個1個結論まで見に行くの大事だと思う)。M個の区間毎に0の個数の累積和の範囲が定まっている。平行四辺形がたくさんあって、左下から右上へ累積和の線が通るように位置を上下に調整し、位置が決まれば一番上を通れば答え。でもこれの解き方が全く見えない。括弧列も考えたけどよくわからず。最後のころには、何か典型知識が足りないような気がしていた。典型はABCで学びやすい環境になっているけど、やっぱ自分のレベルを超える典型は身に付けようがないんだよね。典型もアドホックもどっちも地頭なんだよ。なんか最短経路とかも考えたけど何も見えず。残り5分になって撤退したけど、そこからの5分は長かった(3時間はあっという間だったのに)。