AtCoder Beginner Contest 256 参加記

oooooo--

A問題。1<<Nでok。

B問題。後ろから見た累積和が4以上の個数。

C問題。左上 $2\times 2$ マスを全探索。

D問題。imos法の要領で $0$ とそれ以外が切り替わる位置を管理。

E問題。連結成分ごとにループはちょうど $1$ つ存在するので、それを atcoder::dsu で検出して、ループに沿って最小値を求める。はじめ全体が連結だと思っていてループに沿う手順を $\Theta ($ ループの長さ $)$ ではなく $\Theta (N)$ で雑に処理していたため TLE した。修正して AC したが 2WA はつらい。

F問題。$C$ を持って区間等差数列加算区間和取得の遅延セグ木を書いた。頭をバグらせたのでかなり時間をつかった上、嘘考察もして 2WA 。寄与を考えると $i,i^2$ が出てきて嫌な気持ちになってしまったが、よく考えれば $iA_i,i^2 A_i$ を別物と見てそれぞれの区間和セグ木を書けば十分だと分かる。

G問題。漸化式を立てることを一瞬思いついたが、実験コードからのエスパーに迷走。$N=3$ のとき oeis に怪しげな式 $\displaystyle\sum_{k=0}^{D} {{}_D\mathrm{C}_k }^3$ があるので $3$ を $N$ に読み替えて実装すると $N\neq 3$ で破滅。ここでまだ諦めずに実験して何かいい性質を...とか思ったのが敗因。コンテスト終了後、丁寧に漸化式を立てると行列累乗になるので実装して AC 。悔しみの舞。

Ex問題。見ていません。見ます。