dohatsutsu’s diary

日記を書いています。

【No.032】「AdventCalendar用の記事(3つ目)立命館合宿2016 2日目 会津大学セット M問題 Monochrome Tile (RUPC2016 Day2 M)」

自分が過去に合宿で出題した問題の中から3つ選び、簡単な解説と当時の感想などを書いていきます。(この記事はその3つ目です)

 

立命館合宿2016 2日目 会津大学セット M問題 Monochrome Tile (RUPC2016 Day2 M)

問題URL

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=M

 

簡単にまとめると、次のクエリを高速に処理する問題です。

・x軸、y軸に平行な辺を持つ長方形の左上の座標と右下の座標が与えられる。すでに追加されてある長方形のいずれかと重なってしまうかどうかを判定し、もし重ならないのならばその長方形追加する。重なってしまうのならば追加しない。

 

この問題の想定解法はセグメントツリーです。

それぞれのノードには、set< pair<int,int> > を2つ持たせます。

片方には、そのノードに対応する区間を完全に覆っている長方形の上端のy座標と下端のy座標をpairにして入れるようにします。

もう片方には、そのノードに対応する区間の一部を覆っている長方形の上端のy座標と下端のy座標をpairにして入れるようにします。

このとき同じsetの中でpairどうしの重なりが生まれたら必ずマージするようにします。

 

・長方形を追加するのではなく、区間に一様に線分を追加するイメージです。

 

イメージ用のスライドを用意しました。

www.slideshare.net

区間を完全に覆っているものと、一部を覆っているもので分けるテクニックは、蟻本のp163,164 からヒントを得ました。

 

 

問題文が書いてあるページを見るとわかりますが、この問題文には致命的なミスがありました。( H と W が逆になっている )

 

しかしなぜかClarがコンテスト中に来ることはなく、コンテスト終了後にzerokugiさんのツイートでミスが発覚しました。

 

 

その日は深夜まで起きてリジャッジの作業を行いました。

 

その結果、polinkyチームがM問題をACし、2位から1位になるという逆転が起きてしまいました。

 

本当に申し訳ありませんでした・・・。

 

gist.github.com