ABC317F 制約から，\(O(HW)\) は間に合う． よって，今いるマスを全探索は可能なので， それで DP を考える． 追加で持っておきたい情報として， 今いる行と列が，それぞれ flip しているか \(in 2 \times 2\) がある． 今居るマスと flip の情報で十分であ…

ABC317E 実装が少し面倒だが，ただの BFS. 前処理として，通れないマス全体を求めておくと楽． それさえ出来ていれば，グリッドに対する BFS をするだけ． 実装例: 公式解説の方法を載せる． 通れない頂点は，BFS で既に調べた頂点として初期化しておけばよ…

ABC317D 計算量を見ると，\(O(N * sum(Z))\) は間に合う． ここから DP を考えるというよりは，まずは自然に考える． 簡単に思いつくのは，\(i\) を固定したときの様子を探ること． \(i \in N\) を固定したとき何人を鞍替えさせれば良いかを考える． 鞍替え…

ec ABC317C 解法1: BitDP ハミルトン閉路と同様に， 状態 \(\,(s,v)\,\) の 2つ を持って遷移． ここで，\(s \in 2^{N}\) は訪れた頂点の集合， \(v \in s\) は最後に訪れた頂点． 試験中はこの方針で考えていた． しかし，\(s\) しか状態に持っていなかった…

ABC245F サイクルに到達出来る頂点の個数を求める． そうでない，無駄な頂点を省いていく． 具体的にサイクルを求めたりする必要はなく， 出次数が 1以上の頂点だけ通り続ければサイクルになる． 出次数が 0の頂点 \(v\) に到達しても，サイクルには到達でき…

\( \def \ra {\rightarrow} \) ABC257F テレポータの行き先を超頂点 \(X \not\in N\) とおく． \(X\) を頂点として加えたグラフを考える． これにより，テレポータの行き先を保留した状態でグラフを構成できる． \(X\) の行き先を \(i\) としたいときは， コ…

ABC252F 切り方は tree に対応する． つまり，最適な切り方を探すのは，最適な tree を探すことに対応する． しかし，tree 全体は探索しても間に合わない． Tree の葉に値を割り振って，parent に child の値を足していくと考える． すると，葉を除いた頂点…

