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本選、そして思っても見なかった春合宿にまで参加することができ、自分でも驚いていますし、嬉しいです。もらって一番嬉しいのは名札です。
想像以上の実績を残せて嬉しい気持ちもある反面、色々と思うこともあります。特に「才能」というものについては色々と考えていました。あらゆる分野で「才能」は悩みの種でしょう。競プロはその人の実力がレーティングとして出るなど、特にそれが顕著です。自分はずっと、競プロが強い人たちに憧れていました。いわゆる「レッドコーダー」に自分はなれるのだろうか、漠然と「才能」、つまり天才的な頭脳がほしい、とも思っていました。
今、受験生になって、競技プログラマーとしてではなく一歩引いたところから考えてみると、そんな頭脳の根本にあるのは圧倒的な精進量なのだと気づきました。当然、無から有をうんでしまうように見える天才もいるでしょうが、おそらく、土台にあるのは誰よりも固く、揺るがない基本です。自分に足りないのは、そういう基礎を固める根気です。
そうはいっても性分はそう簡単に変わらないでしょう。なんとか受験を乗り越えて、レベルアップしていきたいですね。
最後に
ここまで読んでくれた方はありがとうございます。
がんばります。
JOI 水ようかん (Mizuyokan)
問題
解説
まず、最小値と最大値の候補はN2個ずつである。
(1) そこで、N4通りについて、それぞれ実際に切り分けられるかの判定の方法を考える。
dp[i] := [0,i]を条件を満たすように切り分けられるか(bool)
[0,i]について、0<=j<=i-1を満たすjをとって、区間を[0,j],[j+1,i]に分けて考える。dp[j]=trueのとき、
最小値<=L_(j+1) + ... L_i<=最大値
を満たすならばdp[i]=true。よって判定には全体でO(N2)。全体でO(N6)かかる。
(2) 真偽値をとるDPには無駄が多い(蟻本より)。最小値を固定すると、知りたい情報は「条件を満たすように切ったときの最大値の最小値」。ここまでくれば先ほどと同じようなことをすればO(N2)でそれぞれの候補について計算ができる。全体でO(N4)。
感想
これ本当に難易度7か？？？とても教育的な気がする。分かると楽しい。
ABC156
全体
5完。立ち回りも特に悪くなかった。単純に解くスピードが遅い。
D-Bouquet
nCkはO(k)でできることに気付くのに10分くらいかかった気がする...。
E-Roaming
重複組み合わせ、少し焦って計算ミスったりしたのが良くない。割とすぐ気づけたのは良かったから、詰めを冷静にしたい。
F-Modularness
コンテスト中に解けず...。
dの要素を各クエリでmod mに置き換えても間に合う。
1) ai mod m = ai+1 mod mのとき
di mod k = 0
「di=0がn項のうち何回現れるか」をカウントすれば良い。
2)ai mod m > ai+1 mod mのとき
m <= ai+1 < ai+m
である。つまり、mで割ったときの商がちょうど1つ増える。「商が全体でいくつ増えるか」が分かればよく、aは単調増加だから、an-1の商とa0の商を比較すれば良い。
数えたいものが直接数えにくいときは、全体から「数えたいものの条件を満たさないもの」を引く。これは典型的な「余事象」の発想であり、数学と少し見た目が違っても頭に置いておくべきだった。
AtCoder ABC 136 E - Max GCD
問題概要
長さの整数列
が与えられる。次の操作を
回以上
回以下行うことができる。
なる
以上
以下の
つの整数
を選び、
に
に
を足す。この操作の後いずれかの要素が負になってもよい。
操作後のの全ての要素を割り切る正の整数として考えられる値の最大値を求めよ。
制約
解説/考察
ステップ1
答えを、各
に対して変化させる値を
とおくと、
です。よって
が成り立ちます。またこのとき、問題文より
なので、
と変形できます。よって、答えは
の総和の約数であることが分かります。
ステップ2
次に、答えの候補をとしたときに、
回以内の操作で整数列
の要素を
の倍数にすることができるのか判定する方法を考えます。
各について、
を引く(「-方向」)
を足す(「+方向」)
ことによっての倍数にすることができます。
= (「-方向」の量) - (「+方向」の量)とするとき、
となっている必要があります。
まず最初に、の全ての要素を「-方向」に設定してみると、
です。また、これはの倍数となることが
の総和が
の倍数であることからわかります。
それでは、ここから1つの要素を「+方向」に変えてみます。このとき、の変化量は
となります。よって、 個だけ「+方向」に設定しなおせばよいことがわかります。操作回数は「+方向」に設定しなおした後に残った「-方向」の量です。どの要素を設定しなおしても
の変化量は
なので、
から、
のうち大きい方から
個の和を引いた値が操作回数の最小値となります。これによって求まった値が
以内ならば、
の要素を
の倍数にすることができます。この判定方法をステップ1で挙げた答えの候補のうち大きい方から適用していくことで答えが求まります。
思考の流れ
- とりあえず文字でおいて式化してみる。
これはあらゆる問題で言えることですが、未知数を一つの文字で置いて、式の最終的な状態、最初の状態、条件式を書き出してみると重要なことが見えてくることが多いです。この問題で言うと、最初の変化量をと置くことで、最後の状態
の式と条件式から、関係性を見出すことができます。
- 答えは
の総和の約数で、約数の個数はあまり大きくならない(参考)ので、列挙して一つずつチェックしていけば良い。判定方法を考える。
の倍数にしたいとき、
だけ引く、又は
を足せばよいことがわかり、全体でこれをうまく調整することで「引く量」=「足す量」にしたい。
- 「引く量」と「足す量」の差を考えれば良さそう。式変形(あるいは実験)をすると、差が
感想
コンテスト中、ステップ1を思いついたときは、これがこの問題の本質だと思っていましたが、どちらかというとステップ2の判定フェーズの方が骨が折れます。しかしステップ1に気付かなければ何も始まらなく、非常に考察力が試される問題だと思いました。
