AtCoder水色になるまでにやったこと

はじめに

Lafoliaです。ようやっと水色になれました。競プロerの慣習として水色になったらそれまでの経緯とやったことを書くらしいので書きます。
前半はただの駄文なので読み飛ばしてください。

f:id:Lafolia:20190309232536p:plain

第一次奮闘期

本格的にやろうかなと思ったのはJOI2017/2018予選で300+部分点で死んだことです。拡張Dijkstraを思い浮かばず森林伐採ができなかったです。
今から思えば森林伐採の解説読んでDijkstraの応用性の高さを知ったのが僕がDijkstraを好きになった理由だと思います。
学校のお勉強は割とできたほうなので悔しくなりました。やろうとなりました。

気がついたら年度が終わってました。

AtCoderやりましょうとなりました。弊部では1年でAOJのIntroductionをやっているので問題を解くことには慣れており、比較的すぐに300まで解けるようになりました。

休止期

PCKがありましたが大したことはしてなかった気がします。 高専プロコンが始まりました。これを言い訳に全く精進せず、コンテストに出るだけをしていました。

高専プロコンが終わりました。

第二次奮闘期

高専プロコンで東京高専の同級生な某々と知り合いました(これは厳密には夏ですが)。やつら強いです。僕は単純なやつなので触発されました。
やりたい気持ちになっていたところ、ちょうどすぐJOI2018/2019が迫ってきたのでやろうとなりました。やります。400難しいです。文字列わからん。未だに分からん。

解説見ながら解ける問題は解きます。解いたので自力が上がります。このあたりでABC全完ができるようになってきました。JOJOにレートも上がります。

JOI予選が通りました。

JOI本選で大爆死しました。

気がついたら年度が終わろうとしています。

春休みになったので圧倒的成長をしたくなり、300を埋めます。埋めました。ABCに出ます。全完します。水色になりました!!!!

水色になるために

上にも書いた気がしますが過去問を埋めるのは非常に重要だったと思います。300点が9割で解けても1割で死ぬので過去の100問くらいを全部埋めて問題に慣れましょう。
ぱっと見で分からない問題で思考停止しないよう耐性をつけましょう。

あと300早解きでも水色になれるらしいですが、多分すごいスローペースになるので400も解けるようにするべきだと思います。

実際問題300と400では基本的には使うアルゴリズムとかデータ構造が違うだけ(だと思っている)なので、どっちも埋めるのがいいと思います。
多分300埋めてるだけだと400を解けるようにはならないんじゃないですかね?出題がまず違うので

400もいくつかに分類できるので、何問か解けばいわゆる典型力が身につくと思います。身についたら本番で出た時に勝てます。レートが上がります。

ということで水色になりました。

300点問題

その他がいっぱいあるきがしますが、基本的には次の問題が出る気がします。文字列は僕の管轄外なので知りません。

  • GCD(最大公約数)
  • ソートして総和
  • 全探索
  • 連想配列

GCDはユークリッドの互除法を実装すればいいです。そのへんに転がってます。数列があって、任意の2要素を互いに引いてく動作があれば大抵GCDです。わからなくても適当に書いてサンプルが合ってたらAC出ることが多いです。

一番大きいのを除外するとかK個選ぶ時の最大とかの問題はソートをして任意個足すとかv[0]だけ引くとかするといけます。

最近はbit全探索がよくでる気がします。再帰全探索を書けるようにしましょう。n進数の表現と復元が理解できればあとは評価計算するだけです。

種類数とかN個選ぶコストの最小とかはmapにぶちこんでsizeしたり上からN個になるまで足したりとかしてくと解けます。

400点問題

ぼくもまだわからないです...(ごめんなさい)。ただ僕の場合はxorでbitをこねこねする問題とかCよりちょっとむずかしい考察問題は解けるので僕はこれで稼ぎました。

注意(?)

上の方に貼ってある僕のレート推移を見ると、大きく下がっている場所があります。ここ全部AGCです。

AGCは1完しかできない場合、水色を目指す人は早解き以外人権がありません(怒られそう)。WAなどもってのほかです。
あと点数にも注意です。ABCとは配点の基準が異なるため、200で累積和とか余裕であります。犠牲者は大量にいるはずです。
僕はAGCのほぼ全てで失敗したためこのような面白いグラフになりました。ちなみにこの時のパフォは負の値になってます。

AGCに出るときは覚悟を決めましょう。出ない選択肢もありだと思ってます。実際次のAGCで死んだら緑に戻るので僕今とても怖いです。

終わりに

いかがでしたか?(以下略)

そんなこんなでようやく水色になれました。青になるには500,600が解けなきゃいけないっぽいので去年一昨年よりも強い気持ちで精進していこうと思います。停滞していたら多分精進してないので、僕よりレートが高い人は気軽にマウントをとってください。あまり間隔が狭いといじけますが、ある程度だったらやる気が出る気がします。

あとこれ読み返すのめんどくさくなるほど読みにくいのでいつか修正します。