ABC195E メモ化再帰で解くのが自然． 結果的には，for を用いた dp で解ける． 後ろから決めていくのが自然． 二人ゲームの基本に則り逆算する． ターンが交互ではなく指定されいているが，勝敗の決め方は同じ． ターンが交互ではないため，勝敗はプレイヤー…

ABC203E DP. 大事な座標だけ見れば十分．差分を高速に計算する．黒のポーンが置かれている行だけが重要． 黒のポーンが無い行は，真下に進むしかないので， 動けるマスに変化は無い． 黒のポーンがある行 \(x\) に対して，黒のポーンの \(y\) 座標を記録して…

ABC208E 桁DP. 先頭の桁の 0を無視しないといけないので， leading zero を保持する． 無視するというのは，積に使わないということ． 実装Leading zero さえ持っておけば，あとは桁DP のテンプレ通り． 注意 まだ \(N\) 未満が確定していないかつ ne > cu …

ABC210E MST. 解法から攻めるのは邪道な気もするが， 問題の性質から攻めて綺麗な方法が作れなかったので， MST のアルゴリズムであるクラスカル法から攻める． クラスカル法により，コストの小さい辺から追加していく． 計算量を無視すればこれで解ける． …

ABC310B 問題文通りに実装． 別解: ソート済みの iterator 範囲 [l, r) に対して std::includes を使うと楽． set やソート済み vector 等に使える． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll …

ABC310C 最初は，回文かそうでないかで分けて考えていた． 回文を入れる string 型の set を a, そうでない文を入れる set を b とする．ただし，b に入れるときは， \(s_{i}\) と \(reverse(s_{i})\) の両方を入れる． \(i \in N\) の \(s_{i}\) を \(a,b\)…

ABC310D \(N,M,T\) がいずれも小さいので，全探索して数えても間に合いそう． DFS によりすべて列挙する． このとき，取りこぼしと重複が無いようにする． 今回は起こらなかったが，仮に重複するのなら，その分を割ることにする． 実装先に \(T\) 個の入れ物…

ABC310E 区間の数え上げ． 最初に考えたのは，\(x nand y = 0\) になる \(x,y \in 2\) の方が少ないから， 取り方全体から\(0\)になる取り方を除く方針だった． 区間 \([l,r]\) の nand が\(0\) になるケースは， \(r\)が \(1\) かつ \([l,r-1]\) までの nan…