Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AtCoderで青色になるまでにやったこと

f:id:misteer:20180607150202p:plain

先々週のAtCoder Regular Contest 098で念願の青Coderになれて、競プロモチベが止まらないMisterです。

プログラミング歴1年半、こと競プロ歴に関しては半年弱の私が今まで何をやってきたのか、いい機会なので振り返ってみます。

目次

AtCoder

私がメインで取り組んでいるコンテストサイトは、もちろん「AtCoder」である。 無論一番多くの問題を解いているのもAtCoderであり、青になった時点で大体500問解いていた。

そこで、私がどのような過程を踏んでAtCoderの問題を解いていったのかを振り返ってみようと思う。

ABC-A,B及びARC-A

ABC-A,Bのように「今の実力なら瞬殺できる」ような問題を大量にACで埋めていく作業のことを、一部では「虚無埋め」と呼ばれている。 名前の由来はそのまんまで、頭を働かせずに解けるので人によっては虚無感を覚えるかららしい。

そんな虚無埋めだが、読者の方々の中には「意味がない」と思っている方も少なからずいることだろう。私もどちらかと言えば「意味はない」と思っている側の人間である。 得られる知識もほとんどないし、しいて言えば多少解答スピードが上がる程度だろうか。

一方で私はこの虚無埋めが大好きでもある。ABC-A,BとARC-Aに関しては100回分弱を約10日で一気に埋めている。

なんで好きかといえば、主な理由としては「進捗が目に見えるから」。 AtCoder Problemsの表が一気に緑に染まる様は見ていて爽快。 あとは「解ける問題が埋まっていない」という状況がひどく気持ち悪いからというのも大きい。変なところで潔癖な性格が出ている。

今もしもABC-A,Bを埋めるか悩んでいる方がいれば、「やりたければやればいい」程度に思ってくれて構わないと思う。無理してまでやるものではない。

ABC-C

そんな虚無埋めの後にようやくABC-C埋めに取り掛かったわけだが、これが予想以上に長く、また得られたものも多かった作業だった。

多分水色レベルの方ならC問題の8割ほどは楽にACを取れるだろう。 しかし終盤に差し掛かってくるとAtCoder初期の方、特に20番台が異様に多く残るはず1

この辺りの問題は本当に容赦ない難易度のものが含まれているが、その分馴染みのない概念が含まれているものも多く、得られる経験値もとても多い。 今まさに詰まっているという方は、解説や他人のコードを見てでもとりあえずACを取ってみることをオススメする。

個人的にとてもツラかった、あるいはまるで解法が思いつかなかったC問題を以下にまとめておく。これらに取り組む際は特に覚悟を決めると良いかと。

  • 008「コイン」
  • 009「辞書式順序ふたたび」
  • 017「ハイスコア」
  • 018「菱型カウント」
  • 021「正直者の高橋くん」
  • 022「Blue Bird」
  • 023「収集王」
  • 025「双子とoxゲーム」
  • 029「Brute-force Attack」
  • 062「Chocolate Bar」
  • 077「Snuke Festival」
  • 080「Shopping Street」
  • 091「2D Plane 2N Points」

ABC-D、ARC-B

長く険しいC問題を力技で抜けた私だが、今現在ABC-DとARC-Bが合わせて残り13問(青になった当初は30問強)埋まっていない。

いや難易度がえげつなさすぎる。解説見ながら「ABCレベルじゃないなら出さないでくれよ...」ってINF回言ってる。 しかしまぁ、その分解法を完全に理解したときは得られるものも大きそうなのでチマチマ埋めていく予定。

ちなみに埋まっていない13問がこちら。6月中にケリをつけたいところだが、果たして。

  • ABC
    • 003「AtCoder社の冬」
    • 008「金塊ゲーム」
    • 020「LCM Rush」
    • 024「動的計画法
    • 025「25個の整数」
    • 031「語呂合わせ」
  • ARC
    • 047「同一円周上」
    • 055「せんべい」
    • 057「高橋君ゲーム」
  • 共通(ナンバリングはABC,ARC)
    • 050,066「Xor Sum」
    • 056,070「No Need」
    • 086,089「Checker」
    • 093,094「Worst Case」

