Greedy:後によいものを残す・今が良いほど未来も良い
パリティ
各桁ごとに見る
市松模様・塗り分け
構築
マンハッタン距離
テク:45度回す
変数変換して扱いやすい同型な問題を見出す
ABC-D
AtCoder
AtCoder600点
ARC-D
橙色diff
2^K
Greedy
小さいところで帳尻を合わせる
考察：独立に考えてよい
x軸とy軸について独立に考えてよい
NoviSteps3D
Greedy:後によいものを残す・今が良いほど未来も良い
くやしい 問題へのリンク 問題概要 個の座標 () が与えられる。 今、40 本以下の正の整数 を用意して、それぞれについて (), (), (), () をうまく選択して加算することで、() をすべて作れ。できないときは -1 とせよ。 各 について共通の を用いなければな…
スケジューリング
区間スケジューリング
区間
区間ソート
Greedy
AtCoder
AtCoder400点
ABC-D
水色diff
双対性
そのまま覚えたい典型問題
思わず解きたくなる興味深い良問
探索順序を工夫して解く
被覆
Greedy:後によいものを残す・今が良いほど未来も良い
Greedy:交換しても悪化しない
NoviSteps1Q
問題へのリンク 実は、こないだの RUPC 2018 で出てた (最後の部分のみほぼ同じ) AOJ 2873 - 検閲により置換 見た目は区間スケジューリング問題とは違うけど、実は区間スケジューリング問題 (こういうの双対問題と言ったりする)。双対性の知識がまったくなく…
操作
最小回数・最小個数を求める
Greedy
AtCoder
AtCoder200点
AGC-A
区間
テク:区間ごとに分割する
パリティ
数列
最小コスト
操作:上書き
灰色diff
スライムやその合体をテーマとした問題
最適化問題
操作:1文字を変更する
Greedy:後によいものを残す・今が良いほど未来も良い
NoviSteps4Q
最初スライムの色の種類が 種類かと思ってしまって、 の場合が面倒じゃないかと思ってしまった。 Colorful Slimes 2 へのリンク 問題概要 (AGC 026 A) 1〜10000 の整数からなる 要素の数列が与えられる。 数列の好きな箇所を選んで 1〜10000 のうちの好きな…
