2回やる意味はない
Codeforces
場合分け
2^K
添字のとりうる範囲がlogオーダー
Dijkstra法
最短路問題
DP値:ペア値
DP
グラフ
操作:辺の向きをflip
グラフの頂点を倍加する
パリティ
コーナーケース
2回やる意味はない
CodeforcesDIV1-C
CodeforcesR2400
AOJ-ICPC みを感じる! 問題へのリンク 問題概要 頂点数 、辺数 の有向グラフが与えられる。頂点 1 から頂点 へとたどり着きたい。以下の 2 種類の操作ができる。 頂点 上にいるとき、辺 をたどって、頂点 へと移動する 移動に要するコストは 1 任意の頂点に…
AtCoder
AtCoder500点
ABC-E
グラフ
DP
最短路問題
二値パラメータ問題
ほとんどのところで値が一定値に決まる
小さいところで帳尻を合わせる
Dijkstra法
グラフの頂点を倍加する
各kに対して
青色diff
2回やる意味はない
価格に関する問題
【問題集】最短路問題
これ、頂点を倍加してダイクストラする系。 問題へのリンク 問題概要 頂点 辺の連結な無向グラフが与えられる。各辺 には 通行に要する料金 円 (所持金が 以上でなければ通行できない) 通行に要する所要時間 秒 という属性がある。また、各頂点 では所持金を…
AtCoder
AtCoder300点
AGC-A
場合分け
最適化テク:探索候補を絞る
最適化テク:解を変形していく(最適性を失わずに)
最適化テク:端点のみを考える
2回やる意味はない
茶色diff
丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…
ライツアウト系の典型題 問題へのリンク 問題概要 × のグリッドと正の整数 が与えられる。各マスは 0 か 1 の値が振られている。今、以下の操作を好きな回数だけ行うことで、すべてのマスの値を 1 にしたい。それが可能かどうか判定せよ。 マスを 1 つ選んで…