Codeforces Educational Codeforces Round 162 (Rated for Div. 2) E. Count Paths

計算量がなぜ間に合うのか自信がない。

fig.1

fig.2

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

深さが最悪ケースではマージテクをつかうことで計算量を抑えることができる。
逆にマージする色のヒストグラムが大きいときは、二分木が最悪ケースで、深さがlogNに抑えられる。
以上から実行時間が間に合う、のだと思う。

実装時はサイズが大きいヒストグラムをコピーしないよこうに注意する。
作れるパスの数の計算の仕方は図にかいた通り。

codeforces Educational Codeforces Round 162 (Rated for Div. 2) B. Monsters Attack!

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

敵を攻撃し始めないと間に合わない締め切りを求める。
締切は 。
これをpriority queueにいれて。締切が早い順に処理していく。
各ターンで、残弾がある限り、もっとも締切が近いものを、1ターン締切を伸ばすように処理してpriority queueに入れなおす。
締め切りを伸ばすのに必要なダメージは (ただし0のときはK) で求める。
締め切りが現ターンより小さければNOを出力。
（締め切りが近いものからKダメージをフルに使うとWAなので注意）

トヨタ自動車プログラミングコンテスト2024#1（AtCoder ABC337） F問題 Usual Color Ball Problems

めちゃくちゃ苦労したけど、コンテスト外でやっと解けたので記録してくおく。

最初に考えたこと。
差分計算したい。
更新時に未使用の色のうち、インデックスが一番小さいものを採用すればよさそう。
ある色が採用されたとき、いくつのボールが利用されるかは事前計算しておく。
色をインデックスとしたセグ木に、各色の一番小さいインデックスをいれて更新していく。使用中の色にはInfを入れておく。
この方針はだいたいのケースでうまくいくんだけど、考慮漏れがあって、一つの色が複数の箱に入る場合にWAになる。
そこでさらに発展させて、箱が無限にあったとき、各色が何個の箱に入ることができるかと、n箱目では何個のボールが入っているかを事前に計算しておくことで、いい感じにセグ木の更新と求める合計を計算することができる。
と書くのは簡単だけど、実装は結構大変だった。コンテスト時間ないに解くのは今のところ絶望的。

擬似的な説明を書く。
各色のボールがn箱目で利用されたときの利用されるボールの数（最大K)：ball[color][n]
各色のボールのindexを管理する配列（予めCを2周分にしておく）。各色の左からt番目。存在しないときはInfを返す。 : index[color][t]
各色について未使用のボールのうち最も左のindexを管理するセグ木。存在しないときはinfをいれる。: segtree[color]
各色について何箱利用しているか : count[color]
初期状態の答え: sum

ballはpop()で先頭を消せるようにリバースしておく。

for _ in 0..M{ //M箱分処理する
    //いい感じに初期状態とsumを作る
}

let mut ans=vec![sum];
for i in 0..N-1{
    let preColor = C[i];
    count[preColor]-=1;    
    index[preColor].pop();
    sum-=ball[preColor][count[preColor]];
    
    segtree.update(preColor, index[preColor].last());
    
    let j = segtree.all_prod();
    let nextColor = C[j];
    sum+=ball[nextColor][count[nextColor]];
    count[nextColor]+=1;

    let L= index[nextColor].len();
    let n = index[nextColor][L - count[nextColor]*K -1];
    //未使用の次のインデックスは現在（末尾）から使用している箱*K番目    
    segtree.update(nextColor, n);

    ans.push(sum);    

}

以上を実装してAC。

AtCoder ABC321 F問題 #(subset sum = K) with Add and Erase

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

ボールの集合の和sの場合の数のDPの遷移は、ボールに書かれた数をaとして、
dp[s]+=dp[s-a]
このとき最後に使ったボールを削除するのは、この操作を打ち消せば良くて、
dp[s]-=dp[s-a]
このDPを考えるとき、ボールの集合の計算する順番が違っても結果は変わらないので、任意のボールの操作を打ち消すとき、打ち消すボールを最後に計算したことにして、考えても問題ない。
よって1番目の疑問は解消した。
同時に遷移の式をみればK以上のDPテーブルを保持する必要がないこともわかる。

AtCoder ARC148 C. Lights Out on Tree

公式解説の通りです。
実装の方針だけ。

• 任意の頂点pを選んで2回操作した場合もとに戻る
• 操作の順番が違っても結果は同じ
• 任意の頂点pだけを反転するには、頂点pにたいして操作をして、頂点pの子に操作する（戻す操作）で可能
• 以上により必要な操作の最小回数になる（厳密さを無視すると完成形からもう一回操作（打ち消す操作なので全体で-1）しても表が増えるので良くなることがない）（公式解説読んで）

よって、頂点とその子に対して操作をした回数を記録して、その和のmod 2をとった結果（2回操作すると元に戻る）の木全体の和が答え。

• 任意の頂点pの子に+1する操作を高速化したい

深さが2のような極端な木が与えられるとTLEするので、子の頂点に+1する操作を高速化する必要がある。
ある範囲に+1したいので、遅延伝播セグメント木が候補。

• ある頂点の子全体を配列の範囲で表したい

オイラーツアーのようなイメージだけど、オイラーツアーは部分木にたいする操作なので、BFSで辿った順番から頂点pの子の集合の範囲を決める。

• 遅延伝播セグメント木をどうするか

mod2 で任意の範囲に+1して、全体で和を取らないといけない。
範囲のサイズを一緒に持って、範囲に+1するときは、「次の状態の1数 = サイズ - その時の1の数」と更新することで、「1,0」の反転を表現できる。
（検索ワード: 範囲に+1 mod2 区間和）

• mod2で+1は範囲にxor 1と一緒

以上を実装してAC。

AtCoder ARC127 A. Leading 1s

AtCoder ARC127 A. Leading 1s

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