考え方 回答例 考え方dpを使うことはわかる．ただし，（座標範囲がデカ過ぎるため）座標をindexにしたdp[x][y]は使えない．「3通りの移動の仕方を何回ずつ選んだか」が「最終的な座標」と1対1対応するので，これをindexとして使えばよい．回答例次がキレイ S…

解法：しゃくとり法 考え方 回答例 解法：累積和（+set） 考え方 解法：しゃくとり法考え方3回のしゃくとり法で，$x = P, Q, R$に対し 区間和が$\sum_{[l, r)} A_{l} = x$を満たす$l$の集合$S_{x}$ $l$を$r$に対応させる辞書$f_{x} (l)=r$ を求めておく．Yes…

解法1 考え方 回答例 解法2：BFS 考え方 回答例 解法1考え方頂点を大きい方から見ていけば，「各街から到達できる街での最高値」がわかる． 求めたい答えは，「(街$i$から到達できる街での最高値) - (街$i$での購入価格)」．回答例 N, M = map(int, input().…

考え方 回答例 考え方「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．UnionFindの初期化では， すべての発電所をつなぐ イベントで切られない辺をつなぐ とすればよ…

よく使う距離について．検索すれば，わかりやすい図が出てくる． Euclidean vs Manhattan vs Chebyshev Distance例チェビシェフ距離（チェス盤距離）B - Nice Grid

方法1：転倒数 考え方 回答例 方法2：BFS 考え方 メモ 方法1：転倒数考え方最近，以下の出題があったので，「転倒数」が最初に浮かんだ． ABC261F - Sorting Color Balls - 競プロはじめました「自分より小さいのに自分よりあとに現れる数」の（すべての「自…

itertools.combinations()の使い方に注意が必要． 考え方 回答例 考え方$A$のどの行・列を残すかを全通り試せば良い．回答例itertools.combinations()を使えば簡単だが，2回使う場合には注意が必要．こうするとダメ． r = combinations(range(H1), H2) c = c…

方法1： 考え方 方法2：座標圧縮+いもす法 考え方 回答例 方法1：考え方$a, b$をイベント発生日としてまとめて扱い，イベント発生日を小さい順に考えると簡単に処理できる． Editorial - AtCoder Beginner Contest 188方法2：座標圧縮+いもす法考え方日をind…

考え方 回答例 考え方トーナメントは再帰で一つ下の階層の勝者を求められる．解法2がきれい． Editorial - AtCoder Beginner Contest 188 （Pythonの例：Submission #19320967 - AtCoder Beginner Contest 188）回答例 N = int(input()) A = list(map(int, i…

解法1：式変形 考え方 回答例 解法1：式変形考え方愚直に計算する方法を考えて，そのあと計算量を落とすことができるか検討する．$x, y$を全探索すると\begin{aligned} f(x, y) = Lx + \sum_{k = x + 1}^{N - y} A_{k} + yR \end{aligned}の最小値を計算でき…