IOI 2007 day2

100 - 100 - 100 = 300

A - Miners

とりあえず問題文が正しく理解できているかの確認のために O(2^N) を投げる。45 点。そしてそれぞれの組に最後に配った 2 個が何かを持つシンプルな dp で 100 点が取れる。もう 15 年程前の IOI だとはいえこれ程簡単な問題が出るとは...

B - Pairs

まず 1 次元を尺取りで実装して 30 点。2 次元をセグ木平面操作で 60 点。3 次元を 1 次元だけ固定して M^2 探索して、その全てに対して 2 次元 ver を解くという実装をする。2 次元をそのまま適用しようとして変なことをしたせいで TLE や WA を出すが、素直に少し変えた実装をして 100 点。この問題もかなりあっさりしている。

C - Training

問題を読み、かなり困ってしまう。本当によくわからなかったので落ち着いて部分点を考える。すると区間スケジューリングのようになる。恐らく合っているだろうから、ここから 100 点を考える。最大独立集合など色々と考えたが、最終的に舗装されていない辺であって、その端点 2 個の木上でのパスが共通辺を持つ 2 辺は一緒に残せず、逆にそうでないなら残すことが出来るという解法を思いつく。1 頂点の次数が 10 以下であるため、dp(i,j) = 頂点 i の部分木を見て、今辺 j を取る途中である or 何も取っていないという動的計画法が計算量は細かくは分からないが定数倍のある程度付いた O(NM) で通るだろうと思った。しかし途中で TL が 300 ms であることに気付く。とりあえず実装をしてみる。重実装であるためにバグらせるもなんとか 100 点。

感想

A,B がやけに簡単だった。昔の IOI は全完しないとまずいレベルなのだろうが、これがいつまで続くか...

ただ、C 問題で色々と自分の書き方が汚く重いことになってしまい、これはいつも思っているため改善する必要がある。