More than 1 year has passed since last update.

2年かけて AtCoder 緑色になって思うこと

Last updated at 2022-07-13Posted at 2022-07-10

先日の AtCoder Beginner Contest 259 において、入緑したことを報告す。

この記事では、センスのないおじさんプレイヤーがいかにして2年以上かけて緑コーダーにたどり着いたか、そしてそこから考える自分にとっての競プロの意義と姿勢のようなものを語ることにフォーカスしたい。客観よりも主観に重きを置いているため、緑コーダーを目指している方もこれを参考にするというよりは精進の間の箸休め的な感じで読んでいただければ幸いである。

自己紹介

数学に関しては、一応数Ⅲ数Cは履修したが、やや苦手であった。
センターテストでもトータル 113 点(200点満点中)というスコアを叩き出している。
大学では有機化学を専攻し、大学院在学中の24歳の時、研究や就職活動が思うように進まず、何も考えず院中退を決めた。当時ニコニコ動画が流行り出した頃で、ゲーム動画をよく視聴していた私は、ふと「ゲームを作りたい」と思うようになった。ネットで調べたところ、プログラミングという手法によってゲームが作られていることを知る。書店で書籍を購入した。それは「やさしいC」というC言語の解説書であった。

翌春、ゲーム専門学校にて2年間勉強し、運よくゲーム会社に就職することができた。開発では C++ を使用した。
その後、SIer や Web 系の会社でいずれも主に開発に携わってきた。

現在は6社目となり、プリセールスとして主にお客さまのビジネス課題を聞いてそれに対する MVP の作成を担当する。デリバリーは行っていない。

得意言語は JavaScript で、好きな菓子メーカーはブルボンである。
フルマラソンの自己ベストは 2時間32分。

AtCoder および競プロに取り組む理由

そんな自分がなぜ35歳(当時)にもなって AtCoder を始めたか。
それは GAFA への転職という崇高(無謀)な目標を抱いていたからである。
そんな時に出会ったこの記事で紹介されていたのが、まさに AtCoder であった。

始まりこそそんな形ではあったが、始めてみると面白く、問題を解くこと自体に楽しみを覚えた。
もちろん鍛えたアルゴリズム力を転職以外にも、普段の業務において活用できれば良いが、それよりはむしろ純粋にゲーム感覚で楽しんでいた。だからこそ成果が出なくても１００回近くもコンテストに参加し続けて来れたと思う。

これまでの取り組み

使用言語: C++, JavaScript

やはり C++ 言語をおすすめする。STL ライブラリなど一通りのデータ構造を扱う環境が揃っていることも挙げられるが、他の言語と比較して解説や他人の解法が豊富だからというのが一番の理由である。

初参加コンテストからの変遷を4期に分けてみた

黎明期: 2020/6 ~ 2021/1

コンテストに参加するのみで、解説動画はほぼ見ず、過去問も意識しては解かなかった。Qiita の記事を決めうちで読むことが多かったかも。

鍛錬/第1成長期: 2021/2 ~ 2021/8

過去問をちゃんとこなそうと思い、主に A~D 問題を順に遡って解き始めた。
また、メインの使用言語を JavaScript から C++ に変更した。
アルゴリズムに触れない日の方が少なかったと思う。
そのような感じで二ヶ月ほど取り組んでいると効果が出始め、2021年3月に入茶した。
また、7月には初めて本番で D問題を正答することに成功した。
その後も C 問題を安定して正答できるようになり、レーティングも順調に上がった。

停滞期: 2021/9 ~ 2021/12

このまま緑に突入できるかと思った矢先、失速した。
おそらく地力が足りていなかったのであろう。
この少し前から精進量が減っていたことが多いに関係していそうである。やはりものを言うのは練習だ。

第2成長期: 2022/1 ~ 2022/7

もう一度基礎から見つめ直すべく、過去問および他の競プロサービス¹を利用して問題を解くことを心掛けた。
参加96回目にして、悲願の入緑を果たした。²
また、競プロに対する姿勢や考え方の多くはこの時期に形成された。

入緑までにやったこと

