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

ctyl's problem solving

競技プログラミングが主な話題です。

プログラミングが苦手な自分が競技プログラミングを始めた話

この記事はCompetitive Programming Advent Calendar 2015 Day22の記事です.

www.adventar.org

始めてから4ヶ月間競技プログラミングを無事に続けられているのですが,自分がどういう思いで競技プログラミングに対して取り組んできたのかを振り返っていこうと思います.アルゴリズムなどの具体的な話題は一切ありません.


自己紹介(前科)

まず自分の話をさせてください.実は(競技)プログラミングの世界はかなり前から知っていました.高校時代にまで遡りますが,当時は情報オリンピックの問題を見たりしていました.言語の基本文法やら何やらで躓いて時間ばかりが過ぎていき,その当時は結局「プログラミングというのは自分ができる技ではない」という結論に終わりました.余談ですが,数学オリンピックの方は中学のころから予選を通過し続けていて,最後の年はあともう少し頑張れば本選通過できるのではないかという感覚だったので,そちらに集中することにしました.結果として,代表にはなれなかったもののなんとか本選を通過することができました.数学オリンピックの日本代表や本選通過者がかなり高い割合で情報オリンピックでも高い成績を出しているのを知ったのはその後になってからでした(最近の動向は追いかけていませんが,今もその傾向はおそらく変わっていないでしょう).

次に競技プログラミングに触れることになったのは学部2年のときで,蟻本とAOJを使った授業を履修していました.やはりそのときも入出力がうまくいかなかったり,謎のエラー(謎ではない)に悩まされたりして肝心の内容にはほとんどついていけず, X Cubic(AOJやっている方なら知ってますよね)を通せる程度でした.話を聞いていて各アルゴリズムの概要は理解できたけれど,ほとんどの問題は力不足で実装のちACには至りませんでした.ただX Cubicのような簡単な問題であっても,Acceptされるとなんとも言えない嬉しさがあったのもまた事実です.

X Cubic: x の3乗 | プログラミング入門 | Aizu Online Judge

それから4年の年月が経ち,CODE FESTIVALというお祭りが開かれる情報を入手し,なんとなく思い出作りに挑戦してみようということで,ABCに参加したりして,他のことを投げ出して予選突破に向けて問題を解いたりしていました.修士課程2年目なので,始めるタイミングとしては最悪だという自覚はありました.来年は学生ではなくなるので集中して取り組む時間も少なくなると思いますし,一通りのアルゴリズムを学ぶには年度末までの時間だけでは十分とは言えません.ただ何か上手く行ったという自信が欲しかったんだと思います.後は断続的に大学での演習や研究などでプログラミングを道具として使ってきて,その行為自体に慣れてきていたのもあるかもしれません.その後ですが,練習の甲斐もあってかCODE FESTIVALは予選Bで通過し,決勝に進むことができました.それと同時に遥か上の世界を生で見ることができました.大会の運営の方には本当に感謝しています.この「遥か上の世界を見上げる」というのがなかなかやりたいと思ってもできないことで,こういう機会を学生の最後の年に体験できたのは本当に運が良かったと思います.レーティングの数字でも「遥か上」感は伝わるのですが,やはり目の前で見せつけられないと人間って納得しないんだなと思いました.

recruit-jinji.jp

しかし,競技プログラミング周りの環境が4年前に比べても変化していたのは事実で,そのおかげもあってか以前と違いハマっていきました.


yukicoder

数年前に諦めた時と比べて競技プログラミング周りの環境は激変していました.その一つがyukicoderです.

yukicoder

自分がアルゴリズムを学ぶ場所として選ぶとしたら今あるオンラインジャッジサービスの中だとyukicoderが一番だと思っています.学習の用途としてのyukicoderの自分にとっての良さを挙げると以下のような理由です.他のサービスとかぶっている点もありますが,これが全て揃っているサービスはなかなかないと思います.

  • テストケースの中身を見ることができる
  • 解説のリンクが問題ごとについている.しかも複数ある場合も多く,色々な人の解説を見ることで独りよがりの解釈を回避できる可能性が高い.
  • 問題にタグリンクが付いていて,似た手法を使った問題を簡単に参照できる
  • スマートサブミットやサンプルコピーボタンなど,検証や提出にかける労力をできる限り少なくするような工夫がある

