AtCoderで灰コーダーから茶コーダーになったので灰色勢に応援する

本記事の目的

自分が灰色時代、かの悪名高きリセマラ対策のせいもあって、自分の精進や実力がレートにつながっていないのではないかという思いを持ってしまい、モチベーションとか自分の能力にたいする思いにゆらぎがでることがあった。

また、自分が灰色時代にしていた精進はいろいろあべこべで、結果的に実力(競技のパフォーマンス)につながっていなかった。

そこで、自分なりに確立した脱初心者(〜茶上位パフォくらい?)の方法をメモする。

(あとせっかくブログ作ったのでなにか投稿したくなった)

今の時代、僕より優れた競技者がロードマップを示してくれている中で今更こんな記事を書く目的ですが、灰色コーダーの暇つぶしになるような記事を書きたかったからです。同じ立場でなければ刺さらない話もあるのかなーと思いました。昨日茶コーダーなりたてレベルの駆け出しのうわ言なので、鵜呑みにするのではなく、話半分に聞くとか、首肯できるところは同意し、できないとしても、一度咀嚼した上で必要ないと判断し吐き出すみたいな感じで扱ってもらえると幸いです。

なお、本記事では基本的にAtCoder Beginner Contest(俗に言うABC)を想定しています。

結論

B〜D埋めをやろう

戦略の勘所

水色くらいまでには2つの壁があると思っていて、それぞれ一つ超えると緑あたりのパフォーマンスをだせるイメージです。その2つの壁とは

• 4完安定
• 3完早とき

です。 結論から言うと先に後者を目指すほうが、前者を目指すより圧倒的に楽です。また、正直前者は後者を実現するレベルの土台があって初めて相乗的に伸びを感じます。

これは自分の経験談ですが、僕は前者ばかりに力を入れ、後者をなおざりにしていました。具体的には実装力がない状態でAtCoder版蟻本初級編をやっていました。 実力ついたにはついたんですが、振り返ればかなり非効率だったと感じています。

戦略のキモ

まず2〜4完に必要な実力を僕なりに整理する。

• 2完

C++入門 AtCoder Programming Guide for beginners(APG4b)で紹介されている概念をだいたい理解して使える

• 3完

上記に磨きをかけ、C++ Standard Template Library (STL)の主要なデータ構造を適切に使いこなせる。また簡単な蟻本初級編の半分くらいのアルゴリズムを使いこなせる。

• 4完

上記に磨きをかけ、残りの蟻本初級編と+αのアルゴリズム(累積和、しゃくとり法あたり)を理解し使いこなす。

あとは完答数相応の慣れがあれば行けるはずです。

お気づきだと思いますが、2〜4完+それ相応の慣れというのはBCD埋めによって必要十分に身につけることが可能です。

また、正直アルゴリズムはあまりいらないです。正確には難しいアルゴリズム(DP)をやるまえにやるべきことがたくさんあります。C++とデータ構造の理解を最優先してください。強いて言うなら以下のアルゴリズムは必須です。

• bit全探索
• 順列全探索
• dfs, bfs
• ダイクストラ法
• 貪欲法 くらいでよいのでは。それよりもSTLに加えてグラフとかqueue、stack、priority_queueなどを理解し使いこなせるようになる方がよっぽど大事だと思う。

僕がHelloWorldから今日プロをやり直すなら?

第0段階

まずは蟻本をAmazonに発注します。必須です。絶対に買ってください。さもないと天才の提出コードからリバースエンジニアリングでアルゴリズムを理解することになります。僕は蟻本買うお金をケチったばっかりに、名も知らぬ青コーダーの提出コードからbit全探索を0から読み解くとかいう本当に不毛な作業をしたので。

ネットで良質な入門記事たくさんありますが、蟻本の説明はシンプルでコードのわかりやすいし、これという型を身につけるためにはやっぱり必須だと思う。

蟻本来るのを待っているうちにAPG4bでもやっておいてください。こちらの教材が有能すぎるのでC++の本は買わなくてもいいと思います。C++自体に興味を持ち始めたのなら、今の時代は「独習C++」とか江添さんの本とかになるのかなー

