ご存じでない方はひとまずこちらを参照。
国内予選はこちらを参照。
今回いろいろとケチりすぎだと思った。 交通費とか土産とか宿泊施設とか。 まぁ、もう、どうでもいいけど。 せめて愛媛なんだからポンジュースは出して欲しかったぞ。
勝ちました。上海に行けるようです。
順位は全体で2位でした。1位は上海交通大学(?)のSpiritというチームで 9問中8問も解いていました(恐ろしいチームです)。うちは9問中7問で2位、 これでも会心の出来でした。ただ、1位のチームはすでに他の大会で決勝進出を決めているらしいので 実質?我々が1位になるらしいのですが、もらった賞状は2nd place。 順位のページでも2位ということに。 同じくオープン参加扱いのGokuri-Squeezeは順位が出てないのに Spiritは堂々の1位で微妙に悲しいです。外国チームはオープン参加にならないのだろうか？ …とはいえ勝てなかったのは事実なのですが。
うちのチームは一昨年は弱小だったし、去年も国内予選は突破したものの ぱっとしない成績だったし、今年は国内予選の成績はこれまでに比べれば遥かに良かったものの 他の強豪チームと渡り合える力があったとは正直そんなに思ってなかったです。 9月頃に東京にお呼ばれして練習合宿に行ったときも 平均4位とか、そんなに際立った記録を残したわけではなかったので 正直そんなに期待もされていなかったんではないでしょうか。 当の本人もまさか勝てるとは(3割ほどしか…3割はGokuriと戦わずに済んだ分) 思ってませんでした。
しかしまぁ、今回色々と私のほうで事務処理が滞ってしまって いろいろなところにご迷惑を掛けてしまいました。 このあたりの "日本の地区予選大会における、日本チームの優勝"という目標に対して、 すでに勝ってるSpirit以外には勝てたので一応せめてもの恩返しが出来たでしょうか？ ………駄目ですか。そうですか。この雪辱は世界大会で晴らすぞ！(とか言ってみる)
当日取った戦略など。 完全分業制シリアルプログラミング。 私 → コード書き、 K氏 → ナビゲーター(…というのか？)、 M氏 → 問題解読(&幾何要員) てな役割分担で最初から最後まで通した。 具体的には、最初に私が雑務をこなしつつM氏が問題を読む。 大体両方が同じぐらいに終わると思うので、その時点で解釈完了した問題を私のほうに まわしてもらいながらコーディングと残りの問題解釈を並行してやっていくというような感じ。 最初から最後までこれで通せたということは途中一回も詰まらない ということなので(詰まると役割が微妙に入れ替わって他の問題を解き始めたりする) その時点で相当調子が良かったということになるだろうか。 あ、あと、補助的な作戦としてはGokuri追従作戦。 Gokuriには勝つ必要が無いのでGokuriが解いた問題を優先的に解いていくという… (だめやん…)
今回は9問で5時間。予選とは違い日本語は無し。 難易度は、 A(割と易しい)、B(易しい)、C(割と易しい)、D(やや面倒)、E(普通)、 F(めんどくさい)、G(やや難)、H(やや難)、I(難しい) ぐらいか。 A〜Eはすべて解きたい。F〜Iはそれなりに大変だがI以外は 解決不能なほど難しい問題ではない。ここをいくつ解けるかが一つのポイントだろうか。 I問題は未だにアルゴリズムが分からず。 今回はE問題以外は計算量が問題になるようなものは無かった。
当日作ったソース。
FとI以外はAcceptしたので正しい。
FとIは手をつけてないのでテンプレートのまま。
全体的に予選のときよりもソースが長い。
特に冗長に書いてしまったということも無いはずなので、
今回の問題は全体的にコード量を必要とするものだったようだ。
ソースは途中で書くのをやめたところなどがそのままになっていたりするので
明らかに変な部分もあるが、せっかくなのでそのままにしておく。
Iは解き方をまだ考えていないが、Fはそのうち実装しようと思う。
(追記 12/9：FとIを解いたのでソースを掲載。愛媛大会のページに
入出力データが公開されているので、ちゃんと正しいことを検証している。
問題Fは普通に深さ優先探索。探索空間は非常に狭いのでこれでOK。
実装してみると思ったよりも手間がかからなかった。
問題Iは立体を少し膨らませたときの増加面積より算出できるらしい。)
行数など。参考までに。
$ wc *.cpp
80 124 1395 a.cpp
97 173 1504 b.cpp
52 88 871 c.cpp
118 178 2120 d.cpp
106 167 1745 e.cpp
9 15 108 f.cpp
135 290 2761 g.cpp
132 241 2813 h.cpp
9 15 108 i.cpp
738 1291 13425 total
せっかくなので、当時の様子を仔細に思い出しながら書いてみる。
まず、開始直後。最初にやらなければならないいろいろなことを片付けにかかる。 具体的には、
キーバインドの変更は前日にクラリフィケーション(質問みたいなもの)で 可能かどうか問い合わせて、可能であるとの返事をもらったので堂々と変更する。 (ちなみに変更できるということはコーチに聞きました。ありがとうございます) 変更内容は目の上のたんこぶ、Caps Lockを殺してCtrlにすること。 CtrlとCaps Lockが両方Ctrlになるといつも色々なキーボードで練習している私にとっては 非常に助かる。Caps Lockは本当にイランキーだ。 間違って押しちゃうと大変なことになるし。せめてシフトを押さないと発動しないようにして欲しい。
ソースファイルのテンプレートは
#include <iostream>
#include <fstream>
using namespace std;
int main()
{
ifstream cin("");
return 0;
}
こんな感じのを作った。
ファイルからの入力の時はいつもcinをスコープで隠すようにしている。
どうせmain以外からは入力しないし。
includeファイルは臨機応変に追加する派。
なんか要らんもんがごちゃごちゃ付いてると気持ちが悪いように感じる。
サンプルインプットの取得、は文字通り。 とある場所にアップロードされるのでそれをブラウザで引っこ抜いてくる。
このあたりで開始5分ぐらい。結構綿密に計画を立てたのに意外と時間がかかった感じだろうか。 この辺でM氏がだいたい問題Aの解読を終えてくれているので説明を聞く。 …。今回は問題Aがいつもより難しいことを即座に理解する。 だっていつもは問題Aは考える余地すらない問題がでるんだもん。 今回の問題Aは二種類のおもりで特定の重さを量るという問題。 そのときの必要なおもりの数の最小値を求めよと。 正直アルゴリズムが全然浮かびませんでした。 5分ぐらい考えれば何とか成るかな?ということでK氏と一緒に考え始める。 M氏には継続して他の問題を解読してもらう。 私が、整数論の問題やで、これ。とか言いながらぐちゃぐちゃ式を変形させ始めるも、 つかみ所が無い泥沼模様に。 そうこうしているうちにK氏が左右に載せるおもりを 重さの差を見ながら増やしていけば良いのではないかと思いつく。 ちょっと考えて正しそうな感じがしたので実装してみることに。 実装自体はいたって簡単なのでさくっと実装すると何問かサンプルが合わない。 二種類のおもりを同じ方に載せるケースを考慮していなかった。 同じほうに載せる場合は、最初に片方のおもりを載せられるだけ載せて、 残りの重さがもう片方のおもりの倍数になるように最初に載せたおもりを減らしながら 探していく、という方法を取ることにした。 で、これもさっくりと実装。しかしなんとまだ答えが合わない。 負の数とかが表示される。負の数…？とちょっと困惑するも考えられるケースは 二つ目に実装した減らしながら…という部分しかない。 そういうわけでそっちで負の数が発生した場合をはじくようにしてようやくサンプルが通る。 なんか怪しいプログラムだな…大丈夫か、と思いつつSubmit。Yesが来た。 この時点で35分ぐらい経過。風船はすでに5個以上上がっていたような気がする。 息つくまもなく次の問題へ。
次の問題をどれにするか考えようとしたとき、 GokuriチームがC問題を解いていることを発見した。 他のチームが皆Aしかといてない中、GokuriはいきなりC問題である。 Gokuriが30分でCを解いたんならうちらにも解けない問題なはずが無い！ ということで次はCを解くことに。 C問題は任意の32ビット整数、a,b,c,d,e,f,g,h,kに対して a^k b^k c^k d^k e^k f^k g^k h^k および (a+b+c+d+e+f+g+h)^k が与えられたとき、kを求めよ、という問題(^は階乗ではなくてxor)。 これもうんうん考えているとM氏が最下位ビットの足し算が合うか合わないかで kの最下位ビットが分かる。ということを発見した。 それを元に私が一般の桁数について繰り上がりを考慮して式を導出。 M氏は問題解読に戻ってもらう。 いろいろと考えるのはややこしかったけど、コード自体はえらく簡潔に書けた。 とりあえず一回目の実行では最上位ビットが立ってたとき答えが おかしくなっていたので、そこをちょちょいと直してSubmit。 普通にYesが返ってきた。この時点でおよそ1時間10分。
M氏が結構問題を解読してくれていたので易しそうな問題を見繕ってもらった。 問題Bはゲームの勝敗を決定する問題でめんどくさそう(この時点では探索問題と勘違いしてはります) ということだったので、問題Eを解くことに。 問題Eは2つのログインネームが似ているかどうかを判定する問題。 具体的には、一文字削除、追加、変更、スワップなどによる操作n回(n<=2)で 一致させることが出来るかという問題である。 ザックリな計算で一ステップ500通りの文字列が生成できるので 操作回数がもっと多ければ非常に困った問題になるのだが、 ここは2回以下というのでわりあい簡単に実装できる。 後に聞いたところによるとこの問題は有名なDP問題らしいのだが、 物を覚えない人間である私はそんなこと知らないし、 情報学が専門ではないでないM氏とK氏にそんなのを要求するのも酷というものなので、 結局この場ではアドホックに解法を考えることになった。 この問題は普通にやろうとすると、 まず元の文字列に対して操作二回以内で到達できる文字列のセットを生成して そのセットに調べたい文字列が入っているかを調べることになると思うが、 最大250000個ぐらいの文字列が生成されるようだし、 それを問題のサイズが文字列100個程度なので100回行うことも それを保持しておくメモリも若干厳しそうである。 うーん…と考えていると、K氏がよさそうな案をひらめいてくれた。 片側から操作2回で到達できるものを保持するのではなくて、 両側から操作1回で到達できるものを計算して、 それの間にインターセクションがあるかどうかを調べれば良いと。 これは探索では割とポピュラーな解法であるが、今回の問題も大幅に探索が 減少するのである。ソートされた集合のインターセクションを取るのはO(n)なので、 計算量はほとんど500*2個程度の文字列を比較するだけである。 これもアルゴリズムが分かれば実装は簡単である(操作が色々あるので面倒だけどね…)。 普通に実装してサンプルが正解したのでSubmit。 …が、ここで今回はじめてのWrong Answer。 サンプルが合ってるので非常に困ったが、 とりあえず文字列操作部分をユニットテストすることにした。 4つの操作を施した後の文字列を表示させながらチェックしたところ、 その1つに非常に初歩的な誤りが発見される。 おかしなところが分かればささっと修正してSubmit。 Yesが返ってきたので次の問題へ。 この時点で開始1時間半過ぎだっただろうか。
次に解いた問題は問題B。M氏が超簡単問題であることを見抜いてくれました…。 ゲームのシミュレーションと勝敗判定だけ。どっちも非常に易しい。 さくさくと実装。実装している途中で6重ループとかが出てきて頭が混乱しつつも 結構すぐに完成。しかし実行するもなかなかSampleがあわない。 K氏と二人がかりでチェックしているとポカミスを2箇所ほど発見。 (この辺から私の頭が錯乱状態になっていたかもしれない…) 修正するとSampleが通ったのでSubmit。Yesが来て次の問題。 この辺で2時間過ぎ。
次に何解こうかなと周りを見渡すと、うちのチームがかなり上位にいることに気付く。 K氏が眠い眠いを連発しはじめていたが、上海がかかっているので頑張ってくれ、と激励。 M氏が全部の問題を読み終わっていたので、残りの問題を聞く。 問題F〜Iはむずかしいっぽい、…が、いろいろじっくり聞いてみると問題Hは解けそうな感じ。 問題Hは空間上に点在する球をスライスしたときの球の外形の個数の増減を求めよ(…なんか表現が おかしいかも。問題文の方を参照してください) アルゴリズム的には、球の交点(交円？)のZ座標の上下と球の上下のZ座標をセットに突っ込んで 下からスキャンして各区間の中間地でスライスして、 そこに乗った円をunion-findで互いに引っ付いていないものの個数を計算。 隣り合う値が違えば増減を出力する、みたいな感じでいけそう。 …なのだが、この問題この時点ではどこも解いていなかったので微妙に不安だった。 とりあえず、いけるという確信のもと実装することに。 球の交点のZ座標はM氏に計算してもらい、 そのあいだ、私は球の交点が必要ない部分をゴリゴリと実装。 これ、実装してみるとアルゴリズム自体は結構明快なのに、 今回のこれまでで一番作業量が多かった。 まず、union-find、円と平面の交点、スキャンしつつ値の増減を求めたり、 色々書かなければならないことが多い多い。しかも私の頭が錯乱してるもんだから、 (pair<double,duble> と書きたいところを vector<string,string> とか書いてしまったり、 もはや意味が分からない。ナビゲーターのK氏には迷惑を掛けました) これ書くだけでたっぷり30分以上かかってしまったと思う。 何とか書き終わってここで私は小休止。頭がやばいのでチョコレートとか食べに休憩室へ。 返ってきてM氏が球の交点を打ち込んでくれるのを待って実行。 細かいバグがいくつかでたけど、どれもすぐに直せてSubmit。 一発でYesが来た。全チーム中始めての問題H正解ではしゃいでしまう。 この辺で国内暫定トップっぽい感じ？ あまりのことにM氏が問題Hの白風船をみて「連邦の白いモビルスーツは化け物か」 とか言い出したりした。化けるようにがんばってくれよ、と。 おそらくこの辺で3時間過ぎ。残り2時間弱だったと思う。
ここまで来ると回りが気になる気になる。 Spiritがすでに6問といててうわあ、とおもいつつ海外だからよし、とか。 国内では依然トップだっただろうか。風船上がらんといてくれと祈るばかり。 次に解くのはHの後に取っておいた問題D。 与えられた2つのURLが存在する同一のファイルを指すのか？という問題。 問題自体は簡単だけど条件が煩雑だし、条件の見落とし等がとても怖い問題。 これを解いている途中確かholizonだったかどこかが5問で並んだけど、 うちはHを含んで5問なんだし、Dが解けるから6問は堅い、堅い……と うわごとのようにつぶやきながら問題Dを処理。 アルゴリズムは、まず与えられた存在するファイルをファイル名のセットに突っ込んで、 さらにそのファイル名をスキャンして存在するディレクトリをディレクトリ名のセットに突っ込む。 ファイルの比較はまずファイルの記法の正規形を求めて(途中ディレクトリの存在判定も行う)、 それぞれの正規形が指すものが同じかどうかを判定。 …というもの。 これまたいまだに錯乱する頭でえっちらおっちらコーディング。 ちょっと休んだほうがいいんじゃないか、とK氏に言われるも 上海上海とうめきながら無理やり続投。 多分30分ぐらいで完成。 ちょこちょこ修正してSampleを通してSubmitするも今回2回目の Wrong Answerをもらう。ええっ？あってるやん〜。とか思いながら いろいろユニットテスト。それでもバグは見つからず、 ここでこの日最大のはまりに。全然分からないので途中でチョコレート食べたりお茶飲んだり。 ケースセンシティブですか？とか、 一つのURLが二つのファイルをさす可能性がありますか？とか クラリフィケーションを送りつつ、いろいろデータを出力して調べてみる。 正規形が間違ってるのかなぁとそこを出力してみると ファイル名の最後に ".." とか "." が入っている場合の処理がおかしいことに気付く。 普通 .. の後ろには/付けるだろ、と思いながらその部分の記述をM氏に読み直してもらって修正。 Submitしつつ、トイレに行く。もう怖くて見てらんない。 帰ってきても風船が来てないので、駄目だったか、と思ったらYesは来てたとのこと。良かった。 この時点で4時間前後。残り一時間ちょっとあったかな?
もう私は疲労困憊。周りのチームの動向ばかり気にしていた。 日本チームでは単独6問正解だったのでなんとか他のチームは解いてくれるなよと祈るばかり。 残りの問題はどれも大変そう。 問題Iは論外だし、問題Fはさいころ。探索空間が小さいのはほとんど自明だけど、 さいころの処理を書いてると一時間ぐらいでは間に合わないような気がした。 問題Gは4色問題のバリアント。国が飛び地を持っている場合の塗りわけ。 一般のグラフ塗り分け問題になるはずなのでNP完全問題なんじゃ? と思ってサイズを見ると100まで。こんなんいけるはずないなぁ とは思うものの、4チームぐらい解いてるところがあったので、やっぱりいけるのかな？ ということで、これを解くことに。 アルゴリズムの方針としては、地図→グラフ変換、それから探索。。 探索が絶対間に合わなそうだからやる気が出ない。仮にDPだとしてもアルゴリズムが浮かばん… とぼやいていたら、M氏がキーボードを奪いゴリゴリと地図→グラフ変換を書き始める。 どうせ無理だろうなぁ…と思いつつ眺めていると残り15分ぐらいで変換部分が完成した。 今から書いても間にあわんよなぁ…と思いながらも キーボードを渡されたので投げやりにコードを書き始める。 めちゃくちゃ適当に全探索なコードを書いてたら残り数分で完成した。 コンパイルして実行したらサンプルに対して答えが正しく出た。 よし、行け！ってな感じで急かされながらSubmitすることに。 残り時間<1minと表示されているところをSubmit。 なんとか間に合ったらしい。 絶対TLEになるだろうなぁと思っていたら、なんとYesが帰ってきた。 これにはさすがに私もびっくりだった。というか、3人ともびっくりだった。 M氏は、ほら、いけたやん。とか言ってたけど、私はどうにも釈然としなかった。 とはいえ、これで7問正解。周りを見渡す限りではSpiritに次ぐ成績だった。
その後で…。
問題Gを解いた方なら分かると思うが、上のコードがTLEしなかったのは 全く自然なことだったようだ。 なんと、独立な国は10個しかないという条件を読み落としていたらしい。 英語が読めない私が悪いんだけど、M氏にはもうちょっと気をつけて条件を 読み落とさないようにして欲しいところだ。 多分10個と分かっていれば私ももっとやる気が出ていたと思う。 まぁ、でもそれでもぎりぎり解けたし、良かったといえば良かった。 もっとやる気があったとしても問題Fが解けるほどに時間が余ることは無かったと思うので。
コンテストが終わって、コーチや東京での練習会のとき来ておられた 他のチームのコーチの皆さん、それから他のチームの皆さんにも祝福を受けました。 時間中一度もスコアボードを見なかったので、ここでようやく、 ああ、勝ったんだなぁという実感が沸いてきました。 最後の最後でうちのチームが7問になったときはコーチ室で 歓声が上がったとか聞きました。残念ながらこっちのほうまでは聞こえてませんでしたけど…。 京大が勝ったのは4年ぶりだか5年ぶりだかだそうです。 (…ごめんなさい、私が今まで駄目駄目だったせいですわ) ともかく、京大の復権ということだそうで。 しかし、勝って終わると気分が全然違うもんですね。周りの空気も全然違う。 上海を決めて松山城観光にいけてよかった。 その後のセレモニーでもいろんな人が話しかけてきてくれました。 良い機会なのでHaskellの布教活動もしました。 しかし、思ったよりも皆さんHaskellのことをご存知でした。 やっぱり強豪チームともなると違いますね。
とにかく、これまで色々ありましたけど、苦労が全て報われたような感じです。 応援してくれた全ての人へ、ありがとう。