読者です 読者をやめる 読者になる 読者になる

社会人10年目から始める競技プログラミングのすすめ

これは、Competitive Programming Advent Calendar 2014の17日目の記事です。

競技プログラミングという世界を知って1年がたちました。結構飽きやすい性格の自分が1年ほどコンスタントに参加するという充実したプロコン(プログラミングコンテスト)ライフを送ることができた記念に、これからプロコンに参加してみようという方向けの記事を書かせていただきます。CPAC2014参加諸氏のような技術的に高度な内容は残念ながらなさそうですが(書けるものなら書きたい)、10年目エンジニア的視点で自分が感じたことを踏まえて「これはいいものだ」と思えたところなどを中心に振り返ることで、なんとかタイトル詐欺を回避したいと思います。中盤はお目汚し感が強いかも。。

経緯や参加したプロコンなど

半導体関連のメーカーで開発の仕事に従事していますが、2012年に職場都合で富山県に引っ越すことになりました。初の関西脱出というところで最初はわくわくしたものの、その後、富山人ライフにも飽きが来ていた2013年の春ごろにFacebookの友人の記事でcodeiqを知ったのが原初体験だったかと思います。

codeiqの出題者や参加者の中にはもちろん競技プログラミング経験者も多いようで、その情報をたどるうちに知ったのがAOJです。しばらくはAOJをコツコツと進めていましたが、割とすぐに解けない壁にぶつかります。回答公開されている方のソースを読んでもよく分からない。そう、動的計画法です。どうやら未知の考え方があるみたい。

分からないのでググったりしているうちに出会ったのがAtCoderですね。というか多分最強最速アルゴリズマー養成講座などの記事から知ったのだろうと思います。この記事か何かでTopCoderの存在を知って、あとCODEVSという学生プログラマのAIコンテストの配信を見たりして、コンテストも挑戦してみようと思ったあたりからいわゆる競技プログラミングの世界に足を踏み入れはじめます。ただ、TopCoderは言語がC++/Java/C#と限定されていた一方、僕はC言語でホントにちょっと書ける程度だったので、しばらくAOJでC#に慣れるために練習しました。

 SRMTopCoderアルゴリズム競技部門)初参加は2014年の1月の下旬、easyを128/250pts位で通して、灰色コーダーデビュー。Ratingの重みを知ります。Ratingは命より重い。嘘です。嘘ですが、プロコンの中毒性をエンハンスしている大きな要素の一つであることは間違いないです。それと、中毒性という点では決まった時間で問題を解くというところが学生時代の試験を思い出して、これもまた懐かしい感覚です。

SRMは代表的なプロコンですが頻度は隔週弱くらいなので、経験を積むという意味でもっとオンラインコンテストないか、と探してみるといろいろあります。codeforcesが高頻度でコンテストを開催していて、こちらは隔週よりかなり多い印象です。codeforcesに関しては、初参戦から4回くらい参加した後、運営側のトラブルで2週間くらいのデータが復元不可能になるほど壮大にこどふぉる(後述)事件がありアカウントごと消えたりしました。初回の結果でスタートのRatingが決まるので、2回目の登録の時、「再履修アドバンテージでハイスコアスタートでいきなりdiv1ワンチャンあるんじゃね?」と思ったがまぁそんなことはなかったです。

そんな感じでSRMcodeforcesをメインに取り組んでそろそろ1年です。他に手を出してみたところではHackerRankProjectEulerなど、まだまだたくさんあります。最近ではyukicoderさんにかなりお世話になっています。

面白いの?

個人の感想であり、効果には個人差があります。エッセンスを説明するのにちょっとしたゲームをしてみます。 

f:id:kuuso1:20141124072705p:plain

16個の数値と、それぞれに振られた番号が上の図のように与えられています。また、あなたの手元には電卓とメモ帳があります。
これから100問あなたに質問します。1問の質問は簡単で以下の要領です。

  • 2つの番号 A,B (但しA ≦ B)をこちらが指定します。番号Aから番号Bまでに対応する数値の総和を答えなさい
  • (例) 問0:1~4 ⇒ 8+14+9+19 = 50 
さて、電卓をたたき続ける作業は非常に億劫なのでできるだけ少ない回数で済ませたい時、あなたならどうする?

 試しに10問くらい考えてみましょう。暗算でもいいので自分が計算する様を思い描いてください。もちろん実際に電卓を叩いてもらっても構いません。
  問1:2~5   問2:3~12 問3:1~20 問4:13~14 問5:13~15
  問6:7~16 問7:13~17  問8:2~5     問9:15~16 問10:13~16

