このたび入茶

このたび、ABC366にて、茶色コーダーになりました。嬉しい。
正直自分でもめっちゃ驚いています。

やってきたこと

茶色になるまでに何をしたのかというと、正直何もしてないです。
だけど何かをやることは重要、ということでやってきたことを貼っていきます。

0. なんでもいいから言語をある程度身につける

AtCoderは競技プログラミングなので、ある程度のプログラムができなければいけません。
しかし言って身に着けることはそんなに難しくないです。具体的には

入出力
四則演算
if文/for文
ある程度の標準ライブラリ
もうこれで行けます。これで多分無理やりでもABC-Bは通せます。

そして、言語はなるべく一つに定めた方がいいかと思います。
これから学ぶことはたくさんあります。なるべく脳みそというHDDの領域を
開けておきましょう。しかし言語を定める際にはそれぞれの特徴を見た方がいいです。
競プロで主力となっているのがPythonとC++です。(最近はRustもいるような...?)
それぞれの特徴として、
C++

実行が速い(Pythonの4倍はあるかな?)
イテレータなどの難しい概念がある
比較的難しいと言われている

Python

文法が簡単
ライブラリなどが豊富
ちょっと遅い
僕はAtCをやる前から競プロで使う分のC++は覚えていた?ため、C++を
選んで、始めました。

1. まずコンテスト参加する！

僕は元々AtCoderのコンテストに参加するためでなく、JOIの過去問練習のために
アカウント登録をしたのですが、さらなる練習のためにABCをやり始めました。
最初の方はレートに大きなマイナス補正がかかっているので、ためらいなくABC,ARCに
参加しましょう。僕の場合はARCが恐ろしくて参加していないチキンですが...。

茶色とは程遠いものでした。
ちなみに僕の最初の二戦のパフォとレーディングはこれです。

2. ある程度慣れたらABCのA,Bを早解きする

茶色コーダーになるためには、茶色パフォを取らなけらばなりません。
茶色パフォを取るためには、以下の2つの方法があると思っています。

ABCのA,B,C問題を取りに行く
ABCのA,B問題を合計15分程度で早解きする
こんな感じなんですが、ABCのC問題になるとなぜか異常に難しくなってくるので
まずはAB早解きをやるようにしました。

AB問題を、ひたすら大量にやりました。ただ、ひたすらに早くできるようにやりました。
結果

こんなことになってしまいました。
とはいってもA問題は基本的な文法さえできればどうにでもなり、
B問題は慣れです。それだけです。

茶色コーダーになるのなら、Aは5分、Bは簡単なもので5分、難しいもので25分以内に
解くことができれば茶色パフォを取ることはできます。

僕は早解きができるようになったことで、茶色パフォを取ることが出来ました。
かなりギリギリですけどね()

そしてこれは余談なんですが、ABC359で奇跡を起こしました。
A問題を1:35、B問題を5:28で解き、茶色中位パフォを獲得したのです。
こんな感じで、ABをすぐとれるようになれば、最悪茶色になれます。

3. C問がんばる

C問が解けるようになれば、確実に茶色パフォを取ることができます。
しかしC問題はA,B問題のようにうまくはいかないのです。
例としてこれを考えてみましょう。
https://atcoder.jp/contests/abc364/tasks/abc364_c

$N$個の料理があります。$i$個目の料理の甘さは$A_i$、しょっぱさは$B_i$です。
高橋君は$N$個の料理を好きなように並べて順に食べていきます。
しかし甘さが$X$を超えるかしょっぱさが$Y$を超えてしまったら食事終了です。
高橋君は最低でいくつの料理を食べますか?

まずは全部の並び替えを試してみることが思いつくと思います。
しかし、実はこれだとTLEという間違えた判定になってしまいます。
実は、コンピューターが計算に時間がかかりすぎてしまい、ダメになってしまいます。
なぜこんなことになるのか、考えてみましょう。

