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 =…