Make Reportite
この記事は未完成です ごめんね
--------------------------------------------------------------------------
レポート課題を作成することを指す造語。
"Reportite"は、レポート・課題という意味の英単語 "Report" の形容詞を指す造語。読みは「りぱーたいと」。由来は、
当時大学で授業をしていた名物教授がレポートのことを「リポート」と呼んでいたこと
の2つ。
名詞を形容詞化していたり、元ネタのBipartite（びぱーたいと）という読みに引っ張られて、本来「りぽーたいと」になるはずが「りぱーたいと」になっていたりと、訳の分からないことになっている。
…というわけで、ここからはMake Bipartiteの解き方について解説する。
問題概要
以下の図のように$ N+1個の町と$ 2N本の橋が存在しており、橋にはそれぞれ修繕コストが割り当てられている。
（町の図）
厳密には、
町$ 0と町$ iを結ぶ橋には修繕コスト$ A_iの橋
$ 0 \leq i \leq Nを満たす整数$ iについて、町$ iと町$ (i+1)には修繕コスト$ B_iの橋
ただし、町$ N+1は町$ 1のことを指す。
が架かっている。
これから、各町を赤色か青色のいずれかに塗リ、全ての町を塗った後、両端の町が同じ色で塗られている橋は崩落する。
あなたは、崩落した橋すべての修繕にかかるコストの総和をできるだけ小さくしたい。うまく町を塗り分けたとき、修繕コストの総和の最小値はいくつになるか。
制約
- $ 3 \leq N \leq 2 \times 10 ^ 5
- $ 1 \leq A_i \leq 10^9
- $ 1 \leq B_i \leq 10^9
考察
それぞれの橋の修繕コストがバラバラなので、全ての町の塗り分けパターンを試さないと答えは出なさそうだ。ところが、$ N+1個の各町についてそれぞれ$ 2色で塗れるので、塗り分けパターンは全部で$ 2^{N+1}通りもある。これを工夫なしに全て試すのは時間的に到底不可能である。よって、塗り分けパターンを工夫して減らそう。
まず、町$ 0は赤色で塗るとしてよい。なぜなら、町$ 0が青色に塗られた以下の左図の塗り分けパターンの修繕コストは、右図の町$ 0が赤色に塗られた以下の右図の塗り分けパターンの修繕コストと全く同じだからである。
（各町の色をflipした図）
これは、他の町$ 0が青色に塗られた塗り分けパターンでも同じことが言える。
このような、特殊な状況を仮定しても、議論全体に影響を及ぼさないことを「一般性を失わない」という。 それぞれの町同士の色が複雑に作用しあっているように見えるが、町$ 0以外のひとつの町だけを取ってみると、$ 3本の橋しかつながっていない。また、町$ 0は確実に赤色で塗られているので、隣接している$ 2つの町の色だけ考えればよい。
ここで、町$ 1から町$ Nまで順番に色を塗っていくことを考える。モチベーションとしては、隣接している町の色によって崩落する橋がわかるので、なるべく隣接している町の色が多く確定しているところから順番に塗っていきたいという気持ちだ。
ここで、隣接している町の色のみで崩落する橋が決まることから、町$ 1から町$ i-1($ iは$ 2以上$ N - 1以下の整数)まで色を塗り、町$ iの色を塗るときに、
町$ 1と町$ i-1の色以外の情報は必要ない。
ということがわかる。なぜなら、これから色を決める町$ i〜$ Nが接するのは、町$ 0,1,i-1〜$ Nまでしかないからである。
（町iが町0,1,i-1としか接する可能性がないことを示す図）
よって、町2からnまでのn-1通りについて、1とi-1の色のパターン4通りの計通りについて、最小値がわかっていれば高校数学の漸化式の要領で求めていくことができる。修繕コストを
$ red \lbrack 1 \rbrack \lbrack 0 \rbrack = A_1
$ red \lbrack 1 \rbrack \lbrack 1 \rbrack = \infty
$ blue \lbrack 1 \rbrack \lbrack 1 \rbrack = 0
$ blue \lbrack 1 \rbrack \lbrack 0 \rbrack = \infty
$ red \lbrack i \rbrack \lbrack 1 \rbrack = min(red \lbrack i-1 \rbrack \lbrack 0 \rbrack + A_i, ~red \lbrack i-1 \rbrack \lbrack 1 \rbrack + A_i + B_{i-1})
$ red \lbrack i \rbrack \lbrack 0 \rbrack = min(red \lbrack i-1 \rbrack \lbrack 0 \rbrack + B_{i-1}, ~red \lbrack i-1 \rbrack \lbrack 1 \rbrack)
$ red \lbrack N \rbrack \lbrack 0 \rbrack = min(red \lbrack i-1 \rbrack \lbrack 0 \rbrack + B_{i-1}, ~red \lbrack i-1 \rbrack \lbrack 1 \rbrack)
「町$ 1を赤く塗り、町$ iまで塗り、町$ iの色を赤色に塗ったときは時の確定している橋の修繕コストの最小値を$ red \lbrack i \rbrack \lbrack color \rbrackを定義する。
dpをつかえばできる（ここが一番むずくね？？？実際本番でもここが思いつかなかったし）
中央の頂点は赤色で塗ってよい（うん）
一つの頂点を見ると、隣接している2頂点と頂点0だけ見ればよい→意外と情報量はすくない
頭からのいくつか決まっていたら最初と今見ている最後の頂点の色の4パターンでの最小値だけもっておけばok（前の説明がちゃんとできれば、妥当な考え）
dpを立てる
定義を明示する
遷移を考える（4パターンを図示すればわかりやすいだろう）
頂点1と頂点Nの判定をする（ここだけAd-hoc）
よって、この問題を解くことができた。
解答例（C++）
考察がしっかりできていれば、実装は非常に軽い。