ABC103 D Island War
解けそうで解けなくてとっても悔しかった．
問題概要
一直線に島々が並んでいて，隣り合う島どうしは橋がかけられていて行き来できる．
あるとき島の色々なところで喧嘩が起きた．そこで橋を撤去して喧嘩してる島を行き来できないようにすることで解決する．
最小で何本の橋を撤去すればよいか．
詳しくはここ見て
解法
うまい橋を撤去すれば一気にいろんな喧嘩を解決できるっぽい．さてどうやってうまい橋を選びましょうか．
喧嘩してる島のリストを番号の大きいほうが昇順になるようにソートする．(ここからは入力例2を使って行きます)
一番下の赤線は撤去してよさそうです．
①－②が通れないのでその一つ上の赤線である①－③も解決してます．
けれど②－③はまだ通れるのでここも撤去するべきです．
②－③を撤去したから②－④，①ー④も解決しています．③－④はまだ駄目なのでここも撤去しましょう．(下図参照)
これを最後まで続けると下の画像のようになります．
こうやって図で見たらどこの橋を撤去すればいいのか分かるけど，プログラムでどうやって実現しようと考えます．
この図のように✖の位置(橋を撤去した位置)と●の大小を比較すればよいことが分かります．
橋を新しく撤去するときは✖の値を更新しましょう．どういう値に更新すればいいかというと，
番号の大きい島 - 1
にするとよいです．
感想
コンテスト中の僕
や，喧嘩してる島を区間と捉えて共通部分とればいけそうやろ！ｗ （ここで喧嘩してる島のリストを普通にソートしてしまい迷宮入り）
コンテスト終了時僕
番号の大きいほうでソートする…？区間スケジューリング問題…？ぐぬぬ，あともうちょっとで分かりそうだったのに悔しい...．眠いし明日通そう．
翌日僕
(解説pdfを読んで)あー，天才．
やっと通せた...
Submission #2890973 - AtCoder Beginner Contest 103
これは気持ちが大きく動かされたのでブログ書くかー．(今)
早く緑になりたい
早く緑になりたい(練習しろ
