AtCoderで青になりました、というAtCoder色変記事である。
- 手短に自己紹介
- レート推移、各種進捗のグラフ
- 時系列的なもの。
- ライブラリ一覧
- pythonで競技プログラミングをやることについて
- いわゆる精進について
- ABCとARCのどちらが得意か把握しよう
- 水色〜青が最近難しすぎる話
- 今後の目標
- 競技プログラミング関係の他の記事
手短に自己紹介
- AtCoder ID Linus で活動している（ハンドル名の由来はリーナス・トーバルズではなく、スヌーピーのキャラクターであるライナス・ヴァン・ペルトである。）
- 30代社会人エンジニア（データ分析系）
- Pythonで競技プログラミングに参加
- AtCoderとGoogle Code Jamのみ登録し参加している
- 得意はその場で色々考察する系。あとDP。
- 苦手はグラフ全般。
ちょっと前は水色で「競技プログラミングをそこそこしっかりやり込んでいる」と言えた気がするけど、競技人口が増えたせいか青色が目立つようになって、青色がそのポジションになった感がある（個人の感想です）。
あとは「数学が得意なタイプだと、この一つの上の青色に行きますが。（AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 ）」って書かれてたから数学が得意な人間としては青に行っておきたかったのよね。
なので青に上がれて一安心している。
この記事は
Competitive Programming (1) Advent Calendar 2020 - Adventar
の16日目の記事です。
レート推移、各種進捗のグラフ
色辺記事の定番である。レート推移と、各種進捗のグラフを見てみよう。
レート推移
見ての通り、初めて青になったのは2020年3月である。ではなぜこのタイミングで書いているのか? というと、以下のような理由である。
青になる前後で、「青になったら一つの節目として振り返り記事を書こうかな。でも青になって『青色になりました』を書いて、すぐ水色に落ちるのは嫌だな。3回くらい連続で青なら、胸を張って青と言っていいかな」と考えていた。
そうしたら1回目も2回めも直後で水色に落ちたんだよね!
晴れて今回、2020年11月28日のAtCoder Regular Contest 109で3連続青になったので、自分の考えていた「書くための条件」を満たしたので、
このタイミングで書いているというわけだ。
AtCoder Problemsの各種進捗状況
問題を解いている状況を示すために、AtCoder Problemsの画像を色々貼る。
上記だと「何点の問題をどれだけ解いたか」はわからないのね。
というわけで、AtCoder Scoresからもう2枚貼る。
解いた問題数×レートのグラフ
atcoderでどのくらい精進すれば色が良くなるか気になったので、JPユーザー全員を精進ポイント対レートで2dプロットしました pic.twitter.com/Mh02IHVLAK
— なぎた (@nagitausu) 2019年7月4日
横軸(rated score sum)140000, 縦軸1600を見ると……あれ、成長遅い方（同レーティング内では解いたrated score sumが多い）なのか?
（鍵RT from @e869120 ）
— ひゅ〜Men (@men_cotton) 2020年1月17日
何問解いたら何色になれるか、精密に検証してみたところ、60% の人が達成するラインは、
青：1120 問
黄：1510 問
橙：1910 問
ということが分かりました。また、「1 問解けばレート 1 上がる」という衝撃の事実も判明しました。
※自由に拡散・使用して良いとのこと pic.twitter.com/iaOwzFoMeR
これだと「解いた問題が550問で青以上に上がれるのは30%くらい」なので、解いた問題の割には早めに青を達成できたと自認していたんだけど。
アルゴリズムのスクールに通ってたので
東京大学の工学部計数工学科→情報理工学系数理情報学専攻という経歴であった。 授業の中で計算量とか各種アルゴリズムとか叩き込まれるので。 （例えばダイクストラやワーシャル・フロイドは授業で扱う。） あと数学得意系の人生をしていたので。
普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。数学が得意なタイプだと、この一つの上の青色に行きますが。
http://chokudai.hatenablog.com/entry/2019/02/11/155904
数学が得意なタイプなので青に行きたいんじゃ！と思っていた。
時系列的なもの。
- 大学（学部）に在学中、ICPCについて書かれた「目指せ!プログラミング世界一―大学対抗プログラミングコンテストICPCへの挑戦」を買って「へーこんなのがあるんだ」と思ったけど、何していいかわからなかったから何もしなかった。
- 「何をしていいかわからない」から脱出できたのはAtCoderのおかげである。
- 水色に乗せる。
- 2018年は何かめんどくさくなって離れた（特に明確な理由はない）
- 2019年はじめに転職活動して、コーディング面接を受けたときに「やっば、コード書く力が全然無くなってる。Pythonの実装力を鍛えよう」と思い、競プロに復活した。
- 2019年7月に前職退職時の有給消化でやり込む
- 2019年7月にパソコンが壊れて萎える
- 実家のPCでやってたけど、Kiが解けなくて萎えて離れる
- 2020年1月にMacBook Proを買い、自由にパソコンが使えるようになり、やり込めるようになった。競技プログラミングのレートを上げるためには自分用のパソコンを買うのがオススメです（冗談）。
- 3月に初めて青になるが、次のコンテストで水色に落ちる
- 5月に再び青になるが、次のコンテストで爆死して水色に落ちる
- 8〜9月に水色diffや青diffの問題に注力して解く
- 10月に三たび青になる
ライブラリ一覧
色変記事を書くときにはとりあえず履修したアルゴリズム一覧を書けという慣習がありますね。 俺も慣習に倣って書いてみよう。ライブラリのフォルダの中にあるアルゴリズムは以下の通りである。
- 二項係数（を109+7で割った余り）の計算
- Union-Find
- 整数の素因数分解関連
- 二部グラフマッチング
- Binary Indexed Tree（BIT）
- Longest Increase Subsequence（LIS、最長増加部分列）
- ワーシャル・フロイド
あと、幅優先探索・深さ優先探索が出た場合は過去の問題のコードを適当に検索して書き換えて出している（ライブラリにまとめてはいない）。
これらの中で、重要なのは何かと聞かれたらこう答える。
- 二項係数は最重要。特にPythonだと、数学的な考察を済ませて「あとは二項係数ライブラリを使ってちょっと書くだけですね」と思っていたら、TLEを起こして泣きを見ることがある。速度が出るライブラリを予め持っておくことを推奨。私が書いた以下の記事を参照→python競技プログラミングで、二項係数の計算でTLEしたので高速化した話 - 子供の落書き帳 Renaissance
- Union-Findは次に重要。
- ぶっちゃけその他はほとんど使わない。（セグメント木を使えないから、使う問題に出会っても「解けない」で終わるため、この感想になるのかもしれない。）
- BITとセグメント木は未だによく分かってない。水色のうちに履修しておきなさいという感があるけど、ちゃんと履修しないまま青になってしまった。
- ABC185のF
- あとローリングハッシュやらZ-algorithmやらは何もわからない。
習得したアルゴリズムが、俺の場合は同じ青に上がった人に比べて少ないんだろうなー。
もうちょっとアルゴリズムを学習して覚えたらもっと強くなれるのかしら。
pythonで競技プログラミングをやることについて
私がPythonでやっている理由は、上に書いた方に「まずpythonの実装力を付けなきゃ」……って言いながら競技プログラミングに復活したからである。 なお、それまでは主にRubyで書いていた。（競技プログラミングでふつう使われる「速い言語」を全然使っていない。どんだけ天邪鬼なんだ……）
python のいいところ悪いところ
いいところ
- 変数の型を考慮しなくて良い
- オーバーフローを考慮しなくて良い
- したがって剰余を求めるタイプの問題では、途中での剰余計算が適当でも最後に割って剰余を求めれば良い
- 100桁の数などを扱うことも可能（計算が重い場合はTLEになるが）
- itertoolsのライブラリが便利
わるいところ
提出して結果がTLEだったときに、次の行動を考えると以下のいずれかになる。
上記のうちどれを選ぶかをミスると痛い目に遭うなぁ、という感覚である。
この間は「解法を思いつく→計算量を見積もる→これPythonだと厳しくね?どうする?どうする?仕方ない、C++で書くか?と書き始める→C++でうまく書けずに終わる→実はPythonでも間に合う」という事があったし（ARC104）。
C++の場合は、上記3つのうち一番下の選択肢は最初から無い。定数倍高速化が必要になることは絶対にないとは言えないが、かなり稀だろう。
したがって「（計算量が想定解よりも遅くてTLEなので）計算量のオーダーを改善する」と断定してほぼ差し支えないはずだ。迷いがなく次の動きに移れるのが良いなぁと思う。
いわゆる精進について
精進の定義って何なんだ? 「コンテスト本番中以外に問題を解くこと」で合ってる? みんな当たり前の用に使っているくせに、「競技プログラミングの用語集」みたいな記事を見ても全然意味の説明が出てこないんだが。
それはさておき。
精進のやり方は人によって異なる、合う方法合わない方法があるので、あくまで参考程度にしてください。
コンテスト外で集中して解くのすごい苦手……
全部埋めるのが苦手
難易度順に下からビッシリ埋めてる人が多いよね。無理です、俺にはできません。
音ゲーもこの傾向がかなり強く「とりあえず当該レベルを1周して全曲触れ」という意見には反発したくなる。
全曲ってそれ何曲あると思ってるの。何クレかかると思ってるの。好きな曲も嫌いな曲もあるのに構わず触れと?
……閑話休題。
初期の問題の質は悪い、とchokudaiさん自ら言ってるし…… https://twitter.com/chokudai/status/1231612496600944641
AGC-A、diff 1200〜1299あたりは埋めようと頑張ったが、それでも完全に埋めてはいない。
AtCoder Problemで自分のレートと同じdiffの問題をやるな
自分がレート1500だからといってdiff1500をやろうとするな。もっと下の問題からやれ。
ちゃんと理解する
コンテストでは既存の問題と全く同じ問題は（基本的には）出題されない。 したがって、過去の問題を解いたとしても、それをそのまま転用することはできない。 過去の問題から何を得るかが重要になってくる。
ある程度雑でも良いから、方針や感想などを日本語の文章にして書いておくのが大事だ、と最近は考えている。 解法を考えるのに苦労した問題は、日本語で解法を書き留めるようにしている。 最近でちゃんと書いた例だとこの辺りか。
https://github.com/Linus-MK/AtCoder/commit/90388090eb293f762dc681f2687b7dce7d54aaec
https://github.com/Linus-MK/AtCoder/commit/8965e87d309b808826ac3d64917b38b6e88f9504
「どこに気づけばACできたか」というポイントが大事。 具体例を挙げよう。
「連結グラフ一般を対象とした問題は、木に対する問題に帰着できる場合がある」という
紙のノートを作って書いている人もいるけど、私はテキストエディタで書く派である。 （具体的な問題から離れて「今日は××のアルゴリズムを勉強するわ」という勉強のやり方をすることがほとんど無い。 したがって、学習内容のほとんどは具体的な問題と直接紐付いているので、 基本的に問題を解いたコードにコメントを添えておくのが良いのかなと思っている。 あとは「競プロの教訓の一覧」も作ってますね。全然綺麗にまとめずにメモ程度だけど。
https://github.com/Linus-MK/AtCoder/blob/master/lesson.md ）
- やったこと
- 問題の解法を抽象化して言語化しておく
- いわゆるメタ解法みたいなやつ
- やってないこと
- バチャ参加
- CodeForces, yukicoder
ABCとARCのどちらが得意か把握しよう
「あなたのレートはどこから?」というサイトがある。
今見たら https://rating-history.herokuapp.com/rating.html?handle=Linus&number=12 で以下の結果だった。
All: 111 AGC: -47 ARC: 160 ABC: -134 Other: 132
このレート帯の人はAGCを解くと「A問題が解けない」という事態があり得るので、AGCを解いてレートを上げるという選択肢は難しい。 ABCかARCかの二択になると思う。
俺は「問題文はごちゃごちゃ書いてあるけど、要はこういうことでしょ?」をやるのが割と上手いという自覚があるので、ABCよりもARCのほうが得意なのだと思う。 本質的な部分を抽出できるとか、問題文の言い換えができるとか、アドホックな力があるとか、その辺かしら? ABCは1つ躓いただけでレートが大きく下がってしまう感があってヤバい。 あと、ABCに出てる人って、みんな過去問をビッシリ埋めてる人ばかりという印象である。 ABCでは典型力が問われるので、俺のようにアルゴリズムの学習に抜け漏れがある人がやると、「この問題はセグメント木の典型です」みたいな、俺の履修していない解法のド典型問題が出題されたときに容易に死ぬんだよね。 ARCが復活してからはABCには出ないことにした。そう言っておきながら、気まぐれで出るかもしれないけど。 最近のABCでは、あれもこれも緑diffになりすぎてマジ怖い。
水色〜青が最近難しすぎる話
- 新規参入者の基準レートが下がっているせい
- これは参考googleドキュメントを探す
- 上に書いてあった、1問を解いたらレートが1上がるって何なのよ
- 全然上がらないじゃんか
- これは予想可能な理由がある
- 多分なんだけど、このレート帯の他の人はyukicoder, CodeForcesに手を出しているので、見かけ上が「AtCoderを1問解く」であったとしても、実際に解いた問題数、実際の努力量は俺よりも他の人が多いと思われる
- どっかで「青になれませんでした」という挫折記事でも出そうかと思っていたら、運良く青に上がれたのでこうして色変記事を書いている
- 競プロはすべての問題を解決する万能薬ではない
- 数学が強くて、しかもアルゴリズムを大学で一通りやったわという人（俺）でも、青になるまでにはこの程度の時間と労力をつぎ込む必要がある
- 時間がある学生ならば良いけど、時間がない人（社会人とか）がやるときには費用対効果を考えたほうが良いと思う
- モチベーションが下がったら離れるくらいで良いんじゃないの
- 少なくとも俺は付かず離れずでやっています
- 今回のアドベントカレンダーにも「なんか水色が厳しくない? 上がれないんだけど?」って記事があるね
今後の目標
青の次は黄色……いや、黄色とか無理だろ。遠すぎるわ。黄色までの真ん中の1800が当座の目標かなぁ。
青は上位7%である。せっかくの休日に競技プログラミングの大会に出続ける酔狂の中で7%なので、全人類の中では上位1%以内に入っていると思う。
組み合わせるのが一番ラクだからです。ある軸で上位3～5%にいるのはそんなに難しくないけど、100万分の１になるのは並大抵のことではないから。かけっこでウサイン・ボルトに勝つようなものですよね。だから、20分の1とか、30分の1のレベルで勝てる領域を3つ探すわけです。上位20分1を3つ組み合わせれば、8000分の1の稀少な存在になれる。
https://diamond.jp/articles/-/208123
このまま努力を続けていって、例えば赤コーダーになれるかって言ったらなれないじゃん。きっと。
この辺で青キープを目指しつつ、機械学習・データ分析の勉強に少し重心を移すのが正解かなぁと思っている。
GCJの予選1回戦突破は自分の中で1つの目標だったけど、2020年に初めて達成できたしなぁ。 ちょっと次の目標が見つからなくて迷子っぽいな。
それでは。
競技プログラミング関係の他の記事
こちらもどうぞ。