まず、料理の順番として考えられるのは$N!$通りです。そして、ある並べ方を実際に
食べてシミュレーションする時間は大体$N$回くらいです。ということは、
計算する量は**大体$NN!$通り、これは

O(NN!)

と書きます。しかし制約には

1\le N\le 2\cdot 10^5

と書かれています。ということは最大でだいたい

10^{556571552}

回計算することになります。怖いですね。
こんなことをしていてはさすがに間に合わないので、もうちょっと考えなければなりません。
このように、計算量を考慮するということが大事になってきます。

さて、もう少し考えてみましょう。しょっぱさと甘さという二つの概念があるので、
それぞれについて考えてみましょう。

しょっぱさが$Y$を超えないようにするには?

という問題と、

甘さが$X$を超えないようにするには?

という問題になります。
実は、一番甘い/しょっぱいものを手当たり次第高橋君に食べさせればいいのです。
わざわざあまりしょっぱくないものを食べさせるのは非効率なので、
高橋君の口に対する負荷が高いものを食べさせればどうにでもなります。
ということで、昇順に並び替えてどうにかするということをすればいいです。
では、甘い順にソートして食べさせたときの食事の回数、
しょっぱい順にソートして食べさせた時の食事の回数の方の小さいほうを考えればいいです。
これは大体$O(N \log N)$なので、制限時間に間に合います。
このように、制限時間に間に合わせることが重要になってきます。

他には、「全探索」をする、というあり得るパターンを全部探索することで
正解をすることができる問題もありますが、そのためにも技法が必要であったり、
ちゃんと制約を見て「全探索できる?」と判断することが大事になってきます。

そして、僕はそれを練習した結果、

このように、茶色上位パフォを取ることが出来ました。これによってレートはグングン
上がっていきます。制約をちゃんと見る力が上がり、全探索をすることによって解くことができた問題もありました。

4. アルゴリズムをちょっと見る

アルゴリズムとその応用をちょっと勉強しました。

貪欲法
二分探索
ソート
累積和

このあたりです。これをやれば大体できるようになります。ABを余裕で解けるように
なったらC問題を練習していました。C問題は大体貪欲かバカみたいな全探索が多い
イメージです。

5. 諦めない

最初は「茶色perfにすらだせないなんて僕は何て馬鹿なんだ」とも思っていました。
しかし、AtCoderなんて天才の集まりです。茶色になるなんて、とても難しい事です。
あなたはAtCoderに参加しただけでも十分偉いのです。
AtCoderの人員は、登録しても70%くらいがやめてしまう、ということを
聞いたことがあります。でも茶色は努力すれば誰でもなれます。
「自分はできない」なんて思ってはいけません。あきらめずに頑張ってください！
おそらくこれが一番大事な事です。

6. 喜ぶ

そして、僕はABC366の大勝利により、緑パフォを出しレート403になり、ついに
茶色コーダーになりました。ここまで道のりが長かった...のかな...?
なったら喜びましょう。そしてここからまだまだ伸びしろがあるはずです。
緑になりましょう！！！現在僕も緑になるため精進中です。

まとめ

AtCoderで茶色になるためには、根性と気力が必要です。
茶色は例えどれだけ初心者であろうともなることができます。
でもその前に諦めてしまう人がいるのです。まずはその壁を乗り越えましょう。
たとえ挫折してしまっても、何年後でもいいからよみがえればそれでいいのです。
ということでただのにんげんが茶色コーダーになった話はこれで終わりです。
これが少しの灰色コーダーの方にでも伝わればいいなと思います。

余談

最近のdiffインフレし過ぎです。怖いです。
昔の灰色上位はめっちゃdiff下がって、簡単なダイクストラとかは茶色diffになって
しまいました。茶色の道のり、やっぱり長いですね...()

追記

こういうのはやはり、「みんな楽しくやる」ことが大事だと思うので、Discordサーバーを開設しました。
上級者から初心者まで入れるのでぜひ。
https://discord.gg/qeaquwhmMA