AtCoderで青色になってJOI春合宿に行って受験生になった
はじめに
JOI春合宿が終わって、これから受験生をやらなければいけないということで、色々と整理して書き残しておきたい欲が出たのでこの記事を書いています。
目次は
です。
経歴など
PCK2019の本戦にいきました
JOI(2019/2020)の予選~春合宿に参加しました(高2)
AtCoderのレートだと、二次予選/本選時には青タッチした後に落ちて水色、春合宿には何とか持ち直して青色底辺でした。戦績は、予選では420点、本選では306点、春合宿ではday1~4で合計37点(!?)でした。(JOIには2018/2019にも参加していたのですが、予選落ちしてしまいました(当時緑コーダー)。)
AtCoderで青色になるまでに
長かった。C++の基礎文法を理解して間もなくJOIのことを知って競技プログラミングを始めたので、ここまでこれたのは感慨深い。
灰色
2018/2/8にABC088(869位)に出たのが自分の競技プログラミングの始まりでした。当時は何も分からず、300点のC問題に手も足も出ないレベルでした。
茶色
2018/4/7のABC093(312位)で茶色になりました。
B問題まではC++でのfor文が書ければ解けて、C問題は少し競技プログラミングに慣れていないと(少なくとも自分には)厳しかったです。過去のABCのC問題を重点的に練習していました。ここら辺から緑perfが安定してきました。
緑色
2018/5/12のABC097(139位)で3完して緑になりました。
緑までは旧ABC(~125)だと3完速解きができるとすぐなれる印象。当時は全然ABC-Dが解けませんでした。
水色
2019/2/9の「みんなのプロコン2019」(1002位)で水色になりました。
緑色までは割と順調だったのですが、水色になるまでにはとても停滞しました。というのも、競技プログラミングに対するモチベーションが保てなくなり、精進を全くしなくなってしまったからです。
ある回で、自分より遅く競技プログラミングを始めた友人に負けてしまい、このままではいけない、とエンジンがかかって再び精進を始めます。ABC-Dレベルの問題の勝率が50~60%くらいだったので、その得点台の問題を練習していました。
青色
2019/11/23の「DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選」(273位)で人生初の黄perfを出して青色になりました。
緑->水以上に停滞していたはずなのですが、あまり停滞していた印象がありません(おそらく少しは精進をしていたから)。特に何をやっていた、というものはありません(覚えていません)、が、問題をより一般化できないか？と考えることを意識するようにしていました。特によく言われる「典型問題」は抑えるようにしていました。
ABCで出るような典型問題は、練習すればそれなりに勝率が上がります(AGCで出るような問題を典型に落とし込む能力は練習しても難しいです。)。ここで重要なのが、「典型問題」と言っても、有名アルゴリズムをそのまま使うことが明らかな問題だけではありません。聞かれる値や問題設定などが、少し言い換えることによって共通する問題は多くあります。これらの、共通する問題の特徴に対するアプローチ方法を予め知っておくことがかなり効いてきます。
例えば、
- 最小値(最大値)の最大化(最小化)
この問題設定では、解を2分探索し、その解が条件を満たすか、を判定するという解法が多い印象があります。(解の候補の2分探索にlog、判定に線形時間、みたいな)
- modを扱う問題
これはアプローチの仕方ですが、数列の場合だと「値を予めmodを取って考えてしまう」、グラフの問題だと「二部グラフを考える」などです。特にmod 2で要素を全て0/1にした絵を描いてみると景色が変わって解法につながることが多いです。
AtCoderの色変に関するまとめ
結構自分なりに精進しても結果が出ないことがあります。自分は緑のときにそれをよく体感しました。結構しんどいですが、そんなときはアニメを見るなりなんなりしましょう。僕はNEW GAMEがおすすめです(ステマ)。他のコンテストサイトに出るのも良いかもしれません。参考までに、自分のレートグラフをのせます。
JOI春合宿に行くまでに
どうしたら各段階まですすめるかというと、ひたすら典型力を高めることです、つまりはJOIの過去問をひたすら解くことです(完)。ここで重要だと思っているのがJOIの過去問を解くということです。というのも、JOIの問題はAtCoderで出るような問題とは思っているよりも毛色が違います。違いは実装の重さがとてもわかりやすいですが、なんとなく雰囲気が違うというか、解いてみるとわかると思います。おすすめはJOI非公式難易度表を埋めることです(ここ)。
以下では非公式難易度表でつけられている「難易度」を使っていきます。
二次予選
ボーダーは4完だと思っておくと良いです。AtCoderで青色レベルの実力があればほぼ確実、水色ならば70%~、緑色ならば50%~くらいだと思います。(これは自分が各色のときにJOIの過去の問題を解いたときの手応えからの推測なので、あまり当てにしないでください)
難易度表を見るとわかるのですが、だいたい難易度7が確実に解けると安心です。自分が予選で落ちたときは難易度6もまともに埋めていなかったので、ちゃんと対策をすれば通ると思います。がんばってください。
本選
ここからは自分は1回しか行ったことがないので、なんとも信憑性が薄くなります。
ボーダーは3完だと思っておくと良いです。部分点をとるのを忘れずに！！！(2019/2020のボーダーは301点です)。難易度9が解ければ安心して通れると思います。
ここを突破するのはかなり難しいと思います。自分が通った原因は実力2割、運8割、といったところでしょうか。予選を通過した後、本選の突破など夢にもみていなかったので完全に落ちる気でいて、難易度表も予選後からほとんど変化がなく、難易度8以降には一切手をつけていませんでした。通過したのは本当に運が良かった、というのはもちろんなのですが、考えられる他の要因を挙げてみます。
類題を思い出した
ボーダーとなった3問目(おそらく難易度9)を考察する過程で、解法を詰めているときに難易度6で解いたことのある類題を思い出しました。自分の考察が正しいことに自信が持てたので、これはとても大きいと思います。ボーダーを知らなかった
はい。これは単に諦めきっていたからです。去年のボーダーは2完+部分点で、多くの人がこれを目標にしたせいで、本来ならば解ける可能性の高い3問目を落としていたように思えます。何も知らなかった自分は、3問目の見た目から、「これは全員解けそうだから何がなんでも通さねば」と考え、かなり時間を書けましたが通すことができました。
お気持ちの問題なので、一般的に言えることではないと思いますが、ボーダーを意識しすぎるのもやめましょう。(なので、上記で「ボーダーは3完だと思っておくと良い」と書きましたが、あまり意識しなくて良いと思います)
春合宿
行きましたが、自分は何もいえません。競技終了後、毎日「人権がほしい」と呟いていました。ただ、難易度表を全部埋めるくらいの覚悟と実力があると通るでしょう。自分には無理でした。がんばってください。
JOIに関してのまとめ
JOIに関しては、精進は裏切らないです。ひたすら問題を解いて勝ち進んでください。
競技プログラミングと自分
これはポエムです。
もともと自分は飽き性です。中高一貫校で、中学3年生の頃、勉強から逃げるために競プロを始めたときは高校生活を競プロに費やすとは夢にも思っていませんでした。最終的に、PCK本戦や目標にしていたJOI本選、そして思っても見なかった春合宿にまで参加することができ、自分でも驚いていますし、嬉しいです。もらって一番嬉しいのは名札です。
想像以上の実績を残せて嬉しい気持ちもある反面、色々と思うこともあります。特に「才能」というものについては色々と考えていました。あらゆる分野で「才能」は悩みの種でしょう。競プロはその人の実力がレーティングとして出るなど、特にそれが顕著です。自分はずっと、競プロが強い人たちに憧れていました。いわゆる「レッドコーダー」に自分はなれるのだろうか、漠然と「才能」、つまり天才的な頭脳がほしい、とも思っていました。
今、受験生になって、競技プログラマーとしてではなく一歩引いたところから考えてみると、そんな頭脳の根本にあるのは圧倒的な精進量なのだと気づきました。当然、無から有をうんでしまうように見える天才もいるでしょうが、おそらく、土台にあるのは誰よりも固く、揺るがない基本です。自分に足りないのは、そういう基礎を固める根気です。
そうはいっても性分はそう簡単に変わらないでしょう。なんとか受験を乗り越えて、レベルアップしていきたいですね。
最後に
ここまで読んでくれた方はありがとうございます。
がんばります。
