マラソンの感想
Competitive Programming Advent Calendar 2014の記事です。
自分はかつてTopCoder Marathon Matchに参加していた時期があったのですが、今回はその感想を書きます。
手を出すまでと手を出してみての印象
やるからには誠意を持って取り組むつもりでいました。
実際にマラソンをやってみるまでもなく私は自身の武器を自覚していました。それは時間を大量に溶かす覚悟です。時間というのは実に使い勝手の良いリソースで、これを大量に保有していると戦略の幅が広がります。具体的な使い方としては、複数の解法を入力のパラメータに応じて変化させるとか、パラメータ調整を入力に応じて複数用意するとか、こういったことで上位との差を少しでも埋められるのではないかと考えていました。パラメータ調整を細かく分けてやるのは実際にずっとやっていて、効果はあったのかなあ。
マラソンに参加してみようかな、と少しでも思ってからやったことは先人の参加記を読むことでした。ですが大抵の参加記は各問題固有のドメインについての記述が多く、欲しかった汎用的な知識はあまり得られませんでした。確認できたのは「早すぎる最適化は悪」という有名なフレーズはマラソンにおいてもやはり正しいらしいということくらいです。後は機械学習のような、ハードルの高い硬い数学はそんなに使わないらしくちょっとした安心も得ることができました。
実際にマラソンをやってみて初めて気づいたこと感じたことがいくつもあります。
初めて参加したマラソンで結果が返ってきて、人間的な発想とちまちました本質的でなさそうな部分の改善だけでも時間をかければ案外戦えるんだなあ、という感触がありました。もっとスマートな感じでこれぞブレイクスルーという壁を理論パワーで乗り越え、最後の最後に細かい職人的な最適化で差をつけるという展開を予想していたのでなんだか意外でした。最初のマラソンでは赤コーダー不在だったのでそのせいだろうと思っていたんですが、赤コーダーが参加するマラソンでも違いはなくて、思ったよりも地味なんだなあと。
次に、乱数やメタヒューリスティックは魔法の道具ではないということです。私は確率的な手法やらメタヒューリスティックやらに21世紀っぽいカッコよさを感じて、その効果に大層な期待をしていました。ワクワクしていました。そして初参加のマラソンで使ったのは多スタート法という非常に単純なものですが、その効果たるや非常に微々たるものでした。当時は感覚が未発達だったのでそれが受け入れ難く、裏切られたような、白けた気分になってしまったことを覚えています。
潜伏やら順位表から得られる情報など、問題そのものからは少し外れたメタな部分についても参加前と参加後でギャップがありました。他の参加者なんて目もくれず、ひたすら問題と1対1で向き合う求道者スタイルは実に王道的でカッコいいと思うのですが、自分にそんな横綱相撲がとれるはずもありません。相対スコアのときに他人の点数が削れるか、とかキューに張り付いて上位陣のプログラムの実行時間を監視するとか、そういうセコイところでちまちま稼ぐのはむしろ楽しそうだと思っていました。実際にやってみると確かに有用な情報も得られるけどそんなに頑張ってやるほどのことでもないね、という感想を持ちました。得られる情報はしょぼい上に確信が持てるようなことでもなかったので。これもまた、白けた気分にさせられました。やめなかったけど。
そしてマラソンは赤コーダーとか上位陣の強さが分かりづらいです。単に順位表や過去の記録といった結果だけを見て「赤コーダーはいつでも強いなあ」とかそういうのはもちろん分かるのですが、どう強いのかは実感しづらいのです。マラソンマッチで1位の人の方針などを聞いて、「その発想はなかった」となることはそんなに多くなく「自分と方針は似てるのにどこで差がついたんだ？」とか「たったそれだけでこんなに差がつくのか」と感じることの方が多かったです。他人のマラソンのコードを読んで理解しようとするのはコストが高いし、コード読んだだけでは分からない強さだっていくらでもあります。
パラメータ調整についても触れておきましょう。実際にマラソンを始めるまではこう考えていました。「パラメータ調整とは後回しにできる、あるいは後回しにすべき本質的でないものだ」と。でも実際はそれほど単純なものでもなかったのです。普通にマラソンをやっていると、スコアの上昇が頭打ちになって新しい手法を採用せざるを得なくなります。新しい手法、というのはちょっと大げさな表現で実際は新しい着眼点、くらいのものだったりします。無料の昼食なんてすぐになくなってしまうので、大抵の場合新しい手法というものは旧い手法と比べて長所と短所を両方持っています。そして長所が短所を上回るかどうかは往々にして判断が難しかったりします。さて、新しい手法を試してスコアが上がるかどうか確認してみましょう。ここでスコアが上がっていたら万々歳ですが、そうでなかったとき我々は適切に判断しなければなりません。「新しい手法そのものが駄目だったのか？それともパラメータが悪かっただけなのか？」。何故駄目だったのか？より先に本当に駄目だったのか？をはっきりさせないといけません。高い実力があれば、あるいは実装すら省いて考察のみによって手法の善悪を判断できるのかもしれません。しかし自分にとってそれはリスクの高い行為でした。自分はリスクを回避する一つの手段として新しい手法でもパラメータ調整をちゃんとすることにしました。最終的に採用するかどうかわからない手法なのにパラメータ調整という面倒な作業は省略できないのです。省略できるのはもう本当にどうしようもないくらい駄目だったときだけでやっぱり嬉しくありません。
私にとってのマラソンの面倒臭さはこの周辺に集約されます。提案手法の効果を確認する作業は沼の中でもがいているようでそれなりに辛い。もちろん、「これはスコアが上がるに違いない」と確信しているときは特に面倒でもなくむしろワクワクします。ただしそういうレベルの新手法が出てくるのは大抵序中盤で、だからマラソンは序中盤のスコアが伸びやすい時期が特に楽しいのでしょう。終盤になるとスコアが上がるかどうか分からない、とか多分スコア落ちるだろうなという手法も試すことがあります。辛い。こういうダメ元の手法でも試してみると稀にスコアが上がってしまうのだから性質が悪い。やる気ポインツの残量が少ないと、「この手法でスコア上がる確率は直感で20%くらい(高い！)かな？」というのでも実装量との兼ね合いによっては面倒でスルーしてしまいます。誠意はどこへ行ったのでしょう。それもこれも長所と短所の比較の難しさのせいです。本当にどうしようもありません。
思いついた手法を試すことよりも手法を考えること、および手法を考えるための調査の方が面倒だという人もきっといることだと思いますが、私の場合そこまで苦に感じていなかったような気がしています。だって、妄想したりスコアが上がる夢を見ることはワクワクしますからね！
最後に。マラソンの楽しさについては、勝つことが大部分を占めています。勝ちの定義はコンテスト毎に自分に都合良いよう変わりますが、適切な競争相手がいて自分のスコアが上回って、というのが基本です。問題そのものの面白さというのはそりゃ大事ですがあくまでサブです。問題の本質を解き明かしてそれに触れられれば満足、なんて高尚な楽しみ方ができる人間ではないので。争う相手あってこそのマラソンです。
TCO関連
マラソンにも大分慣れたころ、TCO 2011の予選が始まりました。ところでTCO Marathonの予選形式は2012年から変更されました。選抜方法としては現行方式が優れていると思います。以前の形式はとにかくround3の一本勝負という側面が強く、またマラソン3セットというのは重いので、(潜在的に)強い人も面倒がって参加してくれないかもしれないからです。ただ、それでも自分は以前の形式の方が好きでした。以前の形式の何がよかったのか、それはround3で強い人達がほぼ全員揃って本気を出してくれるということです。旧形式のround3こそがマラソンで開催される年内最大のお祭りだと思っていました。Finalは参加人数が少ない上に短時間すぎて正直なところあれをマラソンとは認めたくありません。
TCOの予選は参加者が多く、感想戦とかTwitterで眺めたり、参加記読むのがとても楽しかったです。このときほどマラソンに参加する日本人が多くてよかったと感じるときはありません。
さて幸運にも私は予選を通過してFinalに出場することができました。ちょっと自意識過剰でキモいですが、私がTCOに出たことで「komiyaが出られるくらいなんだからTCOって案外身近なのでは？マラソンって穴場なのでは？」と思った競技プログラマが少なからずいたのではないかと密かに思っています。そうだといいな。それはともかく、Finalでは惨敗しました。これがAlgorithm系コンテストなら0完座るだけに匹敵する無様な負け方でした。コンテストが終了する頃にはオンサイトに呼んでくれたTopCoder社に申し訳なさを覚えました。いくら「あれはマラソンじゃないから」なんて予防線を張っていてもこの結果にはダメージを受けました。TCOというイベント自体は間違いなく楽しかったのですが。
楽しくなくなった原因
「Marathon Matchは時間をかけて取り組めば誰だってそこそこの成績が残せる」という主張をずっと繰り返してきました。「誰だって」というのは微少な誇張が含まれていますが、大筋では今もこの主張に変わりはありません。全員がほぼ同じ条件で戦うTCO Finalで無様な負け方をして、悔しさ惨めさはあったのですが同時にその結果はすんなり納得できてしまったのです。「ああ、やっぱりね。今まで自分なんかが良い成績を出せていたのは時間というドーピング剤のおかげだったんだ」と。「アルゴリズムで超強いあの人とかが自分と同じように時間を使って取り組んだら絶対に勝てないだろうなあ」とかずっと考えていたんですが、それに証明が与えられたような気分でした。プレイしたことがないのでイメージだけで語りますが、課金ゲームみたいなものなのでしょう。他人のゲームの楽しみ方にケチをつける気はないのですが、少なくとも自分については「大量に課金してトップ集団に入れてもらう」というのにあまり魅力を感じられないのです。この考え方は傲慢だし、瑕疵があることは自覚しています。
TCOが終わった後のMatchではモチベーションの維持に苦労しました。それでもマラソンから離れるという選択肢は当時の自分にありませんでしたから、どうすればよいかをちゃんと考えようとしました。私の持論では、マラソンはやる気さえあればまともな成績になることになっています。それはつまり、やる気の維持管理もマラソンの本質であるいう主張です。そこで今までのマラソンで好成績を出せていたのは、やる気があったのは何故なのかと考えてみました。どう考えてもそれは新鮮さだとか、レートがどんどん伸びるとか、一言でまとめるとただの初心者ボーナスでしかなかったのです。このあたりで完全に冷めてしまいました。技術や感性に自信を持てなかった私にとって、今までの好成績はただの初心者ボーナスの恩恵だとしか思えず、それはとても空しい事実でした。やる気とかひらめきに頼らないシステマチックな勝ち方へのスタイルを模索したりもしましたが、案の定うまくいきませんでした。
長々と書きましたが、要するに私は自分の身の丈に合った楽しみ方を見つけられなかったのです。
マラソンから離れてみて
稼げるときにひたすら稼ぐタイプの問題を一度やってみたかったです。ひたすら弱点潰すのよりは前向きでワクワク感がありますね。問題としてそれが良いのか悪いのかは判断できませんが、そういう方向の問題も1回くらいはやっておきたかったです。1回やれば十分な気もします。
私が最初にマラソンに興味を持ったのは、知人の「マラソン始めたらアルゴリズムのレートも上がった」という発言からです。事実を述べると、私のアルゴリズムのレートはマラソン始めてから確かに上がりました。しかしそれがマラソンのおかげなのかどうかは判断がつきません。先の発言は、「マラソンやるくらい競技に熱心な人はレートにまだ伸びる余地がある」という程度のことでしかないのかもしれません。
マラソンをやって得たアルゴリズム的な知見もなくはないです(逆はいっぱいある)。とは言っても具体的で詳細なあれこれではなく、抽象的で原理的な考え方の方向性についてですが。プログラムが遅い原因というのは解がないところを探索しているか、同じような計算を何度も繰り返しているか、原理的にどうしようもないかです。プログラムを高速化するには、枝を刈る、状態の同一視、部分的な計算結果の再利用、謎の数学パワーが基本路線となるようです。マラソンをやって得た知見、というよりは探索を書いて得た知見といった方が正確かもしれません。
マラソンどころか競技全般から離れて時間が経ちましたが、知識は減るものでもないので今の私はやる気という条件さえ同じであれば当時の自分より当然強いはずだと信じています。意味のない話ですけどね。
各Matchの感想
問題そのものはMatchの一要素に過ぎません。
StreetSales
適度に複雑な問題自体は好きですが参加者が振るわなかったのが残念です。今の強い人たちがやったら当時一位のスコアもあっさり抜けるのではないかと思います。ビジュアライザを眺めるだけでも結構楽しめます。大雑把にいってやることは1.経路探索 2.仕入量の決定 3.経路、仕入量の修正、以上3点です。
この回ではyowaさんが私と同じく初参加していて、密かにライバル視して競争を楽しんでいました。最終的には負けましたが、途中までは抜きつ抜かれつの緊迫した勝負ができていた気がします。
CuttingFigures
期待値計算とパッキングの2点がメインです。期待値計算の部分が非常に重要になってきますがそこは前提条件にすぎず差がつけられません。
DigitsPattern
同着1位が大量発生した回です。テストケースの生成方法が2種類あり、一方の生成方法で作られたケースは多項式時間で最適解を出すことができます。もう一方の生成方法で作られたケースも多項式時間の前処理で問題のサイズを劇的に落とすことができます。ところでMarathon Matchはかなり多くの情報が公開されているのですが、本番で用いられるテストケースの数については事前に公開されません。この回ではそれが問題になりました。前処理を施した後に多項式時間で解くことが難しそうな小さいサイズの問題が残るのですが、これを全探索で解くか適当なヒューリスティックで解くかという選択に関わってきます。ローカルで10000ケース程試して全探索がすべて制限時間内に収まっていることを確認したのですが、10000というのが十分だったのかどうかは難しいところです。
BeautifulCrossword
1位の人の解は問題名通り非常に美しい。
私はこの問題を入力によって複数の解法を切り替えるタイプの問題だと信じていました。当時の私はそういう取り組み方勝ち方というのに憧れていたので、信じたいように信じてしまったのです。
この回はやる気も時間も標準的に使った上での不満足な結果だったので、持論に反するという理由でもやもやした気分になりました。
QualityPolygons
問題自体の面白さは多くの人が触れています。現実的な方針がたくさん考えられる、というのが人気の理由でしょうか。このMatchはスコアリングも特殊です。各テストケース毎における参加者内でのランキングに基づきそのテストケースにおける得点が定まるという形式をとっています。これについてコンテスト中は「稼げるときに稼ぐのではなく取りこぼしを減らさなければならない」と意識していました。
この問題は問題サイズがsmallとlargeで二分できます。先に上げた取りこぼしを減らすという意味ではsmallに気を配る必要があります。実際コンテスト中終盤で、順位表から得られる情報を加味してもsmallケースで稼げていないと分かっていながら時間の多くをlarge対策に費やしてしまいました(理由は面白かったから)。
そして結果についてですが、自分が参加した全てのMarathon Matchの中で最も印象に残っているのがこの回のainu7さんです。総合的な順位は8位ですが、smallケースだけで見ると凄まじい圧勝をしています。スコアリングがランキング形式という特殊なものだったことも影響しているのでしょうが、焼きなまし系統(というのはあまりにも大雑把すぎる分類ですが)の問題でこんなに大差がつくのは見たことがありません。逆にBestが93個、Unique Bestが18個しかないのにも関わらず総合で圧勝しているwataさんも印象的です。
StringCompression
TCO Round3という最も胸躍る舞台にも関わらず好きになれない問題でした。途中で問題の重要な制約に変更が加えられたこともあり悪い印象しか持っていません。問題自体には不満がありますがMatch自体は楽しめました。強い人たちの間近で戦えるというのはやはり良い。
そういえば初めてビームサーチを使ったのがこの問題です。初めてというか、最初で最後になってしまいましたが。これ以前のMatchでは大体貪欲か全探索しか使ってなく、それで赤コーダーまでいけたのですから大らかな時代でしたね。
OptimalScheduling
12時間で取り組む問題ということを前提に考えるとそんなに悪くない問題だったと思います。
初めて焼き鈍しを実装したのもこの問題です。…ここに至るまで焼き鈍し実装したことがないというのは不誠実なのでは？
AntiTravelingSalesperson
数学を軽視した結果大敗を喫した回です。多分こうすればまともなスコアになるんだろうな、という方針を考えて実装してみるもスコアは上がりませんでした。不思議に思いつつもその方針を破棄し、そこで実質的に終戦してしまいました。スコアが上がらないのは実装のミスが原因でした。実装を間違えるのは仕方ないことですが、それに気付けないのは大問題です。直感なんて持ち出すまでもなくちょっと手計算していれば実装ミスだと気づけたのですが。あまりにもみっともない失策で、自分に強く失望しました。
