ICPC練習会

この前の合宿に続き、今日は"東京大学"でICPCの練習会が
あったもよう。まぁ、うちのチームにとっちゃ東京大学でも
北海道大学でもあんまり変わりは無いのですが。
東京に行くわけにもいかないので、オンラインからこっそり参加となったわけです。
(いつもの)M氏と2人でしたが…。
もう一人のチームメンバのK氏はオンラインにいなかった?ので不参加。

問題はacm.uva.es…ではなくて、acm.timus.ruのなかの、
1003
1004
1060
1062
1090
1091
1095
の7問を3時間で。無茶な時間設定ですな。
(本来は6問だったところが不手際で7問になったということのようだけど)

解き始めはもちろんいつもどおり一問目(1003)から。
20秒ぐらい考えて、これは簡単じゃない…ということが分かったけど、
意地になってそのまま一時間ぐらい考えてしまった。
で、一時間ぐらい考えてから、"やっぱこれ難しいわ"ということで問題変更。
コード一切書かず。まったく何をやってるんだ…。

1060がぽつぽつ正解チームが出てきていたので取り掛かることに。
こりゃライツアウトですな…。ということでさらりとAccept。
このあたりでM氏が全部訳し終わってくれたので、分担してみることに。
(…分担していいのか!?いかんよなぁ…)

私は1095解くから1090解いといて。とか言いつつ1095に手をつける。
1095は与えられた数のpermutationの中で7の倍数になるものを一つ求めよ、
という問題。
7の倍数など1/7の確率で出現するんだから、適当に前から順番に調べたら
TimeLimitExceedまでには間に合うやろ。という見積もりで
作成、Submit。みごとにAccept。
(permutationが十分にたくさんあり、そのすべてが7の倍数でないような数
が存在したらまずかったけど、そういうものは無い！とこれまた適当に考えてました)

で、そろそろ1090解けてるかな〜と思ってM氏に1095解けたよ〜、
と連絡したところ、なんと向こうも1095を解いていたらしい。
どうもやり取りで意味の取り違いが発生したらしい。
…オンラインは怖い怖い。

がっくりしつつも、今度こそM氏に1090を任せて、私は1091を解きにかかる。
2<=K<=S<=50 なるK,Sに対して、K個のいずれもSを超えない相異なる数
の組のうち、最大公約数が1より大きいものはいくつあるか。
ただし、解が10000以上なら10000と答えよ。・・・という問題。

10000リミッタで自動的に探索はだいたい頭打ちになると考えて
深さ優先探索をさくさくと作成。みごとにおそい。
入力がK=25,S=49なるときには、実は解は0個なのだが、探索空間は大きい。
つまり時間がかかっているということですな。
K*2>Sの時は0にしかなりえないということに気付き、それを組み込む。
さらに、K*2>S>K*3 のときは最大公約数は2でしかありえず、
その際解の個数は2 C Sであるということに気付く。
K*3>Sのときであるが、これはもう、解が十分大きいと大胆予想。
すぐに10000リミッタに引っかかってくれるはず。
…ということで2つの特殊化を組み込み送信。Accept。

この辺で残り約20分。1090は当初思っていたよりも難しい問題だったらしく、
まだ解けておらず。よりオーダの低いアルゴリズムが必要だったのだが、
結局、解けぬまま終了。2問ぐらい考えてない…というか読んですらいないし。
驚くべきことは3問なのに2位。しかも1位とはペナルティー差。
Gokuriとかどうしたんだ〜。

そのあと、コーチ陣より問題の解説をオンラインで拝聴させていただいたのだが、
私のようなあてずっぽうじゃなかったね。
まぁ、勉強になりました。次回は2週間後ということだが、次回こそは
3本パイプラインでちゃんと勉強して1位になれるように…。
ちゅうか、2人しかおらんと、コーディング、問題解読、で人手が
ふさがってしまうので、"スタートダッシュ期間"中にXPをするのが
不可能になってしまうのに今日気付いた。やっぱり3人という数は
一台の計算機にとってベストなのかな。或いは3人用の戦法に
慣れすぎてしまったのか。