FLYING

/* TODO: 気の利いた説明を書く */

本選当日

先日のエントリにとんでもない人の☆が付いていたような気がしたけど、おそらく気の迷いだろう。うん、きっとそうに違いない。ひとまず、忘れないうちに情報オリンピックの本選に参加した感想と、出題された問題のメモを書いておきたい。支離滅裂な部分は明日直すつもり

問題1

碁石並べ」。言い換えるなら一次元変形オセロ。実装するだけならそこまで苦労はしないが、インプットのサイズがすこぶるでかいので、時間内の完答を目指すなら工夫が必要。この辺から既に今回の問題セットの難しさがうかがえる。

オレは素朴な方法で実装したため、サイズの大きい問題には対応できずタイムアウト。セミナーでの解説によれば、だいたい6割くらいは得点できるのではないか、とのこと。

問題2

「共通部分文字列」。名前だけでネタバレだが、よく言われるLCSとは共通となる条件がちょっと違う動的計画法による解法を知っていれば楽できるけど、地道にやろうとするとなかなか大変。でも、動的計画を知らなくても工夫次第で回答できる問題らしい。

オレは動的計画で回答。標準ライブラリのstrlenの動作が微妙におかしかったので、自前で実装して問題を回避した。唯一完答が狙える問題か。

問題3

「ダーツ」。なにやら条件がややこしい最大和を求める問題。何も考えずに4重ループで実装すると解答率2割くらいになるらしい。Superconの本に載っていたような前半和・後半和の考え方を用いるとうまく解けるみたい。

オレは4重ループで実装。どこで枝狩りすればいいのか悩んでいたが、そもそも枝狩りする問題ではなかった。

問題4

「ぴょんぴょん川渡り」。今回の問題セットの中では一番条件がややこしい問題。一見すると手を付ける気になれない問題だが、頑張れば深さ優先探索でとりあえず解を求めることができる。そこからいかに計算量を減らすかが問題で、模範解答によるとメモ化再帰を使うのがいいらしい。

見た目で圧倒され、この問題には手を付けられず。再帰って奥が深い。

問題5

「ペンキの色」。パソコン甲子園で出てきたような塗りつぶし問題。ただし、問題サイズの上限が100万×100万というとんでもない数字だった。チュータ曰く「とっつきやすいが、完答が一番難しい問題」。解説では座標圧縮というキーワードが登場。説明聞いても理解できなかったから、あとでプレゼンの画像見ながら考えてみるつもり。

オレはとりあえず問題サイズを1000×1000までに限定し、単純な再帰で塗りつぶす方法をとった。解答率は3割くらいだろうか。

全体を通して

プラクティスでは入出力の方法が分からず、スタッフさんに質問しながら30分かかってようやくファイルから入出力することを理解。正直かなり恥ずかしかったけど、C++をかじっていたおかげで、標準入出力とほとんど変わらない方法でプログラムを書けた。果たして数ヶ月前のC言語しか知らない自分ならどうなっていたことやら。STLの威力をまじまじと思い知った。

それぞれの問題の解答率を合計してみると、正解できたのは多くても5問中2問相当=40点くらいと予想。つまり、合宿参加はまず無理だろうという結論に至った。取れなかったものはしょうがないので、合宿組の皆さんを片隅から応援することにする。ありがとうJOI、さようならJOI。

雑感

ひとつの目的だったid:lonlon2007との会話はなんとか達成。すげー些細なことだけど、オレなりによく頑張ったと思う。驚いたことに、会場の席はlonlon2007のちょうど隣だった。もしあの席順でなければ、オレは彼に話しかけられなかったかもしれない。情報オリンピックすげえ。

本選は訳の分からない問題だらけだったので、夕食後のセミナーの存在は非常にありがたかった。エレガントな解答とはあーゆーものを指すんだろう。というか、epoch@まつやまで優勝した大学生の人がスタッフとして解説をしていて驚いた。オレはあんな凄い人と戦っていたのか・・・そりゃ勝てないよ。

懇談会は和気藹々とした雰囲気で進行。あまりに凡庸な自分の自己紹介に少しブルーな気持ちになったりもしたが、epoch@まつやまに比べて話しやすい雰囲気で助かった。lonlon2007や同じ学校のヤツがいたおかげもあるが、昨年秋のオレから少しは進歩したらしい。このまま非コミュを克服できたらいいんだけど。

何よりも悔しかったのは、会場に宿泊できなかったこと。今頃泊まり組はどんな素敵な話をしているんだろうかと考えると、胸が掻き毟られるような思いがする。出会ったばかりだろうがなんだろうが、一緒に泊まるとなれば嫌でもテンションが上がるもんね。もしかしたらまた、『ねみんぐ』みたいなプロジェクトの芽が出つつあるのかもしれない。