世界大会

ICPC

負けました。
http://icpc.baylor.edu/icpc/Finals/default.htm
http://icpc.baylor.edu/icpc/Finals/Standings2006.html


というわけで、
優勝はロシアのSaratov State大学ということです。
今年は一位チームが6問と、去年からさらに問題が大幅難化、
まさにうちのチームには困った傾向で、
さらに悪いことに二問も泥沼にはまったので、
もうどうしようもこうしようもない状態になってしまいました。
書いても書いても通らないというのはなんとも残酷で、
それでも最後の意地で三問目を通して、オフィシャルには
Nineteenth placeということになりました。
正直悔しくて悔しくてたまらない。
6問はちょっと厳しいとしても、5問では完全にメダル圏で、
4問でもペナルティーが少なければ銅という結果で、
しかも、5問というのはどう考えても不可能な領域ではないと思うので、
本当にもうどうしたものか。
しかし、上方向にも紙一重なら、下方向にも紙一重で、
うちも三問目を通したのが残り数分だったりするので、
ヘタをすると二問でも一問でも全然おかしくなかったのです。
大会直前のechizenからのメールが無かったら問題Dは解けていなかっただろうし、
コーディング時間のEstimateが少しでも狂っていたら問題Aは解けていなかった。
今回は本当に厳しい戦いだったのです。


今は目標を失ったということで、かなりうつろな気分です。
大会期間は大会のための練習を継続的に行うモチベーションを
どうやって保とうかと苦労していたのですが、
まったくもってナンセンスで、
大会に出ること自体が練習するモチベーションではないか。
終わって気づきました。
もう、これ以降はこんなにアグレッシブに
自分の能力を高める努力をする動機はなくなってしまいましたが、
私がこの4年で手に入れた能力は惨敗した今でも嘘では無いと思うので、
今後はそれを利用して何かを生み出す活動を
積極的に行っていきましょうか。
とはいっても、これから何週間かは使い物にならないかもしれません。
ちょっと今はプログラムは書きたくない。


全てを清算するために、近日中にいつもどおりまとまった記事を書くつもりです。
それまでに、ひとまず、全体の感想と思いついた分の解法を載せておきます。
自分で考えたい方はスキップしてください。


・問題
http://icpc.baylor.edu/icpc/Finals/2006WorldFinalProblemSet.pdf


問題数は10問。
今年は"解ける"問題は去年より一つ多い、9問のようですが、
平均のレベルが高すぎるので、全問解くのは到底不可能です。
一問超易問が入っているのですが、
どうも中程度の問題がすっかり抜け落ちているように思います。
私は、去年がグラフたくさん、アルゴリズム重視、難問、
という傾向だったので、今年はビバリーヒルズのときみたく
易問傾向になると思っていたんですが、
どうやら、この路線は継続されたようです。
おおよそICPCがこれから規模を拡大していくのなら、
この路線はこれからも変わらないかもしれません。
大会のレベルが上がるのに、問題のレベルを落とす意味はありませんし…。
今回は時間的制約からやはり一位のチームの6問正解というのが
現在の人類の限界では無いでしょうか。
五問正解程度なら、スケジューリングがうまく行っていれば
うちのチームでも不可能で無いはず。
しかし、難問ぞろいのために、
スケジューリングがうまく行かない可能性は非常に高い。
あのいつも非常に安定しているSJTUでも5問で、
あの北京大会で7問もといたFudanが2問しか解けなかった
http://icpc.baylor.edu/icpc/regionals/ViewRegionalStandings.asp?ContestID=742
というあたりに如実に現れているかと思います。
というか、今回アジア勢は入賞がSJTUだけというのは
一体どうなってしまったのだろう？


・各論

  • 問題A
    • 概要（グラフ・難）

複数の街を経由して移動する航空券がいくつか(<=20)ある。
一つの航空券が経由する街は10まで。
航空券は途中まで移動して捨ててしまってもいい。
ある旅程(これは同じ街を何度も通ることもありうる)が与えられたとき、
それを最小金額で実現できるチケットの使用順と合計金額を求めよ。

    • 解法

