2019-04-01

2019年3月の振り返り

3月の月報。微妙に仕事が忙しかったせいか、あんまり記憶がありません。

AtCoder

f:id:arzk:20190401205647p:plain

1468 -> 1541 でした
やっと青見えてきたなぁ〜という感じです。感慨深い。
でも、1600になるには、1971 必要とのこと。今までのベストを超えてるので多分無理そうです。はぁ〜青になりたい。

その他は、あんまり記憶がありません。無理矢理でもなんか勉強せねば、、という気持ちです。

2019-03-17

AtCoderを始めて半年経ったのでその振り返り

2018/9/10にAtCoderの問題を初めて解いて、約半年経過したので、メモを残します。とりあえず青になるまでは競プロ最優先で時間を振り分けているのですが、3ヶ月で青 -> 半年で青 -> 一年で青、と順調に期限が伸びているようです。

全体推移

コンペに13回参加して、現在水色(1490)。平均すると、1550ぐらいで、ちょっと青には足りないぐらいの模様です。
まだ、上げ止まってはいないですが、そろそろ限界が見えてきそうです。
半年で、150〜200時間ぐらい費やしました

Ratingの推移

f:id:arzk:20190317212211p:plain — ratingの推移

Performanceの推移

f:id:arzk:20190317212532p:plain — performanceの推移

初期状態

10年ほど前にTopCoderで1,2ヶ月遊んでいたので、競プロ自体には馴染みがある。典型アルゴリズムやデータ構造にそれなりの知識があるが、錆びついていてすぐには使えない、といった状態でした。手始めにABCの問題を解いたところ、C問題がぎりぎり解けるぐらいのレベルでした。D問題にはわりと苦戦していて、実際最初二回のABCは全完できず緑パフォでした。

開始1〜２ヶ月

ひとまずけんちょんさんの入門記事を見て過去問を解く作業から始めました。けんちょんさんとアルメリアさんの解説記事にはとても良くお世話になっており、感謝ばかりです。

qiita.com

また最初に解いたC問題で、最小公倍数を求める必要があり、そのときはユークリッド互除法をググって事なきを得たのですが、典型アルゴリズムを知らないと手も足も出ないのでは？ということで早速蟻本を購入しました。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

作者: 秋葉拓哉,岩田陽一,北川宜稔
出版社/メーカー: マイナビ
発売日: 2012/01/28
メディア: 単行本（ソフトカバー）
購入: 25人クリック: 473回
この商品を含むブログ (36件) を見る

情報収集の結果、300点早解きできれば、水色パフォは出るっぽいぞ、ということで300点問題を解けるように、過去問埋めに励みました。爆死しないことは精神衛生上大事だと思うので、低レベル問題の基礎固めしておくことは、スコア安定には良かった気がしています。自分の場合考えるのが苦ではないので、できる限り自力で解けるようにけっこう一問一問時間かけてやっていましたが、正直なところのそのスタイルが効率が良いかと言われるとよくわかっていません。C埋めを始めると同時に、蟻本も読み始めたのですが、C問題を解くには蟻本の知識はやや高度なので、一旦蟻本を封印して過去問を埋め作業を行いました。

AtCoderの点数と色に関する統計データ公開します。（りんご作）
個人的には、赤は練習する意味なし、オレンジは解けなかったら要復習（強い人のコードを見るのは良い）ってくらい。白のゾーンに取り組むのがとてもおすすめ。
青ゾーンはチャレンジゾーンで、黒はまだやらなくて良いところだと思う。 pic.twitter.com/qyiPBg8wne
— chokudai(高橋直大)🍆🍡 (@chokudai) 2018年4月18日

※目指すランクに応じてどのレベルの問題がどの程度解ければよいかを把握するためには、このtweetがとても役に立ちます。

だいたいABC-Cを半分ぐらい埋めたぐらいで、C問題には苦戦しなくなったので、400辺りを解く練習を始めました。ある程度問題を解いていくと、300点問題だとだいたいこういう解き方に絞られる、といった経験則が培われてきます。例えば、ABC-CではDPを使うような問題にはまず出会わないので、DPで解こうとした場合は考察が間違っている可能性が高いです。そういった感覚があると、問題を見たときの解法空間を搾ることができるので、コンテスト中に迷いが少なくなります。(600,700だと逆にそれが悪く働く場合もありますが)

その後、ABC-Dを解く練習を始めたのですが、このタイミングでも蟻本はまだ勉強しませんでした。問題を解く、解けなかったから解説を読んでテクニックを覚えるということを繰り返しました。 ABC-Dぐらいだと、DFS, BFS, 再帰、尺取り法、累積和、GCD あたりの知識があれば、わりと戦える印象で、あまり知識とかは要らない印象でした。

開始3〜4ヶ月

過去問のDが100%解けるかというと微妙な状態でしたが、ABCでは全完できることが多くなってきたので、よりレベルアップするために、500,600辺りを解けるように訓練を始めました。このときは、蟻本をまずざっと眺める、ということから始めました。水色コーダーからすると、500,600問題は、早く解く、というよりは1時間かけてACできれば良いです。なので、アルゴリズムを使いこなすレベルの前に、頭のなかにインデックスを構築しておき、後から引き出せるようにしておくことが大事だと思います。自分の場合、コンテスト中に頻繁に蟻本を眺めます。

400〜700の問題は自分にとっては結構難しいので、勉強には時間がかかりました。問題を解く -> 蟻本の関連する箇所を見る、といった作業を繰り返しました。Webの解説記事はとてもありがたいですが、その大元はおそらく蟻本なので、何かを勉強したいとき蟻本を見るのが私は良いと思います。蟻本は簡潔によくまとまっており、作者の方々の知性に感動する本当に素晴らしい本です。

この終わり頃にはABC-Dあたりは解けないことはあまりなくなってきました。500,600あたりは、解説を読んで理解はできるし、たまーに簡単な問題なら解ける、というレベル感でした。 DPは雰囲気でしか書けなかったのですが、この頃には少しづつDPを使いこなせるようになってきました。

開始5〜6ヶ月

青パフォしか出ないと、青色にはなれなさそうだということが現実に見えてきました。特段、やっていることは変えず、400-700辺りをたまに解くというような精進をしていました。400-700辺りは自分にとっては難しく、1問理解するのに1-2時間かかってしまうため、デイリーの精進がしづらくそれほどは進んでいません。この問題への対応のために、30分考えたら答えを見る、というように時間しばりをいれた動きをしていこうかなと考えています。

また、codeforcesに参戦を始めました。コドフォに関しては