何回くらい「+」の記号を押したでしょうか。コツコツ真面目に毎回計算すると60回くらい押しているはずです。完全にランダムに問題が与えられるとして、平均5.0回は押さないといけない期待値計算になるので、大体100問で500回くらい押すことになりそうです。

 これはさすがにうんざり。例えば、問1と問8は同じ問題なので、問1の計算後に答えをメモっておけば問8での計算は全く不要。もっと言えば、A,Bの組み合わせは136通りしかないので、先に136通り求めておけば後は答えるだけ!じゃあ136通り求めるのに何回くらい「+」を押すかというと、例えば1~4の計算結果に番号5の値を足せば1~5の結果になるので、「1から始めた場合」「2から始めた場合」・・・「15から始めた場合」で合計 15+14+・・・+1 = 120回。これだけ押せば、たとえ1000問出題されてもビタイチ追加で押す必要はありません。真面目に毎回計算する1/5で済みました。

 さて、では次の場合は・・・

160個の数値と、それぞれに振られた番号が前問のように与えられています。また、あなたの手元には電卓とメモ帳があります。
これから100問あなたに質問します。(以下同文)

  同じように計算すると、真面目にやると期待値で5300回。全通り計算する方法では12720回。組み合わせが増えてきて全通りの方が厳しそうになってきました。

 毎回真面目に計算するのと、あらかじめ全部計算するのと、それらの間にもっといい方法がないだろうか。ある程度質問ごとに計算するんだが、1回の計算は事前に計算したメモを参照して簡略化できるような・・・?

 で、例えばこういうのがあります。累積和。

f:id:kuuso1:20141124090929p:plain
               (図は16個の場合)

 最初の例で説明した、1から始めた場合の答えだけ覚えておく。すると、例えば5~9の和を聞かれた場合は、1~9の和(116)から1~4の和(50)を引けば66と答えられます。

 先の160個の場合、この方法だと、下準備に159回、各質問に1回の計算×100問でなんと259回の計算で済みます!!1ケタ以上少ないですね、楽ちん!

 とまあ、こんな感じで、うまくアルゴリズムと覚えておくデータの持ち方を考えて、限られたリソースと時間の中で問題を解くというのが競技プログラミングでよく問われる問題です。どうでしょう、楽しそうでしょうか?物足りない?ではこんな意地悪が入ります。

160個の数値と、それぞれに振られた番号が前問の様に与えられています。また、あなたの手元には電卓とメモ帳があります。
これから100問あなたに質問します。1問の質問は簡単で以下の要領です。

  • 2つの番号 A,B (但しA ≦ B)をこちらが指定します。番号Aから番号Bまでに対応する数値の総和を答えなさい
  • 但し、私は気まぐれなので、2~3問に1回、ランダムに1つ選んだ番号の値を書き換えます。どこを何に書き換えたかは教えます。 

  こんなことをされると、せっかく作った累積和メモを変更のたびに毎回更新しないといけないので大変。。。

f:id:kuuso1:20141212004719p:plain

「もう、無理じゃね?」

 大丈夫、セグメント木ならね。

f:id:kuuso1:20141124094752p:plain


               (図は16個の場合)

 トーナメント式に計算した値を保持しておくと、少し1回の計算数は増えるが、任意の組み合わせについて16個の場合で高々4回、160個でも高々8回の計算で質問に答えることができます(下図の要領)

f:id:kuuso1:20141211012623p:plain

さて、累積和より少し計算数が増えたこの構造、メモの更新という新たな問題に対して素晴らしい効果を発揮します。具体的には下の図を見てもらえば雰囲気が分かるかと思います。

f:id:kuuso1:20141212004726p:plain

 累積和だと、変更された箇所より先は全て影響を受けるので、それらすべてを再計算しないといけないのですが、セグメント木は上方向の値を更新するだけです(これでうまくいく理由はトーナメントの感覚的にわかると思います)。

 このような感じで、与えられた問題に対してどうやるのが最適か?というアルゴリズム的な部分、それをプログラムでどう表現するかというプログラミングの部分。それを適切に選び、時間内にプログラムを書き提出する。とても競技要素の高い知的ゲームが競技プログラミングです。登るべき山は高くまた裾野は広いため、長く楽しめるものだと思います。
chokudaiさんのアルゴリズム擬人化の話で似たようなことを話されていますが、個人的には格ゲーに似た感覚があると思っています。どのキャラがどういう技を持っていてどういう局面に強いのか、みたいな。あと「強い人はフレームが分かる」とか「コマンド入力が恐ろしく無駄がなく正確」とかそういうとこも)

仕事の役に立つの?