いい感じに競技プログラミング向けの教材なので多言語経験ある人もC++をコントローラーに選択するのであればAPG4bは読む価値アリです。多言語経験あれば誇張抜きで2時間あれば十分読み終えられます。あ、僕は自分のPython経験を過信し、これを読まずにコンテストでてた時期があり、毎回C++由来のミスでヒエヒエなっていたので、これもアンチパターンとして紹介しておきます。

本当にプログラミング未経験でHello Worldすら出力したことがない初心者ならAPG4bの練習問題を解いてみても良いかもしれません。結局B埋めするなら必要ない気もします。

第1段階

B埋めをする。(B埋めと並行してSTLのデータ構造への理解を深めていこう。)

この時意識したら良いことは、いかにシンプルに美しくかけるかにプライドを持つことです。きっとすぐにB埋めが虚無に感じるタイミングが来ます。だから無意味に埋めるのではなく、如何にメモリを消費せずに書くか、コード量を減らせるか、計算量を減らせるか、効率的なマクロをどう定義するかなどにこだわってみてください。特に僕の場合は、出される問題に対してvectorを使わなかったらどうなるかみたいなことは常に考えていました。その問題で提出されている誰のコードよりも美しいコードを提出するように心がけよう。

ここで拘った経験は将来必ず報われます。特に緑上位Diffあたりから想定解のアルゴリズムそのものが複雑になってしまい、通ればなんでもヨシなオレオレコードでは負えなくなってしまう日が来ます。

コードへの拘りに突然飽きてしまう(これ以上改善の余地ないんじゃね?と感じてしまう)タイミングでC埋めをしましょう。

第2段階

C埋めをする。

まずは蟻本(初級編)をやりましょう。注意点として動的計画法という初心者殺し的なアルゴリズムの存在です。こいつは言ってしまえば、RPGのはじまりの街すぐ近くにいる強いレアモンスターみたいな感じなので、この段階では理解できなくても気落ちせずに次に進んじゃっていいと思う。茶色灰色って言っているうちは本当にコスパ悪いので。動的計画法とは漸化式のことなので、こういう問題を解くためにはこういうふうに漸化式を立ててその情報を保存しているんだーくらい理解できてればよいのかなと思います。

しかし、素通りOKなのは、蟻本初級編で紹介されているような、情報を2次元以上の配列で保存するバージョンの動的計画法のことを暗に言っています。一方で、あまり意識されることのない、一次元で保存するversionも存在します。そちらはマスターしておいたほうが良いです(俗に言う累積和とかがそれの一種です)。一次元verは他に必要なアルゴリズムより簡単なのでそんなに恐れなくて大丈夫です。というより無意識に書いちゃってると思います。

本当に使いこなせていれば(ここのレベルは落穂広いで簡単に解説します)理屈上水色中間くらいのDiffであれば解けるだけの知識があると思います。あとは慣れだけです。解説ACも全然いいと思うので場数を踏みましょう。

あとは蟻本初級編復習とC埋めのサイクルを高速で回していけば成長した実感が得られると思います。僕が精進がレートに現れ始めたなと感じたのがこのあたりです。

あ、あとここでも提出コードの美しさには拘りましょう。特にデータ構造に対しては徹底的に拘りましょう。自分が組みたいアルゴリズムに対してどのデータ構造が最適なのか、次善はどれか、vectorのメソッドを把握しているかなどは他の提出者の解答をみながら研究しましょう。僕のおすすめは順位表をもとに最速提出〜5番目提出あたりのコードを読んでどんなデータ構造を使っているのかを見て勉強することです。アルゴリズムは割と似通っていても、採用しているデータ構造に違いがあったりして結構面白いです。

第3段階

D埋めをする。

最新問題からC埋めしていると、80番台くらいから難易度が下がるのを感じると思います。80番台以前のCの水色Diffも割と解けるようになると、飽きが来始めると思うのでD埋めにシフトするのもありだと思います。 ぶっちゃけ上記のC埋めを行っているうちに精進の勝ちパターン(どういうことを意識したら精進がレートに反映されるか)が定まると思うのであとはその直感に信じていろいろやれば勝手に実力がついていくと思います。

以上茶色レベルまでの成長戦略でした。

落穂広い