教材

過去問(AtCoder Problems)
- 言わずもがな、AtCoder で出題された過去問を解くことから全ては始まる。
LeetCode¹
- AtCoder が数学色がやや強いのに対して、LeetCode は企業がコーディング面接で出すような（というか実際の問題も含まれていると言う）問題で構成されているため、非常に解き甲斐がある。

アルゴリズム

私が取り組んだアルゴリズムに関して、その習熟度と所感について記す。(粒度はバラバラである)
無論、「実装できる = 正答できる」ではなく、あくまでもアルゴリズムの実装のみに焦点を当てている。

アルゴリズム	サブカテゴリ	自分のレベル(○/△)³	判断基準、ポイントなど
累積和
	一次元	○	N(データ数)が単調増加(減少)で、データセットに対して処理を行うクエリに複数答える必要があるは考える。
	二次元	△
探索系
	bit全探索	○	N が小さい時は考える。
	二分探索	○	最大最小値を求める問題で、$N\leq10^9 $~$ 10^{18}$ くらいの時で二分探索の条件をうまく設定できそうな場合は考える。データ自体に二分探索をかけると言うよりは、ある対象の数に対してその範囲を絞っていき、最大最小値をスポットするイメージ。
	深さ優先探索(DFS)	○	グラフ問題は、見たままグラフ問題の時もあれば、裏に隠されている時もある。少なくとも前者の場合はベースは何も考えなくても構築できるレベルにしておき、題意をどのように反映するかがポイントだと思う。
	幅優先探索(BFS)	○	同上
整数問題
	約数、素因数分解	○
	最大公約数, 最小公倍数	○
組み合わせ
	順列	○	Nが十分小さい時($N\leq10$)で全順番のパターンを探索したい時に考える。ちなみに N=10 で 3,628,800 通りある。C++ の場合、next_permutationが便利。
	重複組合せ	△	「X+Y+Z=10 を満たす非負整数の組みはいくつある？」のような場合⁴。実際の問題ではこの通りには出てこないので、題意が重複組回せのことを言っているのを判断するのが難しかったりする。
その他
	DP	△	単純なものの実装のみ可能。ナップサック問題くらいのレベルだと本番で正答することは難しい。さらには問題が DP で解くべきであることを判断するのが難しい。
	スライディングウィンドウ	○	データ($N\leq10^5$)が単調増加(減少)で、そのうちの K 個ずつ順番に処理するような場合に考える。
	しゃくとり法	○	上のスライディングウィンドウの K が可変バージョン。意外と実装ミスするので気を付ける。
	優先度付きキュー	○	データ($N\leq10^5$)に対して複数のクエリで処理をかけていくシミュレーション問題の場合疑う。毎処理ごとにデータがソートされる必要がある場合は高確率でこれ。

細かいところでは他にもあるかもしれないが、ざっと上げるとこのようになる。
逆に言うと、特定のアルゴリズムを使う系でこれ以外の問題は解けないと言っても過言ではない。

コンテストでの取り組み方

自分の戦略を立てる

速解き $A+B+C$ or 確実に $A+B+C+D$
エンジニアとして考えた場合、極端に偏るのではなくバランスが良い方がベターと思う。

紙と鉛筆を用意する

問題を読んだら、まずは紙に書くことを心がける。頭の中で GO サインが出て初めてキーボードに触れる。
A問題のよほど簡単な問題などでない限り、チョロでも良いので何か書く。理解しているなら30秒ほどで書けるはず。
コーディング面接では単に正答できたら良いのではなく、インタビュアーとコミュニケーションしながら解放を見つけ解いていく。ざっくり実装内容を紙にかけないとそれができない。

順位表を見ない

問題の難易度を確認するために順位表での正答者の数や時間を確認するという手段があると聞いている。
これは本質ではなく小手先のテクニックなので強くおすすめしない。
目の前の問題に集中するべきである。

わらかない問題は飛ばす

しばらく考えても正答できない問題は、一旦保留して次の問題に移る。
ただし、「前の問題が解けなかった」という負の感情をコントロールするのが難しい（私の場合）ため、要注意。
逆に、これで次の問題が正答できると、自分の戦略の幅を広げることになるので非常にポジティブである。

やたら過去問を検索しない

経験上、「過去に同じような問題があったからちょっと確認したいな」と思うことが何回もあった。
ただし、実際はそれを行なっても良い結果に繋がることは少なかったように思える。
場合によりけりだが、その過去問のコンテキストを思い出して解答を見て今回の問題に置き換えて、、とオーバーヘッドの高いことを行うくらいなら、その時間を今回の問題に注ぐ方が良いのではと思っている。

最後の最後まで考える

諦めない。
私はコンテスト終了2秒前に AC したことがある。
これでパフォーマンスが大きく変わることはないかも知れないが、脳にできる限り負荷をかけて絞り出すと言うことは next step に行くために重要なのではないかと思っている。

レーティングが落ちた時

自らに問いかけることで、反省を次回に活かす。

解けなかったのはなぜか？

解法を思いつき、実装もできたが、正答できなかった
- 細かいところでどこが適切でなかったかを確認し、その原因を潰す
  - オーバーフロー、エッジケース、凡ミス etc
解法は思いついたが、実装仕切れなかった
- 正確に実装できるように練習する
解法が思いつかなかった
- しょうがない。その解法を勉強する

解けたとしても、時間がかかったのは、どこでつまづいたからか？

実装に手間取った
- 必要なアルゴリズムを使いこなせていないので、試行錯誤だったから
解法を思いつくのに手間取った
- 練習が足りていない可能性がある。題意から解法を導く訓練する。

真面目に反省ばかりしていてもつまらないので、順位表を眺めて自分より下位の人の中から、ランクが自分より上位の人を探し、「こんな凄い人でもパフォーマンスが悪いことはあるんだ」と気持ちを切り替える。

コンテスト後

最近は、正答した問題のリファクタリングを行っている。
目的は、理解をより強固なものに昇華させることと、本番中のコーディングは最適化されていない場合が多いため、これをじっくり最適化することで実力アップを目指している。

その他こだわり

スニペット等はあまり用意しない

レーティングを追い求めるあまり、さまざまな処理を事前準備しておくのはあまり好きではない。
例えば約数列挙や素因数分解のスニペットに頼っていると、いざ空で書かないといけない状態で書けなくなるようになるのを恐れている。
少なくともたまにはコンテスト以外でも良いので、忘れない程度にはコードを眺める必要があるのかも知れない。
流石に Union-Find を毎回実装するのは骨が折れると思うので、最終的にはどこに線引きをするかの問題である。

競プロ好きを公言する

私は茶色、または灰色コーダーの頃から周囲に「競プロやっています」と公言していた。
そうすることで自分に発破をかけるつもりもないのだが、本当に問題を解くことが好きで楽しかったから、その気持ちに素直になったまでだ。
レベルに関係なく、何かに打ち込めることに誇りを持っていた。

コンテストは極力休まない

ご時勢的に夜9時以降飲み会などは前ほどはないかも知れないが、土日の夜は予定が入りがち。
コンテスト中の緊張と集中した中での1時間40分は、他の何を持ってしても変えられない貴重なものなので、できる限りコンテスト参加が望ましいと考えている。

今後

何年かかるかわからないが、できれば水色を目指したいと考えている。
今の取り組み方だと流石に頭打ちすると思われるので、やり方を変える必要がある。
また、他にも勉強したいことがたくさんあるため、それらとうまく付き合いつつアルゴリズムしていきたい。

Qiita に競プロ関連の記事をいくつかあげているため、紹介させていただきたい。

LeetCode(https://leetcode.com/) ↩ ↩²
ランキング検索をこの条件(Rating:800-850)で行いコンテスト参加回数で降順ソートすると、20前後/1482 番目に位置することからも、私がいかにポンコツであるかがご理解いただけるだろう。 ↩
○: 何も見ずとも実装可能 △: ネットで検索しながら実装可能 ↩
このような記事は大変有用である:https://manabitimes.jp/math/1101 ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up