注意
こちらの記事は解説記事ではありません。 にぼしの思考垂れ流し記事です （若干解説してそうな雰囲気を醸し出しているが…）
２月2日の精進
まえがき
やあ
本文
ABC103 D-Islands War
[区間スケジューリング,貪欲,greedy,] 難しいですね。 お得に橋を切ることを考えているのですが、言語化ができなくて苦労している問題。
僕の思考
例的なものを書いてみます。 1番目の島と5番目の島を行き来でないようにするという条件を、<1,5>と書きます。
<1,5> <1,4> <3,4> という3つの条件があるときは、3番目の島と4番目の島をつなぐ橋を切断すると、 1の島からは4にも5にもいけなくなります。 よって上の3つの条件のとき 答えは 1（本の橋を切断すれば良い）
2つ目の例 <1,3> <1,5> <2,3> <3,5> <4,6> っていう5つの条件があるとき、 2番目の島と3番目の島をつなぐ橋を切断します。 すると、3つめの条件までは達成できました。 あとは <3,5> <4,6>です。 4番目の島と5番目の島を切断すれば条件を達成できます。 よって今回の例では答えは ２ です。 この時のものを超雑に図にしたものが
このツイートの一枚目の画像の左下です。
まあなとなくこんな感じで手元で描きながら頑張ってときました。
int main(){ int n , m; cin >> n >> m; vector<pair<int,int>> p(m); rep(i,m) { cin >> p[i].first >> p[i].second; //a[i]とb[i]を行き来できないようにしてほしい } SORT(p); map<int,int> disconnect_island; //1と縁を切らないと行けない島の最小の島番号を保持するって感じ map rep(i,m) { int a = p[i].first , b = p[i].second; //mapにp[i].firstをkeyでもつものがなければ追加 if(!disconnect_island.count(a)) { disconnect_island[a] = b ; } else { disconnect_island[a] = min(disconnect_island[a],b); } } //下準備が終わった int ans = 1 ; int a = 0 , b = 1e6; //cout << "a: " << a << " b: " << b << endl; for(auto x : disconnect_island) { int p1 = x.first , p2 = x.second ; //cout <<"p1: " << p1 << " p2: " << p2 << endl; //新たにきたp1とp2が納まっている？なら橋はまだ切らずに更新 //p1がbを超えるかp2がbを超えたらだめ if( b <= p1 ) { ans ++ ; a = p1 , b = p2; } else { a = p1 ; b = min(b,p2) ; } //cout << "a: " << a << " b: " << b << endl; } cout << ans << endl; }
お気持ち
1番目の島と６番目の島を交流できないようにしようってなったとき、２番目の島と４番目の島も交流できないようにしなきゃいけなかったとします。 すると、１本だけ橋を切断することで２つの条件を達成できないかな〜？ってなるんです（恐らく）
じゃあ、１つ目の 1 - 6 を切るためにはどうしよう。 → １か２か３か４か５の橋を切ればいい
２つ目の ２−４を切るには？ → ３か４ を切ればいい
じゃあ２つの条件の共通部分とって３か４切れば良いんだな 的な…
常に最適に切るにはどのように考えたら良いだろう。っていうルールをしっかり考えた上で、考えられたら貪欲法？で解こう。
解説PDFを読め
貪欲って、何が自明で何がそうじゃないかわからないですよね 解説PDFは優秀です。何が自明でそうじゃないか分かるようにはなりませんが、なれることはできそうです 先程も貼りましたが、解説PDF写経しました。こちらの２枚めと３枚目ですね。
ABC076 C - Dubious Document 2
また同じ問題をやってしまった。 記事はこちら 12月9日精進
