AtCoderで赤になるまでにしたこと

 

ひとつの到達点なので。

 

自己紹介

・京都大学理学研究科M2(数学系)

・公立高校出身

・ぎりぎり数オリ勢(春合宿参加1回で数オリ勢名乗るのおこがましい)

・競技プログラミングも含めてプログラミングを始めたのは2018年1月から(当時B4)

 

したこと

問題を解いた

f:id:tempura0224:20190924032455p:plain

 

1800問くらい。

作問

今年の春くらいから伸びた理由の1つだと考えていることその1。

yukicoderで数え上げセットを作って以降CPSCOやHUPC、JAGで出題させていただいたりと作問に関わる機会が増えました。

僕は解法を先に決めてから問題をつくることが多くて、その過程で解法の持つ性質だったりどこまで抽象化できるかを考えるようになりました。例えば、答えを決め打つ二分探索が想定解の問題を作ろうと思うと、その解法が適用できる問題は「そのままだと難しいがYes/Noの判定なら高速にできて、Yes/Noに単調性(ある境目が存在してそれ以上ではYes, 未満ではNo など)がある」という性質を持っていることが分かっている必要があります。あるいは「セグ木で問題をつくりたい→セグ木はmax/minとかsumだけじゃなくて一般にはモノイドが乗るらしい→具体的にどんなことができるだろう？」と考えたりです。要は作問をすることでその周辺に対する理解度がかなり上がることがあります。テストケースを作ろうとするとコーナーケースや嘘解法も一通り考えることになるので、それもかなり良さそう。あともっとわかりやすく自分の作った問題がコンテストに出ると瞬殺できるのでお得です(直近2回のコンテストの勝因はこれも大きい)。

実際に出題する/しないはともかくとして、自分で問題を考えて自分で解いてみる習慣はかなりいい訓練になるかなぁと思います。実際にyukicoder等で問題を出したくなったらテスターは暇な限り引き受けるので気軽にお声掛けください。

ICPCのチームを組んだ

伸びた要因その2。チーム練はいいぞという話。

・シンプルに練習時間が増える。

・自分とタイプの違う人と組むと今までなかった視点に気付けたりする。

・国内予選通過とかWF進出とかわかりやすい目標があると精進もはかどる。

 ただ僕はかなり環境に恵まれている自覚はあって、これは誰にでも通用するものではなさそうです。

 

その他

普段意識してることとかTwitterのリプでいただいた質問とか

必要そうな知識

AtCoderはほとんど知識が要求されないこともあってかなり難しいんですがライブラリとしてはAtCoderだけなら600点くらいで出うる内容くらいで十分なんじゃないかなぁ。僕はそれ以上使った記憶がないです。

テクニックも

・区間hoge→差分

・単調性→にぶたん

・マンハッタン距離→45度回転

・(思い出したら書き足す)

みたいな青あたりでも十分知ってることくらいで黄色の頃から極端には増えていない気がします。

赤になる前後の変化でかなり実感しているのはアドホックでない500点以下が瞬殺できるようになったことで、個人的にはこれが1番大事そうです(うーんAtCoderの点数基準で書くの微妙そうで、こどふぉ換算のほうがより正確そうなんだけどこどふぉの点数事情がよくわからない、たぶん1900とかその辺)。

これくらいができるようになると、高得点の問題でも何らかの性質を見つけたときにそれが良さそうかあまり使えなさそうかの判断を間違える確率がかなり下がって、解法探索のコストがかなり下がりがちです。

で、これはたぶんAtCoderよりこどふぉのほうが鍛えられる印象があって(良くも悪くもこどふぉのほうが典型+1ステップ系が多い気がします)、こどふぉを埋めると良さそうな気がします。

 

精進

最近できてません(完)。

AtCoder、codeforces、yukicoder あたりにだいたい出ると週3.5くらいにはなって、それとチーム練を合わせると週5くらいになるのでそんなに余裕なくない...？(ほぼ同じ環境で問題を解きまくってる人がいるのも知っているのであれだけど...)

JAGとかACPCとかで最近できていなかったけどこどふぉのDiv1バチャは再開したいと思っています。何人かで集まってバチャる(最悪同時でなくてもいいが友達の成績が把握しやすいとよくて、その点こどふぉはえらい)と集中できるし解くのにかかった時間とかも管理できるから個人的にはかなりいい練習方法な気がしています。前半の簡単枠でACが稼げるのも精神に良いですね(1日1問を悩み続けて終わり、大事な経験とは思うがつらいので...)

コンテストの立ち回り

これは自明なことしか言えないですが基本的に前から解いています。順位表を見て逆転が起きてるところがあったら考えたりします。現時点で解かれているわけでもないのに後ろを見に行く立ち回りは現時点で求められたことはないです。あとtouristはできるらしいですが並列思考は一般人には無理だと思います。

ARC級は後ろから2番目の問題を高速に解けば普通に赤パフォが出ます(そうでないときは最後の問題が解けないとダメな回なので解いてください)。そういう意味でも500以下の瞬殺力は大事だなぁと思っています。

あと考察に詰まったときは一旦力を抜くのは大事です。ちょっと歩き回るもよし、トイレに立つもよし、なんとなく順位表を開いて友達の進捗を眺めるもよしです。1回深呼吸してから問題に戻ると今まで全然見えなかったことが見えたり見えなかったりします。

 

赤になって変わったこと

ARCがunratedになった

オンサイト予選がunratedになったのはかなりありがたいです(最悪遅刻して参加とかも許されるので)。

ユーザー名が変更できなくなった

知らなかったんですけど赤になると原則変えられなくなります。サポートに連絡するとできたりできなかったりするらしいですが少し面倒。近々赤になる予定があって名前を変えたいかもしれない人は今のうちに変えておくことをお勧めします。

Twitterでバズった

赤になったツイートに1200いいねがついてフォロワーが200人増えました。赤になる行為は言ってしまえばただの私事なのでそれを多くの人にお祝いしてもらえるのはとても嬉しいしありがたいことです。

TBA

まだ赤になってから何もしていないので何かがあるたびに書き足します。

 

今後の目標

・AtCoderのwriterをする(まずはABC、できればARC級)

・chokudaiに勝つ

・オンサイトで賞金

・WF

 

最後に

正直なところ赤になった実感はあまりないです。いやTwitterでは散々ネタにしてるんですけどなんかまだ単に自分の持ってるコンテンツが1つ増えただけ、みたいな感覚です。赤になることがほぼ確定した瞬間は嬉しかったし武者震い(?)もしたけど、いざなってみると呆気ないというか。当たり前なんですが日常は何一つ変わらなくて明日も人生が続くんですよね。

でもそれでいいと思っていて、まだここは通過点であってゴールにはなって欲しくないので。

この数回のコンテストが相当上振れなのは自分でも分かっているけどそうはいっても橙を8回で抜けられたあたりまだまだいけるだろうという思いも当然あるので、もう少しこの調子でレートを上げられたらなぁ。

 

次回のAGCでパフォ2580くらいを叩いたら一発脱色らしいのでそれは避けたいね(フラグ)