AGC-A,B

上の他にも、AGC-A,Bも25回分埋めてある(青になったときはBが半分くらいだった)。

AGCはABC,ARCとは大きく傾向が異なり、「アルゴリズム力」「実装力」よりも「発想力」に大きく寄っている2。それはそれでABC,ARCとは大きく趣向の異なる知識が得られるので、まだ埋めていない方はチャレンジしてみることを強くオススメする。

バイリンガルへの道?

私がメインで取り組んでいるのはAtCoderだが、1月ほど前に「AOJ-ICPC」も60問ほど埋めていた。Pythonで。

言い忘れていたが、私の主な使用言語は競プロ界隈でも最も使われている「C++」である。実行はアホみたいに速いわSTLは充実しているわで競プロのために存在しているような言語だが、やはり低級言語ということもあって配列や文字列の扱いが難しい。 そういったC++では解くのが難しい問題に直面したときに活躍するのがPythonである。

Pythonは最近特に機械学習方面で話題沸騰中の高級言語である。高級言語というだけのほどはあって、リストや文字列の扱いがとても楽。その簡潔さたるや、C++の比ではない。

そしてAOJ-ICPCでは発想問題がメインのAtCoderとは対照的に、実装が重い問題が大半を占める。 その中にはC++よりPythonの方が相性がいい問題も少なくなく、仕様の勉強も兼ねてAOJ-ICPCPythonで埋めていたわけである。 今となっては、PythonでもAtCoderの500点くらいなら十分実装できるレベルにはなっている。

ただし、Pythonの非常に大きな弱点として「実行が遅い」ことが挙げられる。おおまかにはC++の10倍くらい遅いと言われている3。それでもPythonは他分野はもちろん、競プロにおいても十分に習得する価値のある言語だと思う。

C++Pythonに加えて、実行速度もC++に引けを取らずリストもわりかし扱いやすいらしい「C#」を勉強することも考えているが、正直あまり乗り気ではない。競プロやる上で欲しいライブラリが少なすぎるというのがネック。 yukicoderの下埋めをC#でやろうかな〜とか思っていたりしているが、今のところは未定。

解説記事

HatenaBlogの方にも今は移してあるが、5月の上旬にlivedoor BlogでABC-D問題の解説記事を3問分書いたことがある。 たったの3問なので効果についてはとやかく言えたものではないが、書いた後では知識がずいぶんと整理されたような印象を受ける。

ただ、この記事もそうなのだが私が記事を書くとどうしても分量が多くなってしまう傾向にある。1記事書くのに大体3時間も費やしてしまい、重すぎて以前はやめてしまったがまた解説記事の投稿は再開しようと考えている。

今後の話

新年にAtCoderを始めた当初は特に目標もなかったが、3月頃になって「最低でも青になるまでは続ける」というモチベーションが出てきた。 そして5月の下旬になってようやくその目標を達成できたわけだが、今となっては黄色が大きな目標となっている4。パフォも最近は黄色台がそこそこ安定してきているし、それほど無理のない目標でもないと思っているが楽な道のりではないだろう。 いつか「AtCoderで黄色になるまでにやったこと」という記事が書けるよう、今後も精進あるのみだ。


  1. この辺りはD問題も同様に狂っているので、個人的に「魔の20番台」と呼んでいる。

  2. 故にAGCのことを「天才以外お断りコンテスト」「AtCoder 地頭 Contest」なんて揶揄?する人もいるんだとか。

  3. 正しくはPythonが遅いのではなくC++があまりにも速すぎるだけなのだが、多くの問題はC++の計算速度を基準に時間制限が決まっているためPythonは肩身が狭いというのが現状。

  4. 大学が大学なので、周りに青色が多すぎるというのも大きな要因ではある。