計算量がなぜ間に合うのか自信がない。 fig.1fig.2ある頂点P（色c）に注目したとき、パスをつくれる頂点は図のようになる。 DFSで戻るときにパスの数を計算しながら、部分木の色のヒストグラムをマージしていく。 （色c以外は合計して、色cは1にする。） 深…

公式解説は、インデックス1まで移動してきた敵を一気に倒す。 使わずに余った弾丸は次のターンに持ち越すことにしても結果は変わらない。 というもの。 気づかずに少しめんどくさい解法をつかったのでメモしておく。 敵を攻撃し始めないと間に合わない締め切…

めちゃくちゃ苦労したけど、コンテスト外でやっと解けたので記録してくおく。 最初に考えたこと。 差分計算したい。 更新時に未使用の色のうち、インデックスが一番小さいものを採用すればよさそう。 ある色が採用されたとき、いくつのボールが利用されるか…

解説をよんで最初分からなかった部分が腹落ちしたので書いておく。 疑問に感じたのは、途中で使ったボールの操作を打ち消すのに、最新の状態のDPテーブルへの操作で良い理由。 合計K以上のDPテーブルを持たなくて良い理由の部分。 の2点。 直感的にはボール…

公式解説の通りです。 実装の方針だけ。 任意の頂点pを選んで2回操作した場合もとに戻る 操作の順番が違っても結果は同じ 任意の頂点pだけを反転するには、頂点pにたいして操作をして、頂点pの子に操作する（戻す操作）で可能 以上により必要な操作の最小回…

AtCoder ARC127 A. Leading 1s 地獄のような桁dpを書いた。 dp[i桁目][先頭から連続して使用した1の個数][1が連続しているか][未満フラグ] として、遷移はnext = 0から9 leading zeros に注意（nextが1の時だけ初期状態に+1）。 dpの結果（場合の数）にたい…