このタグというのが始めたばかりの段階で特に重宝することになります.今の自分もそうですが,初心者の実力では客観的に質の良い問題,悪い問題の区別がつけられません.難易度も結局自分主体なので,低い難易度でもいつまでたっても解けないことなどもよくあります.その際に,タグで飛んで類題を通すことで「そのタグのついた問題を1問解いた」という自信が得られるので,モチベーションにつながります.調子が良い場合はわからなかった類題が解決することもあります.自分の場合は,まだアルゴリズム自体に慣れていない場合はAOJのIntroductionの該当部分を事前に確認しておきます.

それにしてもyukicoderはオンラインジャッジサービスとして出来すぎていて気持ち悪いくらいです.機能やシステムも流動的に変化したり追加されたりしていて,今後の期待度は高いです.今後も面白い問題を見つけていきたいですし,あわよくば自分も作問できればと思っています.

AtCoder

もう一つはAtCoderの存在です.

AtCoder (アットコーダー)

初心者がプログラミングに興味を持ってもらうファーストステップとして競技プログラミングを推進する理念(?)があるからか,初心者も足を踏み入れやすいコンテストが定期的に開かれています.また,自分が知る限り日本語で行われる唯一の競技プログラミングサイトです.自分が始めたきっかけもABCで良い成績が取れたからで,ABCの存在は間違いなく自分のモチベーションに貢献しました.

主観ですが,ライブラリに頼らず思考力と実装力を試すような問題が多い印象をうけます(この形式は好きです).また問題ごとの難易度もうまくばらついていて,かなり広いレベル帯に対してケアされている気がします.AtCoderにはまだレーティングで競うという文化がないので,勝ちに行くスタイルではなく,何か新しい知見を得る,という目的で参加しています.

ABC, ARCに関しては解説放送がコンテスト終了後にあります.でもスライドを読んでいるだけの部分もあって(特にスライドがわかりにくい場合)わかりにくいことも・・.難しさには少なくとも解法の難しさと実装の難しさがあるので,両方をカバーしながらうまく解説というのはなかなか難しいのかもしれません.

Twitter

Twitterでのコミュニティーの活性化も競技プログラミング周りの環境の変化として挙げないわけにはいきません.

Twitterを見ているとコンテスト前後ではツイート数が増加し,コンテストに対するモチベーションを上げることができます.また,コンテスト後では問題の感想などがツイートされ,色々な解法を流し読みでき簡単なレビューができます.最近だとアルゴリズムや問題のわからないことを呟いたらリプライが飛んできたこともあって,こういうことが自然にされるのは驚きでしたし,自分もできる限り手を差し伸べられる範囲でやっていこうと思いました.この節だけ分量が少ないのは単純に競技プログラミングの知り合いがほとんどいないからです・・色々とオンサイトのイベントなどに行って面識を広げることも必要だと感じています.競技プログラミング系のイベントはこれからも参加できる範囲で参加したいと思っているのでもし会ったらできる限り挨拶したいと思います(CODE FESTIVALの時は周りが全員赤い人に見えて全然声をかけられませんでした).


自分の競技プログラミングに対する取り組み方

TopCoder SRMCodeforcesはそれぞれ月に3~4回開かれていて,それに全て出るだけでも月6回程度コンテストに参加することになります.AtCoderも含めると月7,8回になることだってあります.コンテストに出れば出るほど色々な問題に触れることになりますし,レートもたくさんのコンテストを経験した分上がるかもしれません.一方で,世の中には超強い競技プログラマー(赤い人たち)がいて,上のようなコンテストだけでなくHackerRankやCodeChefなどのコンテストにも参加されていたりします.ですが自分はまだ緑コーダー.身の程をわきまえなくてはいけません.難しくない問題であっても実装に結構な時間をとられてしまうことだってあります.それだけたくさんのコンテストに出て,解けなかった問題のレビューも怠らず,しっかりと物にするほどのキャパシティは今は持ち合わせていません.特に,まだ未習のアルゴリズムが想定解になっているような問題をいくら考えても時間の無駄です.普段は自分はあらかじめ解くと決めていた問題とか設定が面白いと感じた問題を好きなように解いているのですが,できるだけ早く成長するために少し意識していることを書きます(正確とは限らないので,何かコメントやアドバイスがあると嬉しいです)

1. 取り組むジャンルを数問単位で固定する

