コンテストを勝ち抜くために必要だと思われるもの
・今回の合宿で
2/24〜27日に合宿があったのだが、
その際にどういう心積もりで望むかというのが内心テーマだった。
経験の少ないチームだと、このような集まって問題セットを解くという経験だけでも
非常に刺激になって、絶大な効果が期待されるのだが、
うちのチームはおそらくこういう問題をもう解き慣れているし、
5時間で8〜10問のセットを解くと言うのも幾度となく経験しているので、
もはやそれだけでは効果薄だと感じているところだった。
それでも合宿というのは貴重な機会だし、
それに、私個人としてもうちのチームとしてもここ数ヶ月は
ろくに練習ができていないので、ここで何かを掴んでおきたかった。
ただ漫然と問題を解くだけではいけないだろう。
というのも、単にこなした問題数と実力との間には
そこまで相関があるようには思えないからで、
実際のところ、問題数だけ見るともっと強くてもよかったチームとか、
そんなに問題数を解いていないのにすごく強かったチームとか、
そのあたりが実証している。
何かを意図を持って問題に取り組み、
確実に自分を変えていかないといけない。
そういうわけで、今回私は一応ある意図をして問題を解いていて、
さらにそれがある程度思惑通りに進んだ。
他のチームの人がみんな私のようなタイプでは無いとは思うが、
ここで後継の人たちのために私の意見を書いてみようと思う。
- 無知識主義
「私は無知だが、自分が無知であることを知っている」
唐突だが、私は勉強熱心な方ではない。
アルゴリズムだって人一倍勉強していないし、
私が知っていることはおそらく大体の人が知っていることに過ぎないはずだ。
むしろ他の人が知っていることの多くを知らないと思う。
そんなことは無論承知済みである。
去年の時点でそれまで完全に独学でやってきた知識を
一応基本を勉強してそれなりに穴は埋めたはずだが、
そんなので十分なはずが無い。
というか、アルゴリズムなんてものはそれこそ数限りなくあるわけで、
全てを勉強するなんてことは不可能なのだ。
GNCの人などはなるべくたくさんのアルゴリズムを習得して、
カバーできる範囲を広げることが重要だと考えておられるようだが、
これがなんというか、私の経験によると、外される時は外される、なのだ。
特に某リージョンなど知識重視の問題を出して来て、
それはおそらく日本において普通教えられているアルゴリズムから
相当剥離してしまっているように思う。
どうせ外されるのなら、そこまで知識を重視しなくても
良いのではないかというのが私の意見だ。
いや、それでも知識が重要だというのには私も異論は無い。
そうではなくて、少なくとも知識を拠り所とするようなことはしたくないということだ。
当然知っておくべき知識は勉強する。
でも、終わった後で、「こんなん知らんがな！」となりそうな
アルゴリズムまでは無理して勉強する必要は無いのかなと思う。
アルゴリズム学習というのはかなり大変だということに加え
(特に私なんかはものを覚えるのが苦手なので…)
知識は時に発想の障壁になり得ることにも留意しなければならない。
- ひらめき重視
では、知っていれば解ける問題をみすみす捨てるのか？
これはどちらかといえばYesだ。
そんなことでいいのか？これがある程度許されると思っている。
というのも解けない問題というのは知らなくて解けない問題だけでなくて、
思いつくことができなくて解けない問題もあるはずで、
というか、むしろそういう問題の方が往々にして多いわけであるので、
そういう問題を徹底的に排除することが最重要なのではないかと考える。
つまり、終わった後で、「ああーっ！」とかそういう問題があってはいけないのだ。
そういう問題は何も知らなくても解ける問題なんだから。
ひらめきというのは時の運ではない。
これは確実に鍛えることができる。
具体的な方法を述べるのはなかなか難しいが、要するに頭のやわらかさで、
物事をいかに多角的に見ることができるかなのだ。
個人的な意見であるが、これはひらめくという行為を繰り返すことにより
徐々にそのような能力が伸びていくのではないかと思う。
ひらめく能力というのはあるドメインに特化した能力ではないし、
基本的に簡単な問題を含め全ての問題に影響を及ぼす。
簡単な問題の解を発見する時間の短縮、さらに解ける問題数が底上げされ、
もしかしたら知識を前提とする問題について別解を見つけることもできるかもしれない。
鍛える具体的な方法は難しいと書いたが、
今年のImagineCupのアルゴリズム部門の課題なんかはまさにうってつけかもしれない。
解のルートを見つけるのに相当頭を使わなければいけないので、
とても頭を鍛えることができる。
ICPCにおいてはアルゴリズムばかりが取りざたされるが、
実のところヒューリスティックが使えるケースがしばしばある。
そういうケースでは積極的にヒューリスティックを使っていくべきだ。
将棋にも詰みより必至という言葉があるように、
どうせ解けるのなら簡単な方を選ぶべきである。
ヒューリスティックで問題を解くといっても、
闇雲に適当な処理を並べたら良い訳ではない。
ちゃんと解けるめどの立つ方法を考えなければならない。
この辺の感覚は微妙で、質の良いヒューリスティックを生み出そうと思うと
ある種の経験と勘がものを言う。
この感覚は実際にいくつかの問題をヒューリスティックで通して感覚を磨くしかないのだが、
ヒューリスティック初心者には、とりあえずプログラムプロムナードの
2002年9月号 「点の集合を包含する球」
2002年12月号 「三角形の分割」
あたりを読まれることをお勧めする。
・実際の合宿の成果
ここを参照。
一回目
問題A：問題なく解法を思いつく
問題B：二部グラフになることに気付かず。でも、気付いてもそれから使うアルゴリズム知らなかったしいいか…
問題C：ごり押し問題なので普通に解ける
問題D：解法をちゃんと構築できる
問題E：ヒューリスティックで解く。想定解は線形計画法。
線形計画法なんかそらで書くことは不可能だし、こんなものここで書けなくても良かろう…。
構築したヒューリスティックは線形計画法と大体等価という話もあったが、
ここではアルゴリズムも考え方もコードも超単純で、
難しいことなんか何も考えていないことが重要だろう。
問題F：時間が無くて解けず
問題G：問題なく解法を思いつく
問題H：幾何的解法をとる。想定解は連立方程式を解く方法。
掃き出し法なんか難しくないと言われてしまったが、
一次一変数の方程式を解くほうが簡単なのは明白なわけで…。
なお、この解法も連立方程式と等価という話になったが、
やはり難しいことを何も考えていないのと
コードが超単純になっているのが重要。
問題I：時間が無くて解けず
二回目
問題A：問題なく解法を思いつく。必要知識、ダイクストラ
問題B：想定解よりオーダの低い解法を思いつく
問題C：ヒューリスティックで解く。想定解は空間を分割する方法。
想定解は思いついて実装できても良かったが、
質の良いヒューリスティックが実現できて通ったので問題なかろう。
問題D：解法が全く思いつかず。
問題E：適切なアルゴリズムを知らずに変なことをした。
想定アルゴリズムはSuffix Array。
しかし、もっと別のアルゴリズムでも通る。
問題F：問題自体が分からず
問題G：解法は分かったものの、誤差の取り扱いを間違ってWA連発。ダイクストラ
問題H：解法を思いつくことができた。日本チーム唯一。
問題I：問題なく解法を思いつく。
問題J：問題なく解法を思いつく。
さて、このような結果になったのだが、
これを見てもらえるといかに発想力が重要なのかが分かるだろう。
今回うちのチームはダイクストラぐらいしか知識を使っていない。
全体としては割と良好な結果で、まともに考えて解法が思いつけなかったのが
二日目の問題Dぐらいだった。
これでまだ速度面の問題や二日目の問題Dなど伸びしろがあるので、
知識を増強させる前にまだやることがあるのではないかと思う。
・その他
今回は中国チームも何チームか招待してコンテストを行っていたのだが、
その中でもやはりNimrodは強い。ここの強さは本物だ。
現時点でうちのチームより一回りか二回りは強い。
東京大会の時も同じような印象だったし、
正直今から一ヶ月では勝てるようになれないような気がする。
でも、他の中国チームには勝てないことはないと思う。
知識でで負けていても、発想が生かせるケースとなると、
そこまでこちらに不利なわけでもない。
あとは世界大会が知識重視ではなければ…。