1．Q. 第2段階まではアルゴリズムの勉強をしなくてもいいってこと?

A. そんなことはないです。0〜4段階をこなすためには必要なスキルセットがあり、しかもそれらを抜け漏れなく割と高い水準まで極めなくてはならないと思っています。だから〇〇をやるまえに〇〇のアルゴリズムを抑えなければいけない、とかそういうのはないかと。ただ体感としてC++理解>データ構造理解>アルゴリズム理解 の順番で進めたほうが効率がよく、また学んだことがレートにも反映されやすいと思うのでおすすめです。

あと、2でも書きますが、存在を知っているだけのアルゴリズムなんて役に立たないばかりか害にすらなりえます。僕も動的計画法を中途半端に理解した時期はすべての問題が、動的計画法という金槌で叩ける釘に見えていました。

それよりもマスターしたアルゴリズム、データ構造が当座即妙に取り出せて適応できる方が何10000倍も価値があると思います。

2．Q.上記の高い水準とは?

A.自分の実装向けに柔軟にメソッド等を使い分けできるレベルです。

まず前提としてアルゴリズムやデータ構造をVerifyする(例えば露骨にpriorityqueueを使ってくださいと明記してあり、コピペでこしらえたpriorityqueueに打ち込んだらACとれるみたいな)問題はAtCoderには出ません。

(むしろ逆にpriority_queueを想定解と据えておきながらその気配を消すように、文字を無意味に反転させてみたり、負の価値の宝石(?)を捨てれば良いものを無意味にqueueに積ませるなどをして問題に芳香剤を振りまいてきている印象です。)

だから、"存在を知っているだけ"のアルゴリズムやデータ構造に価値はあんまりありません。

目指すべき地点として、アルゴリズムでいうと、コード一行レベルでこのコードがなにを目的にしているのか他人に説明できるようになっていればよいのではと思っています

データ構造でいうと以下のような問題に答えられたらまあ良いのではと思っています。あまり作問センスないですがご容赦を。

• vector<pair<int,int>> でソートする際、まずsecond要素が大きい順に並べ、secondが等価ならばfirstが小さい順に並べる。
• map<int,int>でバリューが大きい順に出力。0から I<N-1 番目の要素をvectorに保存する方法

3．Q.精進の際の解説ACは許容すべき、それとも解説読むのは邪道？

A．It depends on you.(あなた次第です)。僕自身AtCoderは高校時代の数学の模試のようなものであるという感覚で精進しています。そしてその精進はチャート式問題集を解く行為に相当すると思っています。だから、あなたが高校生であったとして、チャート式問題集をどう使うか、あるいはどう使っていたかの成功体験に踏襲すればよいのかなと思っています。

僕は、勉強(特に受験数学は)は死に覚えゲーだと思っています。だから割と早い段階からさじを投げます。それよりむしろ、得く→解説読む→解き直すのサイクルを高速に回すことを意識しています

4．Q.PythonistaもC++に乗り換えるべき?

A．書きやすさの点でも速度の点でも一刻も早く乗り換えたほうが良いと思っています。sortの返し値がvoidだとかいろいろ個人的には気に食わない点もありますが、なんだかんだC++書きやすいです。また、そのように悩むレベルのPython経験があるのであればAPG4bをこなせば競プロ用にコーディングできるC++の実力くらい1日あればつくと思います。解説も大抵がC++で書かれているのでやって損はないです。残念ながらAtCoder王国の母国語はC++です。

また、C++に備わっているマクロという機能を用いることでPython likeなコーディングに近づけることも可能です。この機能を用いることで、僕のコードでは、print("Hello world")とコードに書くと標準出力でHello worldと出力されるようにしています。ループはREP(i,0,N)でfor i in range(0,N)と同様の挙動を実現できるようにしています。

あとは良くも悪くもC++は静的型付けなので思いも寄らないWAなどが起こりにくいです。

その他いろいろな理由があり、C++をおすすめします。

5．最後に、アルゴリズム飛ばしてOKとは言ったけど、これはそのアルゴリズム覚える前にやることたくさんあるよくらいの意味であり、全然必要ないというわけではありません。むしろ動的計画法なんて水色Diffのど本命中の本命です。一応補足を。