各町に旅程がどこまで進んだ状態でいるか、というのをノードにして
(街*旅程の拡大グラフで)その上でダイクストラ。
実装がかなり厄介。
私は普段以上の能力を出して通すまでに40分かかったようだ。

  • 問題B
    • 概要（グラフ・難？易？）

数種クレープ？(各数枚)と数種のアイスクリーム？(各数個)がある。
(それぞれ50種まで)
あるクレープとあるアイスクリームを組み合わせたときにどれぐらいおいしいかが
与えられるので、全てのクレープとアイスクリームを使い尽くしたときの
おいしさの合計の最大値と最小値を求めよ。

    • 解法

どうみても、最小費用流です。
もはやトラウマ。なんでこれが通らない？TLE、TLE、TLE…
どう考えても、実行時にO2をつけてもらえなかったせいです。
帰国後にGNCのN氏に線形最適化を施してもらって、
最適化なしで20倍の高速化を達成する。
どうやら、二段vectorはO2なしだととても遅いようなので、
来年以降要注意です。
定数項に十分な数値を見ていると大会本部は言っておりますが、
うそです。
アルゴリズムがあってれば通すみたいなこといってますが、
うそです。
実際に通ってるチームと同じアルゴリズムなので、
うそです。
世界大会ではPKUと同じく実行速度に気をつけるべし。
とにかく、二段vectorはつぶすこと。

  • 問題C
    • 概要（幾何・不明）

与えられた三次元上の線分と頂点で構成された立体が
重力で自然につぶれるか、指で押すとつぶれるか、
あるいは頑丈か、を求める問題。

    • 解法

華麗にスルーが正解。

  • 問題D
    • 概要（数論・難？）

AAA...BBB... なる、二種類の連続する数からなる数を
Bipartite Numberという。
ある数(<100000)の2倍以上の倍数のうちで、
最小のBipartite Numberを求めよ。

    • 解法（thanks to echizen!）

http://acm.pku.edu.cn/JudgeOnline/problem?id=2283
これの解き方を応用。
最初に1,..,9をキューに突っ込む。
キューから数を取り出しつつ剰余を調べて、
0なら答えが見つかった（元の数がBipartite Numberのときは注意）。
そうでなければキューから取り出した数に、
元の数が同一の数からのみなるのなら→
後ろに任意の数字を付け加え、それぞれをキューに突っ込む。
既に二種類の数からなるのなら→
後ろに一番後ろの数を付け加え、それをキューに突っ込む。
なお、これだと探索空間が広くなりすぎるかもしれないので、
剰余を利用して探索を打ち切る。
同じ剰余、最後の数字、のときは、
次に生成する数の剰余も同じなはずなので、
与えられた数*10程度の探索を行えばよいということになる。

  • 問題E
    • 概要（探索・やや難？）

ビット列を考える。
1の連続の出現を連続している数の二進表現と置き換える、
という圧縮を考える。
圧縮は、短くなるとき常に行う。
短くならないのなら圧縮しない。
そのような圧縮済系列と元の長さ、1の個数が与えられたときに、
元の系列を一意に復元できるか？
圧縮系列は40ビット以下。元の長さは16K以下。

    • 解法

普通に問題の仕様どおりに深さ優先探索をすれば
余裕で間に合うようです。
それに気づかなかった私の負け。
もうすこし、問題を考える時間を与えてもらえればなぁ…。

  • 問題F
    • 概要（探索・かなり難）

ギア（6個以下）を組み合わせて時計を作る。
（詳細不明）

    • 解法

全探索すれば計算量的には間に合いそうだが、
いかんせん問題の仕様が複雑なので、
かなり難しいと思われる。
解いてたチームがあったかどうか。

  • 問題G
    • 概要（数論・やや難）

