ごりちゃんがゆく

競プロをするゴリラの精進記録

AtCoder青になるまでの軌跡


2018年12月29日のAGC030 (=今年最後のAtCoderコンテスト)にて、
ついに、ここ1年7ヶ月力を注いできたAtCoderで青コーダーになりました!!!! 上のレートグラフからも苦労の様子がある程度わかりますが、本当に紆余曲折ありましたので久々にブログに記していこうと思います。

前半はAtCoderに出会うまでの自分語り的なことも多少書くので、 興味がなければ適宜読み飛ばしてください(><)


目次


(推定) 茶色になるまで

まだAtCoderには出会っていない頃の話ですので(推定) と付けました

情報系学部を卒業した

大学をギリギリ卒業しました。成績は下の下の[検閲により削除] でした。
(恥ずかしい記事ですが下記に当時の状況を少し書いています) 1
競プロと出会うまで(前編) - 30歳で競プロに目覚めた霊長類のブログ

学ぶのには最適な環境だったはずなのですが、学業について行けず、諸々やる気も出ずに、かといって休学などもせず 無駄に学費をつぎ込んで2 虚無をして過ごしてしまいました。

記憶に残っているのはダイクストラ法を授業で教わったときはなんか凄い、面白いって思いました
当時はこれを実装するなんて思いもしませんでしたが、今ではスラスラと書けるぜー当時の自分よ!

1年ぐらい趣味で自分なりにコードを書いた

これは大学に在籍していた最後の1年ぐらいのことなのですが、ようやくこの時期になってプログラミングって楽しいって思えたんですね
(プログラムを書くお仕事をしたい、とハッキリ思ったのもこの時期でした)
自己流なので誰かにレビューしてもらうわけではないですが、下のようなものを書いたりしていました

CUIでオセロできるやつ

自分 vs. 自分で対戦したり、自分 vs. AI で対戦できるオセロゲームを書きました
AIといってもαβ法みたいなことは挑戦していなくて、各マスに固定の優先度がつけられてるだけのシンプルなやつでした(笑)

数独ソルバ

数独の解を見つけるプログラムをこの時期に書きました。
条件分岐と配列をすごく駆使して、えぐいスパゲッティコードになっていたと思います。
このとき、実は今思うと自己流の深さ優先探索を書いていたんじゃないかと思います。
自明でないマスはとりあえず仮定を置いて、そのマスに深さ1の仮定だよとマークをつけて、さらにその仮定でマスが埋まりきらなかったら深さ2の仮定を置く...
みたいな感じだったと思います。
自己流なので、当然再帰なんて使おうとも思いませんでした。
今思うと当時の力でよく実装できたなーという気持ちです (ただし1ヶ月かかりましたが...)

こんな感じで自分なりにコードを書いていた時期がありました。
成績自体は下の下の... でしたが、プログラミングのいろはというか、if, for, 配列... をゴリゴリ使った手続き的な処理は、 CS学科の中でも中程度には書けるようになってたんじゃないかなーと思います[要出典]。
この頃の自分にAtCoderをやらせたら推定茶色ぐらいかなーと思っています。(実装は遅かったので...)


(推定) 緑色になるまで

なんだかんだで就職しました。このセクションもAtCoderに出会う前のことです

ソフトウェアエンジニアとして実務経験を積んだ

これは競プロ力とはあまり直結しないのですが、単純に趣味でゆるーくコードを書いていたところから、お仕事で毎日8時間3 向き合うようになったので、単純にプログラムに触れる時間が増えました。
また、実務の中で、先輩にレビューしてもらう中で効率の良いコードのまとめ方なんかは身に着けられたかもしれません。

Project Euler を90問ぐらい解いた

