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 向き合うようになったので、単純にプログラムに触れる時間が増えました。
また、実務の中で、先輩にレビューしてもらう中で効率の良いコードのまとめ方なんかは身に着けられたかもしれません。
ある半年~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 と出会って、人生が変わりました
初回参加
忘れもしない、初めて参加した時のことを書きます。初参加は2017年5月、ABC062でした
この頃の私は、井の中の蛙 だったので、プログラミング力には多少の自信をつけていました。
そして、AtCoder 「Beginners 」 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, ...)
青色になるまで
水色~青までの時代は長かったので、時系列通りに書いてません。(書けません)
このブログを始めた
何か学習した知見をアウトプットしようと思いこのブログを始めました。
しかし記事にまとめるのって物凄く大変だと分かって、あまり記事を書かずに長らく放置しちゃいました。
今後も思い立った時に書こうと思います。。
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 コンテストに被らないように行動します。
(競プロerと遊ぶときはこの辺は共通認識になってたりして面白いです 13 )
AtCoder 以外のコンテストにもできるだけ出ようとした
AtCoder は土曜または日曜の21時~ で、日本人が参加しやすい時間帯に開催されます。
Twitter のTLを眺めると、AtCoder 以外のコンテストの情報も流れてきて、自分もやろうかなーという気持ちになります。
yukicoder
これは金曜の21時か22時頃に開かれるので、これまた日本人に参加しやすい時間帯になっています。
日本の方が運営しているのでもちろん日本語です!
TLで情報が流れてきた際には大体参加するようにしています。
ロシアで運営されているコンテストサイトです。
曜日が固定されていなくて、頻繁にコンテストが開かれている印象があります。
英語が分かりづらいという評判14 もあります...
海外コンの中では一番参加回数が多いです
歴史あるコンテストサイトです。
1度だけSRM (するめ 、短期型)と、2回マラソン に出ました。
CS Academy
最近あまり聞かなくなった気がしますが、教育的なコンテストサイトです。
UIが格好いいです。
年に一度の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
ABC-D, ARC-D(下の円グラフでB) がもうちょいなので埋めきりたかったです...
ARC-E(下の円グラフでC) をもっと解きます
atcoder _problems
AtCoder Scores
こちらも400を埋めきりたかったです...
500,600,700, それ以上... もまだ増やしていきたいです
atcoder _scores
ここ2ヶ月ぐらいは大きな失敗はなく、レートを上げることができました
今後は青パフォ、黄パフォの頻度を上げていきたいです。
AtCoder Performances
最後に
ここまで長々と書いてしまいましたが最後まで読んでいただきありがとうございました。
最後に2つメッセージがあります
灰色、茶色、緑色、水色で行き詰っている方へ
それぞれのステージで、違った大変さがあると思います。
そして私もそれをよく理解しています。
特に私は大学に入って最初の3年間はプログラミングで挫折していて、自分には向かないとさえ思っていました。
でも結局は好き、楽しいという気持ちが勝って、プログラミングを続けることができました。
私はレート上は、AtCoder と出会って4ヶ月で水色になれました。
よく「4ヶ月で水色ってすごいですね~」と言われます。
しかし、上で書いたように、(あるいは書ききれていないけど)、私には長い期間のバックグラウンドがあります。
実際に4ヶ月で水色になれる人は私から見て凄すぎる人です。
成長のペースは人ぞれぞれ違います。
これは持って生まれたものや、様々な置かれた環境が違うので、仕方ないことです。
ただ私は、今置かれた環境の中で手を尽くしたら、どこまで行けるだろう? というところに興味を持ちました。
どうか、他人の成長速度に惑わされることなく、自分のペースで精進を続けてください。
そして、プログラミングが好き だという気持ちを忘れないでください。
黄色、橙色、赤色、、、を達成された方へ
競技プログラミング を極められていて、とても尊敬・憧れの念を持っています。
そこに至るまでに、現在までの私の数倍、数十倍... の努力を重ねられてきたことも知っています。
私はどこまで追いつけるか分かりませんが、少しでも追いつけるように精進していくので、見守っていてください!
はぁ~~年を越す前に書き終わって良かった、ゴリ~~(><)
皆さん、良いお年を、お過ごしください!!
脚注: