順序を求める問題
AtCoder
AtCoder500点
ABC-E
青色diff
グラフ問題
Union-Find
Kruskal法
条件の言い換え
密グラフ
順序を求める問題
操作
数列
葉から考える
最小全域木
全域木を考える
グラフの問題だと考えることが難しい問題
操作:2つのものを1つにマージ
最大スコア
操作後の結果の最適化問題
操作によって作れるものの集合を考える(判定関数を考える)
これをグラフの問題だと思えるかどうか！ 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…
Codeforces
EducationalCodeforces
CodeforcesR1700
文字列問題
ソート
辞書順
推移性に着目する
prefixとsuffix
そのまま覚えたい典型問題
順列の最適化
順序を求める問題
順列
順列は互換(swap操作)の積として表せる
すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…
の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題なん。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速…
区間
最短路問題
順序を求める問題
解を変形していく(最適性を失わずに)
端点のみを考える
Greedy
AGC-C
AtCoder
AtCoder700点
一直線上のN点の問題
黄色diff
点が移動していく問題
コンテスト本番における ウチのコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。 AGC 025 C Interval …