ある半年~1年の間ぐらい、 Project Euler 埋めにはまっていたのを思い出しました。
最初のころは完全自力で解くのを目指していましたが30問解いた辺りから辛くなったので、どうしても分からなかったらググって色んな人の解法を見るようになりました。今の精進方法と同じ!
今思うと、累積和や簡単なDPのような解法は自力で発明していたように思います (当時はそれが名前のついた定跡であると知りませんでした)
ただ、競プロのように正解までの早さを競うわけではないので、めっちゃ(ものによっては1週間とか)考えて編み出したりしていました
にぶたん(二分探索・バイナリサーチ) は知っていました。

素因数分解させたり、素数を列挙させる問題がやたらと多かった4 ので、競プロでよくある整数問題に対する考え方もこのときに多少磨かれた気がします。
あとはLU分解を調べて実装して、任意の有理数が係数になっているn元連立一次方程式を解けるようになって感動した記憶があります(これは競プロで出なさそう?)

90問ぐらい解いたところで行き詰って、それから熱が冷めてしまったのですが、思い出したのでまた久々に再開しようかな ^^

CODE VS 5.0 に出た

2016年3月ごろの、CODE VS 5.0予選に出ました5
同僚がたまたま話題に出していたので、いっちょやってやるか!という気持ちで出てみました。
このとき、キャラクターを動かす場所の候補を探すのに、初めて幅優先探索を書いた記憶があります。
最終日にヒューリスティックなパラメータを怪しくいじったのが意外と善戦して、全参加者の真ん中ぐらいの順位にはなれました。
CODE VSはリアルタイムで他のユーザーと対戦できて、対戦のようすがグラフィカルに表示されるので、やたらと楽しかった記憶が強いです。
6.0があるとしたら有給を何日か使ってでもやりたいなーと思っています6

AtCoderと出会うまではこんな様子でした。
この頃の自分にAtCoderをやらせたら推定緑色ぐらいかなーと思っています。


AtCoderとの出会い~水色になるまで

AtCoderと出会って、人生が変わりました

初回参加

忘れもしない、初めて参加した時のことを書きます。初参加は2017年5月、ABC062でした
この頃の私は、井の中の蛙だったので、プログラミング力には多少の自信をつけていました。
そして、AtCoderBeginners」 Contest だと思って舐めていました。
言語は、当時一番慣れていたJavaではなく、独学で少し触ってみただけのPythonで挑みました。(心境的には舐めプに近いです)
結果は、4問中の2完で、これほどまでに通用しないのか、と凹みました (全部解けて当然とぐらいに思っていたので)
が、同時に 俺はこんなもんじゃねぇ~~!! という、熱い気持ちが沸き上がってきました
これが、私に火をつけたきっかけになり、以降は毎週のAtCoderコンテストでレートを上げることを目標にしました。

ABC全完を目指し、ABC埋めをした

とりあえず、AtCoder Problems を参考に、手当たり次第に過去問をやりました。
言語は、引き続きPython を使いました7
ABCのA~C問題は絶対解くつもりで解いて、解けたらD問題にも挑戦していました。
CやDには自力で解けない問題も多かったので、逐一解説を見たりしては、身に着けていました。
それをがむしゃらに、日によっては2セットや3セットや4セットやりました。(多分、この時期が一番新規ACを稼いでいた)
公式のEditorial が数学的な記述や グラフ理論の言葉を使った記述が多くて、読み解くのに苦労していました。(これは今は多少慣れてきましたが今でも苦労します^^;)
こんなとき先人の書いてくれたブログ記事たちはとても理解の助けになりました。
初めて全完できたときの達成感、気持ちよさは今でも覚えています。

蟻本を買った

プログラミングコンテストチャレンジブック (通称:蟻本) は競プロerのバイブルだと知って、購入しました。
1ページ1ページに情報が凝縮されているので、理解するのに1時間以上かかるページも存在しました。
2017年8月頃にちまちま読み進めて、水色になる前に初級編は読了したと思います。8

