NoviSteps6D
AOJ
AOJ-ICPC
NoviSteps6D
ICPCアジア
LP
双対性
LP双対
三分探索
多面体
考察：一部の変数を固定して考える
区分線形関数
凸関数
凸性に着目する
ギリギリ
最適化の考察：探索候補を絞る
最適化問題
最小コスト
最大スコア
有理数
にょぐた君と一緒に考察した。面白かった。公式解説は多面体で考えているけど、ここでは LP 双対で解いてみる。 問題へのリンク commentary 問題概要 種類の水溶液がある。水溶液 は、 として、 水溶液全体の重さが g 1 g あたりの溶質の重さが g 以上 g 以…
AOJ
AOJ-ICPC
ICPCアジア
NoviSteps6D
グラフ
二次元グリッド
マトロイド
マトロイドと劣モジュラ関数
最適化の考察：最適性条件を深く考える
DFS
二部グラフ
二部マッチング
フロー
【問題集】フローのチャレンジ
どれか1つ求める
復元
Union-Find
考察：パリティに着目する
パリティ
葉から考える
全域木を考える
市松模様・塗り分け
ICPC 本番に正解チームの現れなかった難問！ 問題へのリンク 問題概要 サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。 このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求め…
AtCoder
AtCoder2000～点
AGC-F
順列を題材とした問題
操作:隣接swap
操作:swap
操作
順列テク:逆順列を考える
考察：操作・条件・目的関数を言い換える
考察：変数変換
分割統治法
辞書順
最適化の考察：探索候補を絞る
グラフ
グラフの辺数を削減する
トポロジカルソート
priority_queue
Greedy
天才のGreedy
可視化：ペア値を二次元平面上に可視化する
考察：主客転倒・寄与分解
ソートすることが目的の操作の問題
操作後の結果の最適化問題
思わず解きたくなる興味深い良問
難しいGreedy
NoviSteps6D
これも自力で解けたの、嬉しい！！！！！ 問題へのリンク 問題概要 正の整数 が与えられる。 からなる順列 に対して、以下の操作を好きな回数だけ行ってできる順列のうち、辞書順最小のものを求めよ かつ を満たす に対して、 と を swap する 制約 まずは逆…
