IOI 2011 代表選抜 Day3, Day4
Day3 Deciphering
文字列からいくつか文字を取り去って、1文字以上の別な文字列を作る。但し、「aの次にbは来ない」のようないくつかの規則がある。何通りの異なる文字列が考えられるか。
適当なDP。
Day3 Report
1番目の人から順に仕事をする。仕事が終わったら自分の報告先に報告する。報告された人はまた自分の報告先に報告する。但し2回以上、同じ仕事の報告はしない。各人について、自分が仕事をするときに何通りの報告を受けたか求めよ。
グラフが「サイクルに木がぶらさがったものを集めたもの」になることを使う。サイクルをひとまとめにし、木にDFSで順序をつけると、segment treeを使って解ける。
Day3 UFO
盤面に同じ形のUFOをできるだけたくさん置きたい。UFOは回転させてはならない。UFOは辺で接してはならない。UFOが置けない場所には当然UFOがかぶってはならない。この条件下で、UFOの置き方を出力せよ。UFOをたくさん置いたらたくさん点数がもらえる。
時間を余して退屈しないためのoutput only問題。貪欲法では4/20点ももらえない問題。いろいろなアプローチが考えられるが、semiexpが本番で実装したのは以下の方法である。
まず、置き方を頂点、相容れない置き方の組み合わせを辺としたグラフを生成し、隣接リストで保持する。次に、貪欲法で最初の解を生成する。そして、「1つ頂点を選び、それに隣接する頂点に対応する置き方をすべて解除する。そして選んだ頂点に対応する置き方を実行し、他にも可能な置き方があったら適当に実行する」という操作を何回も行う。
また、UFOが単純な形(1*1)の場合は、ビットDPでも、2部グラフの最大安定集合を求めても、どっちでも解ける。この場合は厳密解が求まる。
Day4 Apples
リンゴの入荷と出荷のクエリが与えられるので処理する。入荷はある「濃さ」のリンゴを入荷するクエリである。出荷はある個数のリンゴを出荷するクエリで、(濃さの最大値-濃さの最小値)は常に一定なM以下でないとならない。可能な出荷法がいくつもあるなら、リンゴの濃さの和が最大となるものを選ぶ。出荷できる場合は選んだリンゴをすぐに出荷する。さもなくば何も出荷しない。これをオンラインで処理せよ。
オフラインだったら座標圧縮×Starry Sky Treeで解ける。オンラインの場合も、Starry Sky Treeを動的に構成するようにすると解ける。この問題はfflushを余計に使うとTLEで50点も落とす難しい問題なので注意。
Day4 Bookshelf
本を滅茶苦茶な順番で本棚に入れてしまった。次の操作を繰り返してソートしたい。「1つの本を選び持っておく。今本棚に入っている本を何冊か横にすべらせて空きスペースを移動し、最後に持っておいた本を空きスペースに戻す。」
本には重さがある。持っておく本の重さの和を最小化せよ。
移動するために持っておかない本だけを考えると、本の順序が最初から正しくないといけないことがわかる。逆に最初から正しい順序なら、他の本を移動すれば整列できることもわかる。よって、最長増加部分列もどきをやれば解ける。segment treeを使えば容易。
Day4 IOI
IOIで、何人かの選手がいて、問題はN問ある。すでにM問の試験が行われ、点数が確定している。IOIでは「選手の1/12以上がその点数以上であるような最大の数」を金メダルボーダーとし、そのボーダー以上の選手に金メダルが与えられる。金メダル確定の選手と、金メダル候補の選手を出力せよ。
二分探索。例えば200点とった選手が金メダル確定なら、230点とった選手も確定である。