水色になるまでに学習したアルゴリズム、考え方

  • 計算量・オーダーに関する感覚
  • list, set, dict, deque(双方向キュー), heap(優先度付きキュー) を使いこなす
  • グラフ理論の基礎
  • ソートして貪欲
  • ソートして二分探索
  • しゃくとり法
  • 累積和、いもす法
  • DFS、BFS
  • ダイクストラ、ワーシャルフロイド、ベルマンフォード
  • DP
  • Union-Find, クラスカル
  • 二項係数のmod 1e9+7 を求めるかわりにmodの逆元を繰り返し二乗法で求めるやつ
  • (Pythonの) itertoolsの便利そうなやつを抑えておく (permutation, combination, product, ...)

青色になるまで

水色~青までの時代は長かったので、時系列通りに書いてません。(書けません)

このブログを始めた

何か学習した知見をアウトプットしようと思いこのブログを始めました。
しかし記事にまとめるのって物凄く大変だと分かって、あまり記事を書かずに長らく放置しちゃいました。
今後も思い立った時に書こうと思います。。

Twitterを始めた

DDCC2017の決勝に進めたのがきっかけで、Twitter を始めました。
畏れ多くも1000名を超える方にフォローいただいています。ありがとうございます。9
特にコンテスト後に解法に関する議論が活発に行われているのを知って、軽い情報収集の目的がありました。
後述しますが、Twitterがきっかけでリアルの交流も多く生まれて、単なる情報収集にとどまらない、期待以上のものが得られたと感じています。

1日1ACを軸に、AtCoderの過去問を埋めていった

AtCoder Problems に、Streak という指標があります。
AtCoderの問題を連続で何日新規ACしたか を表すのですが、2018年1月3日~2018年12月30日現在まで、362日継続中です
この 「Current Streak を切らさない」を1つの方針として、2018年は精進していました。
この方針の精進方法については、向き不向きというか、賛否両論がある10 のですが、結果として私にとっては良かったと思います。
理由としては、常に頭の中に解きかけの問題をいくつか置いておけるというのがあります。
どういうことかというと、Streakを長く続けるためには意外と戦略的に考える必要があって、例えば時間的・体力的に厳しい日なんかは軽めの問題で繋ぎたいので、軽めの問題は温存しときたいという気持ちになります。
すると、普段はできるだけ軽めの問題以外に目を通すようになって、それらの解法を考える習慣が生まれます
大体私は、新しい過去問に目を通したときに「すぐ解けそう」「ちょっと考えれば解けそう」「かなり大変そう」の3つぐらいに分類しています
時間的・体力的に余裕のある日は「かなり大変そう」な問題に挑戦しますが、そうでない日のほうが普段は多いので、「すぐ解けそう」「ちょっと考えれば解けそう」の問題は割とストックしてあります11
その過程で多くの問題に目を通したり、実際にACしたり、「かなり大変そう」な問題の考察にチャレンジしたりしてきました。
このStreakという数字は今後もモチベーションを保つために生きる数字だと思っています。

PythonのLanguage Ownerになった

これは1日1AC以上... をコツコツやってきた結果の副産物ですが、2018年9月頃、「Pythonで一番AtCoderのAC数が多い人」になりました
(これまたAtCoder Problemsさんで言語別に集計されています12)

AtCoderの過去問は2000問以上あるうえ、「すぐ解けそう」に分類される問題も多く解いてきたので、個人的にはあまりすごい事と思っていないです。
でもこういう形で可視化されるのは非常にモチベーションになりました。

AtCoderコンテストには欠かさず出た

これは私ぐらいのモチベーションがあれば自然とそうなってしまうのですが、AtCoderのトップページ左側に「予定されたコンテスト」という一覧がありまして、 そこに表示されているコンテストには冠婚葬祭レベルの理由がない限り大体出ていました
何なら旅行中にも出ていました^^;
休日は基本AtCoderコンテストに被らないように行動します。
(競プロerと遊ぶときはこの辺は共通認識になってたりして面白いです 13)

