ABC262E 赤い頂点 \(v\) の内，\(deg_{v} \equiv 1 \ mod \ 2\) のもの全体を \(X\) とおく．場合分けして数える． \(X\) がら丁度 \(i\) 個 (\(i \in [0,N]\)かつ\(i \equiv 0 \ mod\ 2\)) 選ぶ場合の数の合計が答え． 使っている記号，マクロ等 "https://e…

ABC263E 期待値DP． \(i \in N\) に対する答えを \(dp_{i}\) とおく． 遷移は\(dp_{i} = \frac{1}{a[i]+1} \sum_{x \in a[i]+1} dp_{i + x} + 1\).よって，\(dp_{i} = \frac{1}{a[i]} \sum_{x \in [1, a[i]+1) } dp_{i + x} + \frac{a[i]+1}{a[i]}\).初期値…

ABC266E 期待値DP. 素直に考えると再帰になる． 再帰で考えた後に，高速化として for などが可能か考えればよい． 最初から綺麗に書こうとしない方が楽． 残り \(x\) ターンのときの答えを \(f(x)\) とおく．\(f(x) = \sum_{d \in [1,6]} \frac{1}{6} max(d,…

ABC265E 移動したときに出てくる座標が少ない事がポイント． ただし，map を使って座標を記録すると重いので， 移動回数を状態に持ちながら dp. 解法0: DP\(dp_{i,s,t} := \) \(i\) 回移動して，そのうち タイプ \(0\)の移動を \(s\) 回， タイプ \(1\)の移…

ABC264E Union-find, クエリ先読み，クエリの逆算． 切断するのは難しいが，結合するのは Union-find を用いれば簡単． クエリを先読みして，逆算すれば結合に書き換えられる． 実装\(M\) 個の発電所は，役割がすべて同じなので区別する必要がない． よって…

ABC267E 最大値の最小化は, binary search が典型． しかし，解法から攻めるのは王道とは言えない． まずは性質を考える． 単調性 \(\cdots (*)\)取り除く作業を繰り返してく． ある時点でコスト \(y\) 以下の vertex は，それ以降もずっと コストが \(y\) …

インタラクティブな問題． 解法Binary search と同じで，区間を半分ずつにしていく． 行を 2つの区間に分けたとき，区間の行の個数より駒が少ない区間が存在する． そちらの区間に正解の行がある． 列も同様． 実装入力と出力を一緒に行う関数を用意すると楽…

ABC270E 解法は2つある． いずれにせよ，まずは 1周を一塊で考える． 解法0: Binary search\(K\) を固定する．(\(m\) 周できるか) \(\in Bool\) は単調．\(m\) 周すると，各 \(i \in N\) に対して \(min(a_{i},m)\) 個食べるので， その合計が \(K\) 以下か…

ABC271E 通る道の長さの最小を求める．最小の長さの合計ではない． 良いpath良いpath とはどういうものかを考えると， \(E\) を先頭から見ていくことで判定できる． そこで \(E\) を基準に考える．また，良いpath 自体は多くなりうるので，Dijikstra などで …

ABC273E 永続データ構造．Vector \(a\) 自身でなく，\(a\) の編集履歴を保存しておき， 履歴におけるタイミングに跳ぶことで復元する．今回は tree \(T\) を永続データ構造としてもつ． 出力クエリ必要な情報は，\(a\) の末端．これは \(T\) における頂点 \(…

ABC280E 普通にDPをしても \(O(N)\) で間に合う． 今回は遷移が線形なので，行列冪乗で遷移を計算すれば \(O(log N)\)． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" template<typename T> using M = vector<vector<T>>; template<typename T> M<T> oper</t></typename></vector<t></typename>…

ABC279E \(0\)-indexed で考える． \(j \in M\) 番目を除いたものは， \([0,j) \) と \([j+1, M)\) に分解すると便利． 累積和などでも使われるが，今回も同様にできる．あみだくじの上の方は，\(0\) の場所だけで十分． 下の方は，\([0, N)\) のすべての位…

e ABC275E ちょうど \(i \in K+1\) 回で \(j \in N+1\) に居る確率を DP で求める． どの様な手順でその局面に至ったかは，今後に影響しないので， 状態をまとめることが出来てDP可能．遷移に \(O(M)\)． 使っている記号，マクロ等 "https://ecsmtlir.hatena…

ABC274_E 状態ブースターは，取る順序は無関係． よって，どれを取ったかの情報だけで済むので，\(2^{M}\)．頂点も，訪れた順序は無関係で， どれを訪れたかの情報だけで十分なので，\(2^{N}\)． 原点を含めて，\(2^{N+M+1}\) ． 遷移今の頂点と次の頂点を用…

ABC308 問題の本質から攻めるのが王道． 商品の個数は重要ではなく，大事なのはクーポン． まずはクーポンを全探索する方針で考える． つまり，クーポンを 1枚固定して考える．払う値段は， \begin{align} & \sum_{i \in N} (p_{i} - c_{i}d_{i} )\\ = & \su…

ABC308E 動く物が 3つある場合， 真ん中を全探索する のは典型．\(E\) の場所を全探索して，\(M\) と \(X\) の場所を考える． \(M,X\) それぞれの値に対して，それが何個取り方があるのかを数える． 用意したいもの：\(i \in N\) が与えられたとき， \([0,i)…

文字列 snuke の中に，同じ文字は使われていない． よって，同じマスを通る必要はない． DFS で実装可能． 一般化:もし，文字列 snuke の代わりに，同じ文字が現れる文字列 \(S\) の場合． 訪れたかどうかを，\(x \in H, y \in W, i \in Length(S)\) に対し…

ABC290E Warshall-Floyd. \(O(N^{3})\) が間に合う．(最短距離，お土産の最大化) の優先順位で同時に処理する． つまり，辞書順を用いればよく，pair を使えばよい． 最大化の方は，マイナスをつければ最小化に帰着できる．実装パスの頂点すべてでお土産を買…

ABC287E LCPに関する問題．先頭から貪欲に考えるのが基本．Binary Trie に近い．とりあえず，\(n\) 個は多いので 2つで考える． 2つの文字列 \(s,t \) の LCP は，先頭から貪欲に調べれば求まる．次に複数の文字列を同時に判定することを考える． これは tre…

ABC284E Simple path の個数DFS で求まる．今の頂点 \(cu\) からの遷移が終わった後に， \(vis[cu] = false\) に戻す． 別の path で同じ頂点 \(cu\) に来た場合，区別して数えるから．実装戻り値に答えを入れた． つまり，戻り値に対して \(chmin(cnt, 1e6)…

ABC285E 素直に dp を考えると，\(dp_{i,j} := \) \([0,i)\) まで見て，最後の休日が \(j\) 日目 のときの min. しかし，これは失敗する． なぜなら，生産性は，今決めている日だけでなく，先の日の割り当て次第で 今日の近傍の生産性が変わってしまうから．…

ABC288E Key:買うときの値段を決めているのは何か．買う順序によって値段は変わる． しかし，よく見ると，今買うか決めようとしている商品の値段は， 既に何個買ったか だけに依存している． 買う順序や，どれを買ったかの集合には依存しない． 実装:あまり…