IOI2007 結果発表
国際情報オリンピック2007 クロアチア大会の結果が発表されました。日本の代表選手は金・銀・銅を各１つずつ*1取れたみたいですね。おしくもメダルを逃してしまった選手ももうちょっとのところだったそうです。関係者の皆さま、お疲れ様でした。日本代表の速報ページで、表彰式の様子も含め、日本チームの写真を見ることができるようです。
ランキングの得点状況を見ると、いずれの問題も100点を取っている選手が要る中で、全問正解は無し、ということで、問題セットはとてもバランスが取れていたのではないかと思います。部分点は簡単に取れるが、満点を目指すと非常に難しいという情オリ的に適切な問題がそろっていました。ICPC では、全てのテストケースに通らないと点が入りませんので、こんな問題が出たら阿鼻叫喚になりますが（＾＾；；
また、問題の解説がダウンロード可能になっていますね。ざっとしか見ていませんが、やはり TRAINING がグラフの性質を丁寧に分析しないといけないため、一番難しそうでした。
FLOOD は一番外の壁を知りたいだけなら、一番端から壁に沿って歩いていけばいいだけでしたね。解けそうなやり方が見えてしまうとそれに固執してしまいがちですが、柔軟な発想が必要ですね。
PAIRS は "diagonal coordinates" を使ってできるだけ 1D に落としてから、sweep-line アルゴリズムを使う、というのが正解でした。1D と 2D と 3D をいっぺんに処理しようとしてはいけなかったようです……。ちなみに、コンテスト終了後、解析モードでプログラムを試行できるようになりましたので、2D木でしばらく頑張ってみましたが、最適化してもしなくても56点しか取れませんでした。無念。
sweep-line アルゴリズムは 1D 上の区間の重なりを調べるアルゴリズムで、まず、区間の入と区間の出の点を混ぜてソートしてから、小さい方から順に調べていき、入にたどり着くたびにカウンタを1上げ、出にたどり着くたびにカウンタを1下げることで、ある座標でどのくらい区間が重なっているかを得ることができる、というものだったような気がしますが曖昧です。今回の話だと、全ての点が [x-D, x+D] という区間を持っていると思って、全ての点の座標において区間が重なっている数を合計すれば答えが出るわけですが、そのまま実装するとメモリが溢れそうな気がするので少し変形するのでしょう。解説には head とか tail とか書いてましたが、眠いのでまた明日……。なお、"diagonal coordinates" に関しては昔聞いたことがあるような気もしますが、完全に記憶の彼方へ。やっぱり普段からの勉強は大事だ、ということで。
追記: 1D 上のある範囲に含まれる頂点数を O(log M) で取得できる Binary Indexed Tree などなど
Binary Indexed Tree は頂点の挿入と削除も O(log M) であることが重要かも。ただし、メモリは O(M) で使用しますので、適用範囲は限られます。詳細は↓
PAIRS
PAIRS の 1D は、普通に sweep-line アルゴリズムを適用すればいいだけですね。メモリが足りなくなるというのは、座標の最大値 75M と頂点数 100k 個を少し勘違いしていました。もっとも、解答通り、head と tail で頂点リストを少しずれながら追いかけていけば、x-D や x+D といった点は扱わなくて済みますので、定数係数は減ります。が、自分で解くなら何も考えずに x-D と x+D を加えて並べておいて、あとで重複分を除く形で実装してしまうかも。どちらにせよ、境界条件で微妙に気をつけないといけないところがあるので要注意。幾何の問題はだから苦手です。
sweep-line を実装したものを何パターンか書いてみます。実際に実行すると、それほど実行時間は変わらなかったりします。
// 何も考えずに重複したまま数えてあとで引くバージョン enum { POINT_IN = 0, POINT_CENTER = 1, POINT_OUT = 2 }; // 今回は閉区間なので、IN -> CENTER -> OUT の順番で評価する必要があります // P[i][0] に i 番目の点の座標が入っています long long calc_1D(void) { vector<int> v; for ( int i = 0; i < N; i++ ) { v.push_back((P[i][0]-D)*4 + POINT_IN); v.push_back( P[i][0] *4 + POINT_CENTER); v.push_back((P[i][0]+D)*4 + POINT_OUT); } sort(v.begin(), v.end()); long long result = 0; int ranges = 0; for ( vector<int>::iterator iter = v.begin(); iter != v.end(); ++iter ) { switch (*iter & 3) { case POINT_IN: ranges++; // 区間へ入った break; case POINT_CENTER: result += ranges; // 頂点の座標で、重なっている区間の数を足す break; case POINT_OUT: ranges--; // 区間から出た break; } } result -= N; // 自分同士を除く result /= 2; // A-B と B-A の重複を除く return result; }
// map を使って、同一座標の点の個数を管理したバージョン enum { POINT_IN = 0, POINT_CENTER = 1, }; // 今回は閉区間なので、IN -> CENTER の順番で評価する必要があります long long calc_1D(void) { map<int, int> m; for ( int i = 0; i < N; i++ ) { ++ m[ (P[i][0]-D)*2 + POINT_IN ]; ++ m[ (P[i][0] )*2 + POINT_CENTER ]; } long long result = 0; int ranges = 0; for ( map<int, int>::iterator iter = m.begin(); iter != m.end(); ++iter ) { switch (iter->first & 1) { case POINT_IN: ranges += iter->second; break; case POINT_CENTER: ranges -= iter->second; result += ranges * iter->second; result += (iter->second - 1) * iter->second / 2; // 同じ座標のペアを追加 break; } } return result; }
// 解答にある head と tail を使ったバージョン long long calc_1D(void) { vector<int> v; for ( int i = 0; i < N; i++ ) { v.push_back( P[i][0] ); } sort(v.begin(), v.end()); long long result = 0; vector<int>::iterator head = v.begin(); vector<int>::iterator tail = v.begin(); for ( ; head != v.end(); ++head ) { while ( *tail < *head - D ) ++tail; // *head が番犬代わり result += (head - tail); // vector::iterator は引き算で間の個数+1が出ます } return result; }
こうして書いてみると最後のバージョンがもっともシンプルではありますね。
さて、2D では x + y と x - y で 1D の問題2つに次元を落として、両者で距離が D 以下になる点のペアの共通集合を求める、という問題に変換するわけですが、すぐには O(N log M) で解ける方法が分かりません。なお、M は整数座標値の範囲です。解説には、Binary Indexed Tree を使え、と書いてありますので、少しカンニング。
ということで、2D の計算部分を Binary Indexed Tree で実装してみました。今回、座標値の範囲は [1, 75000] であることに注意。
typedef int Node; #define NODE_MAX 150001 // (75000, 75000) の時の 150000 まで受け入れる必要がある void insertValue(Node* tree, int value) { while ( value < NODE_MAX ) { tree[value]++; value += (value & (-value)); // 一番下の 1 のビット位置に 1 を足す } } void removeValue(Node* tree, int value) { while ( value < NODE_MAX ) { tree[value]--; value += (value & (-value)); // 一番下の 1 のビット位置に 1 を足す } } // [1, value] の累積カウントを求める int getSum(Node* tree, int value) { int result = 0; if ( value >= NODE_MAX ) value = NODE_MAX-1; while ( value > 0 ) { result += tree[value]; value &= (value - 1); // 一番下の 1 を寝かせる有名な演算 } return result; } // [lower, upper] の累積カウントを求める int getRange(Node* tree, int lower, int upper) { return getSum( tree, upper ) - getSum( tree, lower - 1 ); } // P[i][0] と P[i][1] に i 番目の点の x 座標と y 座標が入っています long long calc_2D(void) { multiset<pair<int, int> > m; for ( int i = 0; i < N; i++ ) { m.insert(pair<int, int>(P[i][0] - P[i][1], P[i][0] + P[i][1])); } // m は既に pair.first で整列されていますので、sort の必要はありません Node* tree = new Node[NODE_MAX]; memset(tree, 0, sizeof(Node[NODE_MAX])); long long result = 0; multiset<pair<int, int> >::iterator head = m.begin(); multiset<pair<int, int> >::iterator tail = m.begin(); while ( head != m.end() ) { while ( tail->first < head->first - D ) { removeValue( tree, tail->second ); ++tail; } result += getRange( tree, head->second - D, head->second + D ); insertValue( tree, head->second ); ++head; } delete[] tree; return result; }
最初、multiset
それにしても、Binary Indexed Tree って巧妙なデータ構造ですね。更新する際は、自分を含む親は右上の親だけですので、次の右上の親に行けるように、一番下の1のビット位置に1を足します。累積カウントを取りたい場合は、自分より小さい値の親（左上の親）の値を足せばいいので、次の左上の親に行けるように、一番下の1を寝かします。更新する際に index が溢れた場合は終了すればいいですし、累積カウントを取る場合はビットを寝かせるだけですので単調に index は減少します。そのため、node は必要最低限だけ確保すればかまいません。値として0も扱わないといけない場合には注意が必要ですが、オフセットを足して必ず1以上にしてしまったほうが簡単かもしれませんね。
さて、3D を解くには、さらにこの binary indexed tree を 3D に拡張して、(x + y + z, x + y - z, x - y + z, x - y - z) で同様に計算するとのことですが、3D に拡張するってそんなに簡単な仕事ですか？衝突検出のプロフェッショナルなら簡単に書ける問題なんでせうか。なお、O(N (log M)^3) とのこと。1段ごとに軸をずらすとか、（同じことですが）octet-tree にするとか、いろいろ考えてみたのですが、僕にはすぐには思いつきません……。
模範解答もアップしていただけることを楽しみにしております。＞tsuyoshi氏
*1:IOI では上位1/12が金、さらに2/12が銀、3/12が銅となります。