AtCoder以外のコンテストにもできるだけ出ようとした

AtCoderは土曜または日曜の21時~ で、日本人が参加しやすい時間帯に開催されます。
TwitterのTLを眺めると、AtCoder以外のコンテストの情報も流れてきて、自分もやろうかなーという気持ちになります。

yukicoder

これは金曜の21時か22時頃に開かれるので、これまた日本人に参加しやすい時間帯になっています。
日本の方が運営しているのでもちろん日本語です!
TLで情報が流れてきた際には大体参加するようにしています。

Codeforces

ロシアで運営されているコンテストサイトです。
曜日が固定されていなくて、頻繁にコンテストが開かれている印象があります。
英語が分かりづらいという評判14もあります...
海外コンの中では一番参加回数が多いです

TopCoder

歴史あるコンテストサイトです。
1度だけSRM(するめ、短期型)と、2回マラソンに出ました。

CS Academy

最近あまり聞かなくなった気がしますが、教育的なコンテストサイトです。
UIが格好いいです。

GCJ

年に一度のGoogleが主催する世界的にも大規模なコンテストです。
2018年はqualは突破できたのですが、Round1A~Cはいずれも通過できませんでした。
2019年はRound2まで行ってみたいですね...

Paiza

これはコンテストとは違う形態ですが、日本語の問題が充実していて、いつでも参加できます。
ただ、ネタバレ禁止の特性上、分からなかったときに復習する手段がないのが難点です。。
水色がSランク相当という情報を得ていたので、Sランクは取りました。

ゴリラジオ体操を始めた

2018年5月頃から、AtCoder Virtual Contest さんをお借りして、ゴリラジオ体操 なる早朝バーチャルコンテストを定期開催しました。
実は4月頃、上述のCodeforcesやCSAといった海外コンに積極的に出ようとした結果、深夜のコンテストが多くて寝不足になり、体調を崩してしまいました。
そんな経緯があって、海外コンに出るのは基本諦め、その代わりに普段の生活の中で無理なく精進できる方法はないだろうかと考えた結果、ラジオ体操形式にして毎朝バーチャルコンテストをやるのはどうかと思いつきました。
実際それがうまいこと普段の生活の中に習慣化できて、2018年年末時点で157回 15、いまだにこの習慣が続けられています。

有り難いことに、一緒に精進してくれるゴリラジ勢がいらっしゃって、毎朝10~20人ぐらいの人たちが参加してくれています 16
めちゃめちゃ朝早い(今は6:25~開始) のに、この人数に参加してもらえるのはビビります。
心理的には、これだけの人たちが参加してくれているから、ここまで続けられたという側面もありますね。
いずれにしても皆さんに感謝です。

ゴリラジ以外にも不定期にバチャを立てたり、他の人が立てたバチャを見つけたらお邪魔しているので、水色時代に軽く200回以上はバチャをしています。

オンサイトのイベントにもできるだけ出た

モチベーションの源です。オンサイトコンテストの機会は何度でも行きたいです。

DDCC2017 決勝

初めてのオンサイトでめちゃめちゃモチベーションを得られました。
詳細レポ→ DDCC2017本戦に参加してきました!! - 30歳で競プロに目覚めた霊長類のブログ

RUPC2018

立命館大(滋賀県のキャンパス) に3日間、お邪魔しました。
年齢や所属の縛りがなかったので、社会人である私も参加できる貴重な機会でした。
(平日なので社会人は少なかったですが...) ICPC形式なので、3人1組のチームで問題を解きました。
これをきっかけにTwitterで接していた人たちと仲良くなったり色々出会いがありました。

ACPC2018

3日間会津大(福島県) にお邪魔しました。
RUPCと同様、年齢の縛りがないので私でも参加できました。
貴重な機会でとても刺激になりました。
RUPCのときは一人宿だったのですが、ACPCでは8人ぐらいで民泊しました。
また、この時もたくさんの出会い or 再会がありました。
帰りに温泉にも寄れて楽しかったです