(ここはいわゆるチラ裏なので、興味のない方は次のセクションへ)

 個人の感想であり、効果には個人差があります。自分の場合はほとんど日々の業務には直結しないです。ただ、業務に直結しない=役に立たないと断じてしまうのは早計だとは思います。以下は私見というか単なる僕個人の思い込みですが、例えばこういう利点があると思います。

  • エンジニア寿命という考え方
     ドラッガーの引用で恐縮ですが、「知識労働者の寿命はもはや企業の寿命より長い」という考え方があります。エンジニアは知識労働者です。企業寿命というと大げさに響くかもしれませんが、プロジェクトと言い換えると、自分の携わるプロジェクトが2,3年で変わってしまうことなどは割とありふれている事だということは想像に難くないと思います。すると、当座の業務に直結することが第一の正義という主張は必ずしも肯定されるものではありません。経験上、それよりもある程度のスキルと思考力で手を動かせることの方が、環境適応という点で大切な局面が多いように思います。ちょっとしたプログラムの読み書きでデータの挙動を眺めてみる、その一手が打てるか打てないかは大きいため、プログラムが書けることはそのまま財産になります。競技プログラミングでプログラミング能力は間違いなくある水準までは高まるため、エンジニア寿命にとって有益といっても良いと考えます。(と、10年前の自分に教えてあげたい)
  • 競技プログラマ達のコミュニティの中に身を置くという事
     語弊を恐れずに言えば、それなりに真面目に10年ほど働くと、「この件に関して自分が一番詳しい」という局面がちょくちょく出てきます。それは良いことでもあるのですが、増えすぎると自分の能力律速になってしまい、気づかないうちに飽和してしまうという事もあります。その点において、競技プログラミングの世界には、もう訳分からんくらい頭のキレる人が山のようにいます。中学生にフルボッコにされたりします。まぁ大学の時もそういう人々に囲まれた生活だったので、懐古的と言えばそういう気持ちもないでもないです。
  • Tシャツとかもらえるらしい
     僕はもらったことないです。2014年という年は特に学生の競技プログラマを取り巻く環境にとっての大きな変化の年だったようで、CodeFestivalはじめさまざまな意欲的な取り組みがあちこちで催されていました。Tシャツだけじゃなく焼肉がついてくるらしい?社会人競技プログラマからすれば羨ましい限りという思いを抱かれた方も少なからず居るかと勝手に妄想してますが、大体よく言われているように技術者の職場マッチングはこれからもまだまだなくなることのない課題だと考えれば、今の世代の学生さん達が社会人となって3年目くらいとか、5年目くらいとか、まだまだ社会人ワンチャンみたいなイベントは増えるかも(もっともその頃には僕はもう中堅より上の年齢層で、やはり人権はないかもですが、労働サイクル自体が伸びている可能性もあるし、うーんなかなか)。あとやっぱりGCJシャツとかゲット出来たらちょっとかっこいい。
  • レーティング
     大体のコンテストサイトには独自のレーティング制度があります。コンテスト成績の良し悪しに応じてそのプレイヤーのランクが数値化されていて、上位の数%の人たちは神か悪魔かといったふうな扱いです。こういうレーティング制度みたいなものも賛否両論ありますが、個人的には自身の能力を量る指標としてはいいものだと思います(よく言われるのに「レーティングの数値≠実際の能力」だから意味がない、害悪だ、ということがありますが、それは精度の問題であってレーティングすることの問題ではない)。精度が多少犠牲になっていても、実際レーティングが上がればやる気は向上するし、下がれば悔しい思いをする。そういう競争的な刺激のあるものは、仕事の上ではあまり無いから余計そう感じているのかも(成果主義とか、評価関数を成果でしか測れないと諦めたところから生まれた言葉だと思っている)。

 まあ、何でもそうなんですが、あくまで競技プログラミングを練習することで得られる最大の効果は競技プログラミング能力の向上であって、仕事に役に立つとかいうのは運が良ければ副次的に得られるものです。本筋ではない部分にまで直截的な効果ばかりを求めるのは近道なようでいてあまり身にならないことが多い(と個人的には思っている)ので、あくまで種を蒔くというスタンスが自分には合っていて、上に書いたようにTシャツ目指すとか、レーティングに一喜一憂するとか、いろんなタイプのかしこい人の考え方に触れるとか、そういうちょっとしたことが大切だなと思います。

もしこんな感じで、そろそろ仕事にも慣れてきたなと感じている方は、ちょっとした頭の体操がしたい、新しい言語を練習したい、自分のスキルがどんなものか試したい、などなどそれくらいの軽い気持ちが湧いたなら、これを期に始めてみるのもいいのではないでしょうか(ここでタイトルノルマクリア)。

あと箇条書きで僕にとっての良かった/悪かった点を挙げるとすると、

  • (良い点)C#覚えた。OOPもついてきたのでこれは大きいな)
  • (悪い点)C#がベターCみたいになっとる。
  • (良い点)twitterを始めた (プロコン勢はtwitter率たかい)
  • (悪い点)twitterを始めてしまった
  • (良い点)コーディング速度が上がった
  • (悪い点)仕事でのコーディング量は減った(昔は、自動化できるものは割と嬉々としてマクロ化したりしてたが、最近はプログラムにはプログラムにしかできないことをやらせたくなって、人の手でできることをマクロ化したりする事の魅力が減ってきた。これはまずい)
  • (良い点)趣味の充実によるリフレッシュ(仕事自体は今年はクソ忙しかったんだよなぁ・・・)
  • (悪い点)趣味の充実によるインドアライフの加速