とにかく一通りのアルゴリズムを早く習得したいと思っているので,3~4問単位で同一の(または類似した)手法が解法として想定されている問題を解きます.例えば「2分探索」「DP(動的計画法)」というようにテーマを縛り,yukicoderのタグをたどったり,AOJから問題を選びます.また自分は必ず日本語で読める問題を選びます.英語を読むための余計なエネルギーを消費したくないからです.蟻本を読むだけだとやった気になるだけだし,長い間1ジャンルに粘着するとモチベーションが落ちるので,モチベーションの維持という観点ではある程度の成果が出ているのではないかと思います.タグ別にこの順番で解くと理解が深まるというガイドってなかなかないからお膳立てがけっこう大変.みなさんはどうしているのでしょう.

2. コンテスト中以外で進展のない長考をしない

自分は手がかりがつかめない状態で10~15分経ったら解説を見てしまいます.そして大体の場合,解説を読んだからといってすぐに実装してACできるということは起こりません(発想で一発という場合を除く).長考する意味がある部分は,どういうアルゴリズムやデータ構造に落としこむかを思いつくところだと思っています(違ったらすいません).アルゴリズム自体に不慣れな最初のうちはアルゴリズムやデータ構造の適用に慣れることが最優先だと信じています.多分解説を読んでからどう実装しようか考える部分の方が学習効果は高いのではないかと思っています.これがどう影響するかは今後数か月の自分のレート変動にも関わってくるでしょう(怖い).自分の実力が上がってきたと感じたら長考スタイルにシフトしていくと思います.

3. 作問者によるEditorialがないコンテストには不用意に参加しない

始めたばかりのうちは解ける問題より解けない問題の方が多いので,復習は何が何でも必要です.特に時間いっぱい考えてもどうしてもわからなかった(通らなかった)問題はすぐにでも解説が見たい.あとはTesterがいるコンテストの方が参加していて安心感がありますね.解けていない問題のうち一番手前の問題を復習すると良いと言われているので,大体はそれに従って復習しています.

4. 同じ日に複数のコンテストに参加しない

単純に疲れるし,復習の量もかさむので2つ以上のコンテストが同じ日にあるときはどちらかを捨てます.SRMCodeforcesの日程がかぶるのは本当に勘弁.

5. AtCoder Beginner Contest(ABC)には極力参加する

これはワンパスで解ける問題を速く通す練習にはもってこいのコンテストだと思います.ただD問題はA,B,Cに比べて結構難しい傾向があるので,A,B,Cを早めに解いて残り時間でDをゆっくり考えるという時間配分になりやすいです.自分はA,B,Cは速さを意識して,Dは時間内に通せれば最高,という感じで参加しています.ACが速くつくので気分的にも乗りやすいコンテストです.

6. 自分を雑魚だと思わない

自分のことを不用意に雑魚と公言するのは一種のハラスメントだと思っています.と同時にそう思ってしまうと,「自分は雑魚だからこんな難しい問題解けなくて当然」という暗示をかけて実力向上に歯止めをかけてしまう恐れがあります.自分の場合はコンテスト中になかなか解き方がわからない問題に出会ったときは,「人間が出題している正解のある問題なんだから解けないわけがない」と暗示をかけて(自分を騙して)います.

最近は専らハラスメントが横行しているとのうわさです.例えば自分が弱い(具体的に何がとは言い難いですが,例えばレーティングの数値とか?)ことを主張することで自身を擁護し,言いたい放題ものをいうのは見ていてつらいです.TopCoderなどで他人のコードを撃墜するのと,コミュニティーでの他人そのものを潰すのは違うと思います.プログラマー界隈はただでさえギスギスしている印象があるので(主観です),少しでも優しい世界になってほしいものです.(自分はプログラミングが苦手ですが,そのような理由でプログラマーも苦手ですね・・)


おわりに

ここまで読んでくださった方,本当にありがとうございます.今思うともっと早く競技プログラミングを始めていたら,周りの環境も変わるだろうし,自分の考えも違う方向に行っていただろうと少し後悔しています.また中学生や高校生で高レートの人は本当にすごいなあと思ってしまいます.自分は今以上に強くなりたいと思っていますし,またプログラミングコンテストに定期的に参加することで自分の頭も多少は腐りにくくなるかと思っているので,できる限り続けていきたいと思います.あとはチームで何かコンテストに出るのがいつか達成したいことです.まずはチームを組みたいと思われるような実力にならないといけませんね.(同じ思いの方がいたら是非...!)

次(23日目)の担当者はnico_shindanninさんと_ehaさんです.