パーティーが旅をしている。
パーティーはお金を持っていて、
パーティーに人が加わったり、出て行ったり、
お金を集めたり、お金を払ったりする。
パーティーの所持金をN、人数をMとする。
パーティーにメンバが加入するときは、
一人当たり、N/Mのお金を持ってきてもらう。
メンバーが離脱するときは、
一人当たりN/Mのお金を持たせてあげる。
一人当たりKのお金を集める、
全体でK(<=2000)のお金を支払う、
というコマンドがある。
ここで、ある操作の列(長さ50以下)が与えられたとき、
運の良いことに全ての操作でお金の端数が出なかった。
ありうる初期人数を全て求めよ、
あるいはそういう解は無限にあるか？

    • 解法

一人当たりの所持金を考えると問題はとたんに簡単になる。
ある時点でのパーティーの人数をn、
一人当たりの所持金をmとする。
各操作におけるn,mの変化を考える。
IN k -> n+=k, m変わらず。
OUT k -> n-=k, m変わらず。
COLLECT k → n変わらず、m+=k。
PAY k → n変わらず、m-=k/n。
これらを考えるに、任意の時点での一人当たりの所持金は
m+(a1/(n+b1))+(a2/(n+b2))+...(an/(n+bn)) となる。
IN、OUT発生時にこの分数の列が整数かどうかを調べればよい。
ちなみに、自明にmは任意であるので、
分数の部分だけ考えればよいし、
COLLECTは全体にわたって無視しても良い。
IN,OUTの前のPAYは無視しないといけない。
PAYが一度でもあって、その後にIN/OUTがあれば解は必ずに有限になる。
しかも、その最大値は2000*50程度。
1から100000まで、全てについてnに代入して
分数を実際に計算して、整数になるものをフィルターしても間に合いそう。
あとは、IN/OUTから生じる人数の最小値を考慮すればOK。
これも、私にもうすこし考える時間がもらえれば…。

n*n(n<=64)正方形の紙を折りたたんで、1*1正方形にする。
そのときに出来るポケットの数を求めよ。

    • 解法

各1*1正方形に(1,1)から(n,n)の番号を振る。
折りたたまれた後、これらの正方形が
どういう向きで、どういう順につみあがるのか、を計算する。
それから、それを下からスキャンして、
各正方形の隣接正方形がどこにあるかを調べる。
それらに挟まる区間は袋とじみたいになっていることが分かる。
全て完了したら、四辺おのおのについて
どの区間が袋とじになっているかがわかるので、
あとはポケットの数をカウントするのはとても簡単。
実装はかなり大変だと思われる。
紙の折りたたみ、区間の計算、ともに一問級。
私のEstimateだと一時間以上は優にかかるんではないか。
この問題を解き始めるぐらいなら、
他の問題の解法を考えた方が早いに違いない。
残り一時間で手をつけているチームすらなし。

  • 問題I
    • 概要（グラフ・易）

人物の相関関係が与えられて、
一番関係の最短距離が長いペアの距離を求める。

    • 解法

ウォーシャルフロイド一発。
MITがなんと10分で通した。
私はMITが解いたのを見てから解いて+15分かかった。
速すぎるぞ、MITハッカー。

  • 問題J
    • 概要（グラフ・とても難）

有向グラフ(ノード数50以下)が与えられて、
ノード1とノード2が双方向通信をしたい。
ただし、安全のために、
データを経由するノードにはウイルスソフトをインストールしたい。
ライセンス料を最小にするために、
データを経由するノードを最小にしたい。
最小何ノード経由させる必要があるか？

    • 解法

分からない。
解ける問題のうちでは最難ではないか？

        • -

ちょっとストーリーは、又聞きなので、
適当に脳内補完した部分があるが、
概要としてはこんな感じである。
今回、全体的に異様に正答率が低いので、
(ほとんどの問題で10%を切っている)
7問ぐらいに手をつけて、5問ぐらい正解するのが
よろしいのではないか？
問題Bがとおらないのは論外。本当にくやしい。
ところで、なんで最近は幾何の問題が
出題する意味も分からないほど難しい問題しか
出なくなったんだろうか？
幾何はもう準備しなくてもいいのかもしれん…