ICPC 本番に正解チームの現れなかった難問！ 問題へのリンク 問題概要 サイズのグリッドグラフから、いくつかの頂点と辺を削除してできる連結なグラフが与えられる。 このグラフの全域木であって、どの 2 つの葉も、その間の距離が偶数であるものを 1 つ求め…

最初、頂点にアルファベット、辺に文字列を乗せたグラフを考えていたが、うまく解けなかった。 頂点に文字列を乗せて、しりとりが成立する箇所に辺を張ったグラフを考えるとうまくいった。 問題へのリンク 問題概要 英大文字 2 文字からなる 個の文字列 が与…

Dilworth の定理から、DAG の最小パス被覆！！ かつて流行った高度典型。 問題へのリンク 問題概要 個の文字列 が与えられる。各文字列には重み がついている。 これらの文字列から「どの 2 つの文字列も互いに他を部分文字列として含まない」という条件を満…

面白かった！！ 上手に変数変換することで「2 変数劣モジュラ関数の和の最小化」になるタイプの問題だった。 問題へのリンク 問題概要 考えたこと 一目見て、2 変数劣モジュラ関数の最小化 (燃やす埋める) っぽいと感じた。値が 500 以下というのも怪しい。 …

こういう系すごく楽しいよね 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向単純グラフ が与えられる。 このグラフ上で次の条件を満たすパス (同じ頂点を二度通らないものに限る) が存在するかどうかを判定し、そのようなパスの重みの最小値を求めよ…

需要供給を考え、さらに最小流量制約もある最小費用フロー！！！ 問題へのリンク 問題概要 左頂点数 、右頂点数 、辺数 の二部グラフが与えられる。各頂点は「赤」または「青」または「白」に塗られている。 さて、各辺は最初は白色である。そのうちの何本か…

2 変数劣モジュラ関数の和を最小カットで表すという、とても面白い問題！！！ 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... ..........…

二段階単体法のデバッグに苦労しました。 問題概要 初期状態が全要素が 0 であるような N 次元ベクトルに対し、 以下のような Q 個の区間クエリを実施して得られる結果が 全要素が等しい N 次元ベクトルとなるようにしたい。区間クエリ i: 閉区間 [ L[i], R[…