AtCoderで茶色になったよ！

1/21のARC170にて、AtCoderのRatingが茶色になりました！
昨年12/21に会員登録をしたので、丁度1ヵ月の記念日での入茶！（前日のABCで茶色入りしてたら「1ヵ月以内」だったのにね、とは思ってしまうけど…）
名前の表示もランクに応じて変わるのがめっちゃ嬉しい！

という訳で、今回は茶色になるまでの振り返りをしたいと思います！

始めた経緯などはこちらを。

前提として、全くのプログラミング・アルゴリズム初心者から始めたという訳ではないので、そのような方にとって参考になるような記事ではないと思います。

12/21 最初の最初にやったこと

初動はこちらの記事を参考にしました。
会員登録や簡単な提出のお試しをした後は、問題の形式に慣れるため、AtCoder Beginners Selectionを解きました。
これくらいの問題なら解法はパッと思いつけますが、いざ実装すると計算量が膨大になるものも。
試行錯誤をしつつ問題を解く過程で、競技プログラミングというものの面白さを知りました。

12/22~ お試しとか練習とか…

①当面の主戦場であろうABCまで時間があったので、とりあえずその日やっていたAHC029に参戦。
そのときは大会にAlgorithmとHeuristicの違いもRatingが2種類あることもよく理解していない状態。
無事Heuristic大会の洗礼を受けてきました。
答えがひとつではなく、最適な解が明確でないという点で、アレは普通の大会とは別物だなと理解しました。

②来る大会に備え、よく使いそうな機能をテンプレート化しておきたいと思いました。
beginner's selectionを受けて、最初は配列を扱うものを色々と用意した気がします。

③直近の過去開催のABCの問題を解いてみました。取り敢えずD問題まで！
確かバーチャル参加ではギリギリ3完だったか。出力の手本と睨めっこしながら法則を見出そうとしたC問題の思ひ出…
D問題は、私にとって初めての木構造を扱った問題でした。当初はクソデカ二次元配列でなんとかしようとしていましたが、そんなクソデカ配列のメモリを実行時に用意できる訳もなく…他の人の提出を参考にしながら木構造を実装しました。勿論テンプレートにも追加。

余談ですが、私は人のプログラムを写すときは丸写しはしないようにしています。プログラムを読んで意図を理解した上で一度何も見ずコードを書き、行き詰まったり上手く動かなかったりするときは再度お手本と比べて直します。
一度上手く動くものを書いてしまったらその内容を顧みることがなくなってしまうので、そのときでしっかり理解するように心がけています。

12/23 はじめてのコンテスト参加！ABC334

胸を高鳴らせて参加したはじめてのABC、結果から言うと惨敗でした。334に相応しい

1完。
A問題は流石に秒で解けました。
B問題、ここでまさかの惨敗。考え方も、言語に対する理解も足りていませんでした。C言語での、負の数が関わるときの商や余りについて理解が足らず、何度やってもWA…printデバッグの大事さ、教訓になりました。
C問題は、正直方針すらしっかりと立っていませんでした。このような問題の言い換えは今後も障害になるかもしれませんな。
D問題、実は一番正解に近い考え方ができていた問題でした。累積和までは実装できたものの、二部探索の実装が間に合わず。後に完成した二部探索の関数はテンプレートにブチ込まれました。

Rating 12（+12）
絶望的な幕開けでした…

練習など

という訳で練習をしっかり始めました。
備えだいじ。こちらに羅列していきます。

競プロ典型90問
常設大会にもなっている問題集です。
現在は取り敢えず★5以下の難易度のものを順に解いていっています。1問解くたびに考え方や必要なアルゴリズムについての新たな発見があり、とても勉強になっています。
余談ですが、この問題集を企画・作成した方、私と同学年だそうで(しかも赤コーダー！)。同い年で、最早「負けられない」などと言うのも烏滸がましいほど高い実力の方がいらっしゃると思うと、身の引き締まる思いです。

Educational DP Contest
こちらはまだ触りはじめたばかりですが…
一応事前知識として色々なアルゴリズムを知ってはいたつもりでしたが、こと動的計画法(DP)は自由に活用できるほど理解が足りていないと感じました。
そのため、多岐にわたるというDPの使い所さんを把握し、イザというときに物怖じせずに使えるよう練習していこうと思います！

ABCの問題
参加したり、過去問を解いたりしたときは、時間がかかってもD問題まではしっかりコードを完成させるようにしています。解説は、コーディング中は行き詰まったときにヒントとして読む低度に留めていますが、解き終えたときは必ず読むようにしています。私の考え方よりもより簡潔、或いは計算量の少ない模範解答がある問題は多いからです。

という訳で、ここからはこれまで参加したコンテストの話を書いていきます！

1/6　ABC335

2完！前回よりはマシになりましたが、それでも微妙なスコア…
A、B問題はかなり早く解けたのですが、C問題に手こずりました…方針は分かっていただけに悔しい！ひとえに実装力ぢからの無さです。
で、C問題に集中しすぎててノーマークだったD問題がすっげ簡単だったというね。この教訓は後にABC337で活かされることとなります。

Rating 52（+40）

1/14　ABC336

3完。そこそこの満足。
A~Cまではそこそこ簡単だったけど、Dは正しい方針を立てられず終い。問題がちょっと複雑だと読み替えられないのは問題点ですね。

Rating 151（+99）

1/20　ABC337

ABCEの4完でした。
Dで行き詰まったときにE問題にシフトチェンジできたのが良かった。寄り道だったAHC029でインタラクティブ形式に触れていたお陰で物怖じせずに実装できました。そこそこ時間が余ったのにD問題を実装しきれなかったのは悔しいですが…

Rating 356（+205）

↑あれ！？あとちょっとで茶色では！？
あれ！明日Rated大会あるじゃん！！出よ！
…ということでARC170に出てみることにしたのです。

問題の具合を見るためにARC169の問題を解いてみたのですが…何これ面白い！
10^100という突拍子もない数字に一瞬気圧されるけれど、紙にシミュレーションしてみると「より遠くから影響している項ほど係数が桁違いに上がっていく」という事実が分かり、そこから一見関係の無さそうな木構造の問題に収斂していく面白さ！！
がっつりと歯ごたえのある問題と、それが解ける気持ち良さがたまらない！
提出までは1時間ほどかかりました。
…という訳で翌日のARC170へのやる気を新たにしたのですが、コレ解法を知らなかったら手も足も出ない可能性がある。目標は1完だなー…とか思いつつ、本番！

1/21　ARC170

1完できたー！！！（爆速結論）
とはいえラッキーパンチ感は強いですね…
勝因があるとすれば、しっかり紙に書いて情報を整理したことですかね。よほどワーキングメモリに自信がある場合以外は慣れるまではコレやったほうが確実だと思いましたね。
ちなみにB問題は方針から的外れでした。

Rating 495（+139）
入茶！やっ茶ー！
ARCは参加者自体が少ないし、穴場なのかも…ｸﾞﾍﾍ
と思ってたら、初参加で1位獲った人が1発で黄色になっとる。世界広いｺﾜｲ

と、いう訳でこの1ヶ月を総ざらいしてみました。
今後の目標は、2月の間に緑入りすること！
そして、コンテストで1/2くらいの割合で水色パフォを出せるようになることです！
「よく出る」と言われるような形式はしっかりとマスターできるよう、取り合えずは上記の練習を頑張ります！

それでは入緑記事で会いましょう！