Future Meets You Contest (ふみこん)

Future社にて、社会人限定のオンサイトコンテストがありました。
3時間でマラソン形式の問題を解くスタイルでした。
ラソン形式は慣れていないのですが、たまたま方針が良くて、20数名中4位の結果でした。
(賞金が3位からだったので惜しい)
懇親会でも交流させていただきました。
また、帰りにエントランスホールから皆でARCに参加したのもいい思い出です(笑)

競プロer達と交流した

交流の機会はできるだけ大事にしました!
競プロのモチベーションを得られる、人生の充実感を得られる... 等 様々な恩恵がありました

CombNaf, CombGig, CombMof

いずれも高校生が主催していて若い方が多く集まるLTイベントでしたが...
発表内容がどれもすごくて刺激になりました。
参加者がいずれも数十人規模で、二次会まで参加しています
GigとMofでは二次会の幹事をさせていただきました (自然とそんな流れになっていました)

ビアガーデン

企画としては初めての私主導だったので思い出深いです
Twitterで何気なく「ビアガーデン行きたいなー」と呟いたら、行きたい!という声が意外と上がったので決行の運びになりました

競プロキャンプ2018

8月末に、千葉へ競プロer達との交流キャンプに行ってきました。
これも外せない思い出の一つです。
競プロer達と泊ったのはこれが初めてでした。
たくさん交流できて良かったです。
何と2019年は私が幹事をやることになったので、うまく行きますよう、皆さんよろしくお願いします。

和歌山旅行

tatuyanさんが企画してくれました。
駅猫を見に行ったり、浜焼きバーベキューしたり、温泉入りまくったり... 素敵な思い出でした。
旅行の習慣がなかったのですごく新鮮で楽しかった!


...その他、書ききれませんが、勉強会、もくもく会、〇〇会、××会、その他たくさん交流の機会がありました
AtCoderを始める前はこんなに交友関係が広がるとは思いもしなかったので、(競プロのレートとは別の) 思わぬ収穫でした!!
2018年、(2017年も) 仲良くしてくださった皆さんありがとうございます。

ゴリラのぬいぐるみを買った

競プロキャンプ2018の行きにUSB扇風機を買おうと立ち寄ったドンキで出会いました
ゴリたろうと言います
競プロキャンプの後も何かと活躍してくれました。

青になるまでに学習したアルゴリズム、考え方

実は上のほうに挙げた、水色のときに学習したアルゴリズムたちで青色にはほぼ足りています
足りないのはスピードだとある時に認識して、毎朝のゴリラジオ体操で、早解き力を鍛えました。

以下は学んだけど類題を多く解いていないのであまり使いこなせていないかも (><)

  • 二部グラフの判定 →私の記事
  • 包除原理
  • LCA, ダブリング
  • 行列累乗
  • 最大流最小カット(フロー)
  • BIT, セグ木
  • 幾何いろいろ、文字列いろいろ

青色達成時のスナップショット色々

AtCoder Problems

AtCoder Problems

ABC-D, ARC-D(下の円グラフでB) がもうちょいなので埋めきりたかったです...
ARC-E(下の円グラフでC) をもっと解きます

f:id:prd_xxx:20181230225038p:plain
atcoder_problems

AtCoder Scores

AtCoder Scores

こちらも400を埋めきりたかったです...
500,600,700, それ以上... もまだ増やしていきたいです

f:id:prd_xxx:20181230225107p:plain
atcoder_scores

AtCoder Performances

ここ2ヶ月ぐらいは大きな失敗はなく、レートを上げることができました
今後は青パフォ、黄パフォの頻度を上げていきたいです。

AtCoder Performances

最後に

ここまで長々と書いてしまいましたが最後まで読んでいただきありがとうございました。

最後に2つメッセージがあります

灰色、茶色、緑色、水色で行き詰っている方へ

