色変しました（茶→緑）
昨日のAtCoder Beginner Contest 188で無事、レーティングが800を超えて緑色になりましたので僭越ながら色変記事というものを書かせていただきます。上位の方からすると取るに足らない内容ですが、Rating分布をみるとどうやら灰、茶の人が全体の半分以上を占めるようで、、それならこの記事にも価値があるのかなーって思いましたので書くに至りました。あとは、私があとで見返したいという理由も大きいです。
どんな感じで書こうかなーって1分ほど悩みました。ぱっと浮かびました。誰からも質問は届いていませんが、勝手に10問Q&Aをやってしまおうと思います。来るであろう質問を勝手に10個予想して、勝手に答えます。
どうやってお勉強をして、どうすれば緑になれるかを主軸に書きますので、お時間がありましたらどうぞ最後までお付き合い下さい。
だいぶ長いうえに、見返してみると、まだ上に何万人といるのによくもこんなに自信満々に語れるな、と恥ずかしくなりました。共感性羞恥の方は覚悟してください。
あと、あくまで私の意見、体験です。明らかに誤りである点はおそらくないとは思いますが、なにかありましたらご指摘いただけると幸いです。
では、いきます。
Q1 誰？
私です。
Q2 競プロ歴は？
2020年8月2日のABC174から始めました。歴で言いますと5か月ですね。
Q3 灰→茶はどのくらいかかった？
どうやら2020年11月1日のABC181で茶色になってるみたいです。ということで、茶色期間は2か月です。自分なりにはそれなりに早く抜けられたと思ってます。
このときの感想を置いておきます。
Q4 そもそも数学とプログラミングはどのくらいできるの？
この辺の質問は競プロ初心者談義で避けては通れないと思います。お話しします。
まず、数学ですね。日本人という母集団の中から無作為に抽出した集合においては、ぼちぼちできる方だと思います（こんなことは競プロ界隈では口が裂けても言えないのですが、、、世界は広すぎます）。一応、高校生に数学を教えるバイト的なものをしていたぐらいには数学と触れ合ってます。そのため、中学、高校数学の問題は一応解けると思ってます。たまに、ググりますが、、、。数学に関しては後程「Q7 そのために何したの？」で触れたいと思います。いったん保留。
次にプログラミングですね。これを表現するのは難しいですね。某就職活動でも「自分のプログラミングのスキルを口頭で僕らにアピールして見せてよ」っていう質問が飛んできて、困った記憶があります。
これに関しては、ほんとに最低限の文法が書けるといった程度でしょうか？プログラミングでなんかを作ろうとか思った時は恐ろしいほど調べながら進めています。言い方を変えるのであれば、この程度であれば日常からプログラミングはしているよって感じです。
さて、実際に数学とプログラミングの実力はどうなのでしょうか？次行きます。
Q5 じゃあ初回と今までの成績ってどんななの？
そろそろ、AtCoderの内容に入っていきます。成績ですね。こちらになります。
散々大口を叩きましたが、初回パフォは「108」です。その後もあんまり良くないですね。私の実力はこんなもんです。
正直に申しますと「水色ぐらいはまあ、ぱっと行けるべ」って思ってました。すぐに打ち砕かれました。お恥ずかしい。ただ、1か月もする頃には少しずつスコアが伸び始めているのかな？この話もQ７で書きます。
Q6 あなたの成績はもういいから、どうやったら緑になれるか教えて？
ここからが本記事の重要な部分なります。長々とすみません。お待たせしました。
マルチ勧誘みたいですが、どうやったら緑になれるかを”言語化するのは”とっても簡単です。
ABC4完
これさえできていれば近かれ遠かれ緑になります。現在のところ絶対です。将来はわかりません。ARCだと2完ぐらいかな？今回は置いておきます。
解答速度にもよりますが、4完できていると、だいたいパフォーマンスが700から1000に落ち着くと思います（体感です）。このあたりが維持できるといずれは緑になれます。
一応私のコンテストの提出結果を載せておきますね（画質が悪くて申し訳ないです）。濃い緑がコンテスト中にACできた問題です。ABC187はバーチャル参加でA-Dの4完でした。
もちろん達成できないこともありましたが、、、多少失敗しても4完していればいずれレートは上がっていきます。
ということで私は「4完」を明確に意識して、コンテストと精進をしてました。というか、競プロにあたって、これ以外はほとんど考えてませんでした。
だって、緑になるって目標だと何していいかよくわかんないけど、4完するってとってもわかりやすいじゃないですか。達成の可否に関わらずです！
Q7 そのために何したの？
Q６で4完と口うるさく書きました。ということで、4完できるようになる精進の方法を書いてきます。
結論から申しますと、緑diff以下の過去問をとにかく埋めていきました。本番では茶色が通れば十分パフォーマンスは出ると思いますが、灰灰灰緑みたいな回がそこそこあるので一応緑も埋めてました。現在のところ、ABC173から下っていきABC130まで埋めました。こんな感じです。
5か月ほどAtCoder様の問題を解かせていただいていますが、正直なところABC（特にd,eまで）は、過去問を解いていれば一発で解ける問題ばかりです。（と思ってます（小声））。逆に解いてないと厳しいかもしれません。というよりかは、まともに議論をしなければなりません（こちらが競プロ、数学の本質かもしれませんが、、。）
難しい問題ってなんで難しいというと、難しい知識を使っているのもそうですが、簡単なもの、基本的なものを組み合わせており、ゴールまでの道筋が長いから難しいんです。と私は思います。
逆にABCとかの簡単な問題はその通り簡単なんです。道筋を長くできないんです。だから、問題によって差はあるにしろ、その根底は過去問で見た考え方やアルゴリズムが大部分を占めています。と私は思います。
ちょっと例を挙げますね。
e問題ですが緑色なので良しとしましょう。こいつらはどちらも「ρ法」で解くことができます。問題を見たときにその手法を知ってるかどうか、その手法に結びつけられるかどうかが、私たちのレート帯だとパフォーマンスの分かれ目になると思います。
競プロを初めて1か月くらいでうっすらと感じ始めました。そのあたりからちょこっとパフォーマンスが伸びてきました。
Q8 どんな感じで過去問解くの？
とにかく多くの問題に触れることを意識しました。そのため、解説ACもどんどんやってしまいました。
このくらいのレートにおいて問題が解けないのは、考察不足ではなく、明らかに知識不足が原因であることが多いと思います。
そのため、大体コンテストで1問に使える時間（茶なら30～60分、緑なら1時間ぐらい？人に寄りますが）考えてダメなら解説を見て良いと思います。幸いなことに公式解説は文書と動画が用意されていますし、解答記事を書いてくださっている方もたくさんおられます。
解説を見て新しい知識を手に入れる。
似た問題が出たときに試してみる。
この繰り返しが効率いいんじゃないかな。
また、もし解説を読んでわからなかったら、いったん見なかったことにして良いと思います。今はわからなくても、演習を重ねて成長してから見るとすんなり理解できることって結構あります。がんがん飛ばして、がんがん進めましょう。
ただし、上で書いた最低限の時間は考えましょうね。これをさぼるとコンテスト本番ですぐ諦めちゃう癖がつきますので注意です。
さて、どんどん進めると書きました。ここで、私が思うことを3つほど。
まず1つ目。Q３で挙げた数学の話です。最近？（そんな昔のことは知りませんが）ABCが数学に寄ってて難しい、ということがたまに取り上げられてます。
例えばこれです。
直線の傾きを求めるのですが、じゃあ直線の傾きってどうやって求めるの？というお話です（0除算とかはいったんおいておきます）。
これは中学生で習うので知っておきたい内容ですが、普段使わないとそんなこと忘れます。数学だから私は覚えていますが、例えば日本史の有名人で同じことされたらたぶん無理です。
ちょっとプログラミングよりかは数学に寄ってますね。
ただ、この問題に関して少し前のコンテストを見るとこんな問題があります。
ちょいとひねってますが、傾きが等しいものを見つける問題です。こんな感じで、過去問をかじっており、それを引っ張ってくることができれば、緑程度までの基本的な数学知識は網羅できると考えています。よくあるコンビネーションの計算も同様です。（あまり譲歩しすぎる文章は好きではないのですが補足を。これに関してはどうしても個人差があると思います。ほんとに数学が苦手な方はこの通りではないことは承知しております。）
もし過去に見たことがなければ、今覚えましょう。この問題が過去になります。一歩ずつのんびり行きましょう。みんなあなたの仲間です。
2点目です。がんがん解くと、AC数は増えていきます。当然です。ただ、AC数がパフォーマンスに直結するとは考えていません。
大切なのは
問題を自分の過去問ストックと関連付ける
ことができるかです。
さて、
問題を理解できること
問題が解けること
コンテストでACできること
この3つは似ているようで、全然難易度が違います。少なくとも私はそう考えています。コンテストで問題が解けなくて、解説見たら、似た問題解いたことあったわーっていう経験があるのではないでしょうか？私は競プロに限らず、そんな体験は星の数ほどあります。
AC数は多いんだけど、いまいちパフォーマンスが伸びないって方は一度この意識を持ってみるといいかもしれませんね。現在の理解は一番上で止まってしまってるかもしれません。
一番下の状態は俗にいう「これ進〇ゼミでやったやつだ」ってやつです。コンテスト中にこの現象が発生すれば自ずと正解できるはずです。たぶんね。
当然、これも個人差が大きいと思います。おそらく、私はこの過去問と結び付けたり、引っ張てくる力がぼちぼちあるんじゃないかと思ってます。さすがに一回見れば全部行けるほどではないですが、2回目は「なんか見たことある、でも解けんなー」ってなって３回目ぐらいに「過去問っぽくやったらいけたわ」ってなって、それ以降は「はいはい典型典型」となっています。
これに関しても、数をこなすしかないのかなと、、何回かかっても良いので「なんか、あれっぽい？」の気づきが成長の証です。
下2つが同じ問題だって気づけたとき私は嬉しくなりました。ああ、強くなってしまったんだなあ、と。
最後の3点目は手短に。どんどん問題を解いていくと、類題のおかげなのか「なんか解ける思考」がでてきました。
まずは愚直考えて、オーダーを減らすにはこうしようー
とりあえず、a+bのスコアが小さいほうからやればいいんじゃないか？
たぶんだけど、M-1で割ると都合がいい気がする。
みたいな感じです。ふわっとしてますが、すぐにその考えが出てきて、実装したら通ったことが増えました。「未証明の解法は良くない」のは承知してますが、ただ指をくわえて眺めてるより何倍もましです。試験後にしっかり復習しましょう。
この章ありえないほど長くなったので、最後に簡単にまとめます。
まずはとにかく量をこなしましょう。こなしていく際には必ず類題（どこかしらは関係している要素の問題）があるはずです。それに気づいたら喜びましょう。そういう意識を持ってると、なんかよくわからない脳の回路ができるかも。
以上です。
Q9 どんなアルゴリズムを覚えた？
この質問もとっても簡単です。
4完に必要なアルゴリズム
です。具体的にはQ８で書いた緑以下の問題に出てきたアルゴリズムやデータ構造を勉強しました。それ以上のことは、あまりやってません。一応、私も解説記事書いているので参加したコンテストはFまで解いているのですが、Fのアルゴリズムはそれ以前の問題にはあんまり使ってないと思ってます。部分的に使うことはあるかもですが、、そのため、青以上のdiffのアルゴリズムは優先度が低くなるのかなと。
なんかぱっと思い浮かんだやつを列挙します。たぶん抜けがいっぱいあると思います。
学んだ（使う）
基本的な入出力
文字列操作
データ構造（set,map,queueなど）
累積和でうまいことやるやつ
BFS
ダイクストラ法
二分探索
動的計画法（簡単なやつ）
modint
modの性質（割り算はダメ、みたいなやつ）
combination（modint,パスカルの三角形）
Unionfind
imos法
順列全探索
bit全探索
ρ法
gcd,lcm
45度回転でマンハッタン距離
繰り返し2乗法
たぶんこんなもんだと思います。
学んだけど使わないと思うやつ（まだ早い）
難しい動的計画法（bitDPとか桁DPとか難しいやつ）
セグ木
BIT
逆元について（フェルマーの小定理、拡張ユークリッド互除法）
半分全列挙
学んでないけど知っときたかったこと
再帰関数
DFS
ダブリング
ワーシャルフロイト法
書きながら、あれも書かなきゃ、ああこれもってなったので、抜けばっかだと思います。
ここで、大事のなのがどこまでできたら勉強したかといえるかですかね。
これもQ８の過去問の場合と同様で「そのアルゴリズムで過去問解けました」から「そのアルゴリズムを別問題に拡張しました」まで持ってくる必要があります。
問題を解く際には上記のものを手足のように扱い、それの組み合わせで問題を解いていきます。そのときに、setってなんだっけ？みたいなことを考えてたら考察、実装が一向に進みません。
例えば、
setにpair<int,int>を入れると、どの順番で並べられて、どのように取り出すか。これわかりますか。私は最近知りました。
こういう小さな操作を問題なく行えて、初めて私たちの武器になります。背伸びをして難しいアルゴリズムを学びたい気持ちもわからなくはないですが、簡単なところから確実に知識と技能を広げましょう。
Q10 モチベーションはどう保つの？
あっさり目に書こうと思いましたが、思いのほか楽しくなっちゃて長くなりました。最後です。
人生やる気に満ち溢れてるときと、そうではないとき誰にもあると思います。競プロのやる気がなくなることも当然あります。
でも、それでいいと勝手に思ってます。
私のなかで競プロはテレビゲームと待ったく同じカテゴリに位置してます。練習して、コンテストにでてレートを上げる。勝てば嬉しい、負ければ悲しい。ときどきみんなで協力する。同じですね。
歳がばれるかもしれませんが、昔、携帯で「チャリ走」ってあったの覚えていますか？ボタンを押すとジャンプして障害物を超えるやつです。でも、「チャリ走のモチベーションがなくてやばい、なんとしてもスコア更新しないと」っていう人は見たことありません。でも、それでいいんだと思います（これプロゲーマーの言葉です。私はこのお話好きなのでよく使わせてもらってます。）。
競技としてゲームに人生を賭けて取り組んでる人もいます。そういう人のことは心から尊敬しています。ただ、多くの人にとってゲームは娯楽です。楽しみましょう。レートが冷えて悲しいとき、次は負けない！となればやればいいし、しんどいわ、、となればいったん休んでも誰も文句は言いません。「しょうがないから、また参加してあげようかしら」となったら再開しましょう。
私はまだまだひよっこですが、これからもこの精神で臨みますのでよろしくお願いいたします。
大変長くなりました。
何年後になるかわかりませんが、水色になった際にはまた色変記事を書こうかなと思います。さすがに2回目なのでとっても短くなると思います。というか短くしたいです。
当面は茶色に戻らないことを第一に精進を続けたいと思います。
ここまで読んでくださった方がいらっしゃいましたらとっても嬉しいです。貴重なお時間をいただきまして、ありがとうございました。
この記事が気に入ったらサポートをしてみませんか？