君、これではトータルでマイナスではないかね?いやいやそんなことは。

蛇足ついでに、twitterを見ているとこの話題は「月刊競技プログラミングは役に立たない」などという定期スレが立つ話題のようですが、こういう「○○が何の役に立つのか」というテーマは僕自身理学部数学科の出身ということもあって、就活していたころのことを思い出してなんか懐かしくなります。折しも当時は大学の独立行政法人化の波などがあり、虚学だどうだと槍玉にあがることもあったのでいろいろ考えたものですが、10年働いた今思うことは2つ。

  • (仕事がイケイケの時)「誰だよ数学なんか役に立たないって言った奴は!(以下某こくじんさんの名セリフを適宜置き換え」
  • (仕事がダメダメの時)役に立たないのは数学じゃなくて僕のほうorz

競プロと数学と共通して言えるのは、正解に向かって正しく思考できている時には、それが正しいと感覚的に分かるというところで(いわゆる筋というやつ)、数学とほぼ関係ない今の仕事にあっても、筋の良し悪しが判別できるようになってきたころからうまく回せるようになってきたと思うので、そういうところを習得できることは大事だと思ったり。ただそれが数学や競プロでしか養えないか・最適か、となるとそれはまた別。

どんなコンテストがあるの?

 いろいろあります。僕が参加したものはおおむね冒頭で挙げてしまってますが、以下にコメントとリンクなどまとめてみました(今回の記事テーマを機能的にフォロー)

コンテスト形式コンテスト名開催頻度出題形式コメント
コンテスト系 AtCoder 毎週~隔週・ほぼ土曜固定 ARC 4問/90分 日本語なのでとっつきやすい。コンテスト後の解説放送が確実に競プロ界の底上げを加速している。後半2問は難しめ。
ABC 4問/120分 「初心者向け内容」で2完とかで凹む事も。あと1問目10秒サブミットとか意味が分かりません。
TopCoder 隔週弱くらい、曜日不定 SRM 3問/75分+15分 div1とdiv2がある。定期コンテストとしては一番有名どころなのかな。英語だが読み易いのでそれほど気にならない。
codeforces 隔週強くらい、曜日不定 5問/120分 div1とdiv2がある。毎回4-5000人くらいエントリーしていてビビる。その多さからサーバーがよく不安定になる。そこからサイトが不安定なことを「こどふぉる」また、英文が難解な問題が稀によくあり、「ReadForces」などと呼ばれる。
yukicoder 火・木・日 23:20- 2問(!)1時間後くらいから解説 yuki2006さん個人運営のコンテストサイト。最近勢力拡大中。すごい。
HackerRank 隔週弱くらい、曜日不定 いろいろ weeklyChallengeや、48時間コンテストなど、社会人には一見嬉しいサイズのコンテストがあって個人的には結構好き。
HackerEarth いろいろ? いろいろ AC取ると「よくできました!」、WAとると「頑張れ頑張れできるできる絶対出来る頑張れもっとやれるって!」みたいなメールが来る。
オンラインジャッジ系 AOJ いつでも ICPC等の過去問が充実 日本語でとっかかり易く、問題も簡単なものからタフなものまであるので、いきなりコンテストはちょっと、という方はこれで雰囲気に慣れるのがいいのかなと思います。
ProjectEuler いつでも 数学っぽい問題、1問必答 最初50問は数学ゲーというより全検索ゲーなので暇つぶしに。後半は見るからに難しそうな感じがしますがまだまだそこまで手をつけれてません。
その他 codeiq 出題が期間限定(~2,3週くらい) 回答に出題者からフィードバック。 難易度はそれほど高くない問題が多いが、いろんな方が出題されていて面白い。ゴルファーやマルチリンガルプログラマがうろうろしていて怖い

ちなみに僕のレーティングはSRM1214Codeforces1720とともに1年かけてようやくdiv1に滑り込んだくらいです。自分的にはまぁまぁこんなもんか、ちょっとよくできた方かなと思ってます。来年はdiv1安定から黄色ワンチャンくらいを目標に。あとなんでもいいからTシャツ欲しい。

まとめ

何事も始めるのに遅すぎるという事はないし、なにより「今まで知らなかった知識が増える」「これまでできなかったことが出来るようになる」これらの快楽は中毒性が半端ないので、興味湧いた方は是非やってみましょう!スタートコストが低いのもエコでお勧めですよ!