2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) - B. Berkomnadzor
概要
32bitのIPアドレスがN個与えられる。それぞれのアドレスには、悪いと良いがある。悪いアドレスは必ずブロックし、よいアドレスは必ず通す。何もないアドレスは、通すことにする。
ところで、サブネットというのを定める。192.168.0.1/8の下から8bit分以外一致してるのを、192.168.0.1/8のサブネットという。
このルールで、あるアドレスがよいアドレスでもあり、わるいアドレスでもある場合は、-1と出力せよ。そうでないのなら、このサブネットという構造を使って、ブロックするべきアドレスの数を最小化せよ。
制約： 1 <= N <= 2 * 10^5
ACするまで
1. 人のソースコードを見る。
2. 心を理解する。
3. 半分写経、半分自分で書く。 AC!(実装力だー！)
考察
この問題では、ひとまず次のように言い換える。
1. いくつかのよい区間と悪い区間が与えられる。
2. よい区間と悪い区間が交わることがあるのかをチェック
3. いい感じに、代表的なサブネットをみつける。
よい区間と悪い区間の交わりのチェックだが、ACソースコードのように、ソートしてしゃくとり法の要領でやるときれいに、しかも計算量がひとめでわかりやすい。
ここで、代表的なサブネットを見つけるにあたって、次のように考える。
サブネットのサイズをどんどん半分にしておいて、ちょうど含まれるようなサイズが初めて現れたのならば、それが代表的なサブネットとして答えとなる。
今回はとりわけ、IPアドレス自体も2のべき乗と相性がいいので、分割統治法でうまくいく。
分割統治の関数内で、
今見てるものの左端と右端(そしてその区間の長さ)、その左端と右端の間にある区間の一覧
を受け取って、
- すべてよいアドレスor悪いアドレスのならば、サブネットで完全に被覆できる。
- そうでないのならば、今の左端と右端の真ん中でまた(左端, 真ん中)と(真ん中, 右端)のように区間を分割する。
この際、分ける際で真ん中をまたぐような区間については、サブネットを設定するにあたって、他との整合性を考えるとどう考えても1つのサブネットにすることはできないので、左右2つに分割する(詳細はソースコード参照)
一言
分割統治法って言葉で説明するの難しいなぁ。まあ実装力がついたってことで
Special Thanks
2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror) Solution - 阿波罗2003 - 博客园
Codeforces紫色，实力果然非凡！非常感谢你的代码与解释！