ABC248F 状態をまとめて DP． 連結しているかどうかが重要． 今 i番目の コ の字の部分を決めようとしているとする． つまり，左側は既に決まっているとする． 上の頂点と下の頂点が，左側において連結しているかどうかだけが， 今後に影響する． \(dp_{i,k}…

ABC254F 長方形領域における GCD を求める問題． 2次元の計算を 1次元に落とす． 気持ちとしては，和や差によって GCD が変わらないことを利用して， 左上を基準のマスとして，残りは差分で計算したい． 行と列の差分を別々に計算することで，計算量を減らす…

ABC315F スキップした頂点が多いほどペナルティが大きくなる． スキップできる箇所はそんなに多くないのがポイント． スキップしないで頂点を通った場合，最大で \(2^{1/2} 10^{4}*n \leq 1.5 \cdot 10^{8}\). ペナルティがこれよりも大きい場合，ペナルティ…

ABC315参加． 2週間連続でやらかしてレーティングが合計100減った． これなら試験に参加しなければよかったと感じる． ランクが上がったところで気持ちよく終わっていればよかった． 勉強を続けても，試験は受けないほうが精神面でプラスだった． AtCoder の…

ABC315D あまり綺麗な解法がない．全探索によるシュミレーションを高速化する問題． 基本は， 何を全探索するか． 升目の全探索は，削除の処理を考えると TLE である． たとえば，aaaaabccccbdeeebdfghのような形が最悪ケース． 対策：色が 26種類と少ないこ…

ABC315E トポロジカルソート． 本問題は DFS, BFS どちらでも可能である． どちらでも良いときは，DFS の方が実装が軽いケースが多い． DFS のトポロジカルソートは，帰りがけ順で vertex を並べて， 最後に reverse. 試験本番では BFS で実装した． どこが…

ABC241F 大事な座標だけもって BFS. オブジェクトの周囲 4マスだけがグラフの頂点となる． map や upper_bound を使うので，遷移ごとに \(log(V)\) がかかる． ここで \(V\) は vertex の集合のサイズ． 前処理にもソートで \(log V\) が余分にかかる． 遷移…

ABC237F 制約から，DPで計算するときに 状態 \( O(NM^3) \), 遷移 \( O(M) \) でも間に合う． LIS の求め方を考えると， LIS の 3つの項が \(x,y,z\) のときを状態に持てばよい． 一旦，LIS を無視して考える． 長さ \(N\) の vector \(v\) であって，各元 \…

ABC236F \(V := (\mathbb{F}_{2}\) における \(N\) 次元ベクトル空間) の基底を求める問題． コストの小さいほうから貪欲に選んでいく． コストを無視すれば，吐き出し法で基底は求まる． \(b\) を 1次独立な vector の集合として，\(V\) を span できるまで…

ABC232F swap たち全て \(\rightarrow\) abs たち全ての順で操作をしても良い． まず \(n\) 次 permutation \(P\) を固定して， \(P\) に対するコストを求める． Swap of \(P\) の回数は，転倒数で求まる． これに \(y\) を掛けると，swap に対するコストに…

ABC224F 遷移が線形なので，行列積で書ける． + を置いたときに，+ より左にある項の和を \(t\), 今計算中の項を \(x\) とおく． 遷移は， \(s_{i}\) の直前に + を置く場合：\(t \rightarrow t + x\), \(x \rightarrow s_{i}\), \(1 \rightarrow 1\) となる…

ABC314E まず，0 の目が出ない様に変換しておく． 0 の個数を \(z\) 個とおく． 0 以外の目が出るまでの回数の期待値は \(\frac{p}{p-z}\) 回． \(c\) を \(c \cdot \frac{p}{p-z}\) で置き換えて，\(z\) を除いたルーレットで考えてよい． \(e_{x}\) を，ス…

ABC314D 原因不明の WA. 小文字(または大文字)に直す自作の関数でWA. 手元では，テストケースが正しく動いていた． 提出したら，テストケースもWA. 対策std::toupper, std::tolower を用いたら AC. クエリ先読み大文字，小文字の入れ替えを毎回実行したら， …

ABC214F 最後に使う文字を全探索する． 今 \(i \in N\) 文字目を見ているとする． \(j \leq i\) の範囲を，\(j\) を小さくしながら調べる． 初めて \(s_{j} \neq s_{i}\) となる直前までの \(j\) に対して， \(dp_{i} += dp_{j}\). 実装2文字前からスタート…

ABC220F 差分の更新で高速化の問題． まず，vertex を一つ固定した場合の答えを求まる． Vertex を 0で考えると，0 を根とした木に対してDFSをすればよい． 根からの距離はDFSの深さで求まる． 次に差分を考える． \(s \rightarrow t\) と vertex を遷移した…

ABC197F 問題文で与えられたグラフを \(G\) とおく． 解法1: BFS 素直な実装． 頂点が \(N \times N\) のグラフ \(\hat{G}\) を考える． \(\hat{G}\) における 頂点 \(\,(x,y), (nx,ny)\,\) に対する辺は， \(G\) において辺 \(e = (x,y,c), ne = (nx,ny,nc)…

ABC131F 格子点を2部グラフとして扱う． 点 \(\,(x,y)\,\) が与えられたとき， グラフ \(G\) において 頂点 \(v_{x}, v_{y}\) と 向無辺 \(\,\{v_{x}, v_{y}\}\,\) を作る． 点として現れる \(x\) 座標全体，\(y\) 座標全体を \(a_{x}, a_{y}\) とおく． \(c…

ABC153F まずは，爆弾を使う座標について考える． ダメージの入る範囲を \([x-d, x+d]\) でなく， \([x', x'+2d]\) と考える． 中途半端な位置で爆弾を使うメリットは無いため， 爆弾を使うときに左端に敵が居ると仮定してよい． 言い換えれば，左端に敵が居…

ABC154F パスカルの三角形を長方形で書く． \(r\) 行 \(c\) 列が \({}_{r+c}C_{r}\) となる． 長方形領域の和は，左上を\(\,(0,0)\,\) で固定して， 累積和と同様に計算すると良い． パスカルの三角形の性質 \(\sum{r \in [0,R] } f_{r,c} = f_{R,c+1}\) と…

ABC188E DAG であることを用いる．DP は DAG のときしか使えない． 売る町を全探索する． 町 \(i \in N\) に居るとき， 番号が \(i\) 未満の町は調べ終わっている． とくに，制約から \(i\) にたどり着く path は全て調べ終わっている． よって，それらの pa…

ABC190F 転倒数，クエリ問題． 毎回愚直に求めると間に合わないので，差分を更新する． \(b\) の先頭を一番後ろに持ってきても， 転倒数を計算するときの処理の大部分は使いまわせる． 先頭からの削除と，後ろへの追加を別々に処理出来れば十分． \(b\) の先…

ABC189F 漸化式を立てると，一見循環してしまう． これを式変形して循環しない形にして計算する． 振り出しに戻るものが厄介． そのときの答えを \(x\) とおいて， \(x\) に関する 1次式とみなす． \(dp_{i} := i\) に居るときの答え(期待値) とする． \(x =…

ABC313 ABC313 参加． 水色 になって嬉しい!! まぐれでなく，レーティングをあげるために対策をした結果なので， その取り組みも含めて満足した． 具体的には，水色問題の復習をメインにした． 新しく学ぶよりは，すでに解き方を知っている物を， 速く正確に…