それぞれのステージで、違った大変さがあると思います。
そして私もそれをよく理解しています。
特に私は大学に入って最初の3年間はプログラミングで挫折していて、自分には向かないとさえ思っていました。
でも結局は好き、楽しいという気持ちが勝って、プログラミングを続けることができました。

私はレート上は、AtCoderと出会って4ヶ月で水色になれました。
よく「4ヶ月で水色ってすごいですね~」と言われます。
しかし、上で書いたように、(あるいは書ききれていないけど)、私には長い期間のバックグラウンドがあります。
実際に4ヶ月で水色になれる人は私から見て凄すぎる人です。

成長のペースは人ぞれぞれ違います。
これは持って生まれたものや、様々な置かれた環境が違うので、仕方ないことです。
ただ私は、今置かれた環境の中で手を尽くしたら、どこまで行けるだろう? というところに興味を持ちました。

どうか、他人の成長速度に惑わされることなく、自分のペースで精進を続けてください。
そして、プログラミングが好きだという気持ちを忘れないでください。

黄色、橙色、赤色、、、を達成された方へ

競技プログラミングを極められていて、とても尊敬・憧れの念を持っています。
そこに至るまでに、現在までの私の数倍、数十倍... の努力を重ねられてきたことも知っています。
私はどこまで追いつけるか分かりませんが、少しでも追いつけるように精進していくので、見守っていてください!


はぁ~~年を越す前に書き終わって良かった、ゴリ~~(><)
皆さん、良いお年を、お過ごしください!!


脚注:


  1. 当ブログ最初の薄っぺらい記事です。長らく(後編)が書かれていませんが、当エントリが(後編)の役目を果たすつもりで書きます

  2. 留年した超過分は私が全部負担する約束で、ついこの間全額完済しました

  3. ずっと実装だけさせてくれるというわけでは全然ないですけど

  4. 当時はエラトステネスのふるいを座圧して定数倍高速化して喜んでいました

  5. これは広義の競プロではあるので、30代になって競プロを始めたと宣言した気がしますが、厳密には嘘です (当時29歳) まあそんなことは置いといて、当時の順位表を今見ると知っている名前が多くて楽しいですね

  6. と思いつつ、ずっと開催されないので首を長くして待っています

  7. もともとLL言語をさくーっと書ける人に憧れがあったので独学でPythonを始めていて、毎週のAtCoderPythonに慣れることを最初は目的の一つと考えていました

  8. 初級編といっても、生半可な覚悟では読み切れない難しさですよね。。ちなみに青になった現在、中級編を読了していません。。2019年は全部読むぞ!!

  9. 皆さん、何にそんなに惹かれるんでしょう…?? というのは自意識過剰ですかね。。理由はどうあれ、フォローいただいているのはありがたいことです。

  10. 否定的な意見の例… Streakを繋ぐことを目的にしてしまうと精進強度の低いAC(虚無と呼ばれたりします) をすることになり必ずしも役に立たない、AC継続にとらわれてしまい他のことができない、等

  11. 実はそうでもなくて最近カツカツしてきたかもしれない

  12. 裏話があって、初期のころは訳合ってPython2系で提出していたので、Python2とPython3で分けて集計されていたらこうはなっていませんでした。合算してくれてありがたいです

  13. 急にコンテストが生えることもあるので、土日の夜に企画を立てづらいというのはちょっとあります。。「予定されたコンテスト」欄にはできるだけ早めに予定を掲示してほしい… (願望)

  14. “Read"forces なんて呼ばれてたりしますね… 私も何度も誤読で時間を溶かしています (ただこれは私の英語力の問題な可能性がある)

  15. 土日祝日は好きな時間に起きたいので途中ではずしました。平日に、出社前にやるのを習慣化しました。

  16. 最近10名を切るぐらいに減りつつあります。(寒くなったし朝オフトンから出られないのは無理もないです) (というか出てる人すごい)