Attack All Around

今やCTFと競プロばかりだが、トビタテ生のアメリカ留学やTOEFL奮闘記

AtCoder 入水しました！

初めて色変記事というものを書いていきます。多くの方に読んでもらえたらと思っています！特に入水を目指している方向けになればいいなと思っています！

f:id:partender810:20210517123732p:plain
ユーザ名の色変わったらしばらく見ていたいものである

f:id:partender810:20210517124035p:plain
初めて2年半で入水しました！

では、今までのことをつらつら書いていきます。最初は競プロをするまでのことを書くので、始めてからを知りたい方は読み飛ばして下さい。

AtCoderを始める前

高校生まで

プログラミングの「プ」の字も知らない。パソコンと言えば親に隠れてゲームの攻略法(ワザップとか)を調べる手段に過ぎない。それか情報の授業で触る程度。

今や中学生高校生がAtCoderをやっているのが珍しくなく、自分よりも全然rateが高い方を見るとすげえなぁって言葉しか出ない。例えまだ入水していない学生さんでもやってるだけですごいと本当に思う。

大学学部生時代 プログラミングと出会う

1年次に初めてプログラミングというものを知る。最初はC言語で、Hello worldってどの目線で言ってんねん、for文ってなんやと思っていました。プログラミングって新しそうっていう薄っぺらい知識から親は知らないだろうと話してみたら、なんと親父が知っていた。高校生の時も勉強を父から教わっていて、大学生になってもそれは変わらずC言語を教えてもらっていました(参考にならなくてすみません)。それから授業の中でも好きな方になっていきました。

2年次に挫折を味わう。Java言語の授業に遭遇するのである。オブジェクト指向ってなんやねん！！！そしてソフトウェア開発？的なグループワークでチェスを作る課題が一切分からず、他のチームメイトが99%行い自分は何もできないんだと悟る。
他にも2年次にはアルゴリズムの授業があり、ソートについてや最短経路探索、幅優先深さ優先などなど競プロにかなり役立つものばかりでしたが、当時の私はそんなに理解できていませんでした。

3年次は好転します。C言語の授業で競プロのようなオンラインジャッジシステムにグループで提出しろというのが毎週ありました。3人グループで自分以外女子、しかも二人とも可愛い。頑張らないわけがありません。積極的に課題に取り組み好感度爆上げ作戦を実行します。おかげでプログラミングの経験値は稼げました(他は察しろ)。

4年次、今の研究室に配属するとみんなpythonを使っていました。授業でpythonを扱ったことが無いので、なんでみんな知っているのか&よく使われているんだ、と壁を感じました。少し勉強したら使い方も分かり、今では本当によく使っています。でも、4年生になりたての時は授業で使ったことない言語を普通に使いこなしている先輩&同期が遠く見えました。

AtCoderを始めてみた

そんなこんなで大学院生になりました。やっと競プロを始めます。
競プロを始める前のプログラミングとの関わりとしては

といった感じです。

これからは下の図に沿って書いていきます。

f:id:partender810:20210517131546p:plain
全5部作

灰色期

昨年度同期みんなpythonを知っていてビビり散らかした経験から、他にも言語学んでおかねばとフリーランスの友達にどんな言語を学ぶと将来活きるか聞いたところ、golangとかいいかもねと言われ勉強します。ただ勉強するだけじゃつまらない上にできているかどうか分からないので、競技プログラミングをチュートリアルとしようと思いアカウントを作りました。コンテストには出ず、過去問をいくつか解いていました。灰色ではなく黒色期ですね(笑)

そこから問題を解いていくうちに、実際に自分はどれだけできるのだろうと気になりコンテストに2回出ます。最初はまさかのAGC。よく知らないまま参加したのでいつもより難しすぎる！！！となります。ただ初めて出たのでrateは少し上がります。2回目はちゃんとABCに出ます。その時の記憶が無いのですが、なんと1100パフォ。提出履歴観たらpythonで出してる。GO言語の勉強どこ行った(おそらくいい成績出したくて慣れてるpythonでやったのでしょう)。

そこから留学準備の為半年間お休みします。この時期のTOEFL勉強きつかった。よかったらその時の記事もあるので読んでみてください。

復帰後はGO言語でコンテストには出て、特にこれといって精進はしていなかったです。競プロのための勉強はしたくなかった…。1ヶ月しかいなかった留学中もやっており、その期間で入茶しました。

茶色期

帰国後、一番の転機が訪れます。研究室の新入生に黄coderがいたのです。茶色になりたてからするととても遠い存在ではありますが、彼に教えてもらう気満々でいたことは確かです。そして、緑coderもいました。彼とはいいライバルが続いております。

まだGO言語を使っており、灰色期に比べ反省や復習をよくした記憶です。挑んだけど解けなかった問題であったり、どうしてもO(N), O(N logN)に落とし込めない問題など、実装はともかくACへのプロセスは理解するようにしていました。それもこれも彼の指導ですね。

そしてコンテストもよほどのことが無い限り参加していました。上級者が身近にいるのは本当にありがたく、未熟者からすると解説を読んでも分からない近いできないということはよくありました。また解説にはないやりやすい方法など彼に聞いて教えてもらっていました。

一度、ABC-Eまでコンテスト中に解け、終了後FもACできた時がありました。5月過ぎの伸びているところです。それから緑にならいけるのでは？とモチベーションが上がりました。

そして、とうとう親父も競プロを始めました。親父はc++を使っており、同じアルゴリズムでもc++の方が断然速いことを目の当たりにした結果、GO言語を学びたいという初心を捨てrateを上げたいと目標を変えます。c++に完全移行した日あたりで入緑しました。

入緑後、即停滞期

この時期の停滞期は妥当と思っていました。まだまだ不慣れなc++の扱いであったり、緑になる目標が達成されたので上を目指す意識が低かったです。それでも色落ちした時は悔しかったですね。

ここらへんの時期から彼や、他の競プロerの勧めもあり、ちゃんと精進するようになりました。よく使っていたのはこのサイトですね。

レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】 - Qiita

夏休み中や、ちょっと空いた時など解いていました。ワーシャルフロイド法やUnion-find、いもす法など知らないアルゴリズムが多かったので勉強になりました。今までろくに勉強してなかった分ですね。

また、競プロ用のアカウント(@ks37814026)を作って多くの競プロerの方と繋がれるようにしました。その方たちが詰まったところや良い問題などを共有して下さるので、勉強するのに困らなかったです！ 今もそのアカウントは続けているのですが、CTFの宣伝が多いですね(笑)

そして、精進の成果が出てきたのは肌寒くなった頃でした。

入水できるかも期

ある程度のアルゴリズムを覚え実装もできるようになると、だんだんrateが上がってきました。ABCではDが安定して解けるようになり自信も付いてきました。また、この時期からARCの頻度も増えてきてよく参加していました。ABCよりrateが上がる確率や幅が大きいことが多かったのでできるだけ出るようにしてました(ダメだった時の影響も大きいけど)。なので、ABC-Dが解けそうになってきた方はARCをお勧めします！

また速解きができるよう、スニペットが載っているサイトをブックマークしていました。他にも自作のライブラリなどを持っていると実装がすぐできると思います！特に数学的な問題はgoogleに頼る方がいいですね。

「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 - Qiita

AtCoder 版！マスター・オブ・整数 (素因数分解編) - Qiita

巡回セールスマン問題をビットDPで解く (C++) - Qoosky

中には素因数は何種類あるか？って問題で2つ目のサイトをそのままコピペして最後だけ変えれば即ACという時もありました。コンテスト中は理解は後回しで、終わってから理解でも良いのかなと思っています(ペナ吐いたら考え物だけど)。

あと有難かったものとして、解けなかった問題の類題を彼が教えてくれる時がありました。リベンジという面でモチベにもなりますし純粋に経験値を多く得られます。上級者の知り合いを作るのが一番良い手かもしれません。

この時期はコンテスト参加すればほぼ毎回highestを更新していました。

この頃、鬼滅の刃は全く知らないのですがコンテスト前に紅蓮華を聞いて強くなれる理由を知ってました！(笑) しかし入水目前でまたしても停滞期が…

第二停滞期

この頃の心の叫びです。

色変前はよくあること、水パフォが全く出ないってことはないからいずれなるだろう、と思うようにしました。rateは下がってはいたのですが、大きく下がりはしなかったのでまだよかったです。

しかし、状況打破のためにこのようなことを始めました。

これは今でも続けています。思い立った時にやるよりかは、毎日少しでも競プロに触れることでアルゴリズムや実装法など忘れにくくなります。毎日時間を取るのは難しいですが、実装しなくても問題を考えることが重要だと思います。おそらくこのレベルになると、頭に浮かんだ方法を考える方が、それを実装する世にも遥かに難しいからです。私は毎日家に引きこもっているので時間は簡単に作れるのですが、そうでない方で停滞している方は是非やってみてください！

最近はこれをよくやっています。★4,5あたりは解けなくて解説を読むことが多いですが、よくある解法を頭に落とし込めるのは良い経験になります。

atcoder.jp

その結果もあって、週末二つのコンテスト(ABC, ARC)で150以上も上がり入水できました！ この日は誕生日でもあったのでWでお祝いでした！

個人的なコンテストの挑み方

コンテスト前

  • ルーティンを大事にする。コンテスト中は音楽を聴きながらやっているのですが、好きな音楽を最初にかける。紅蓮華効果は絶大だった(rate下がったらやめた)。
  • エディタの準備を怠らない。提出する時にそのコンテスト用のディレクトリにすぐアクセスできるようにしておく。
  • 好きなものを食べる！(揚げ物食べた日の調子はすごくいい)

コンテスト中

  • 時間的計算量をまず考える。N=105 だったらO(N), O(N logN)で解けるからその方法を考える。N = 1018ならO(1)で解ける。などなど
  • Nosubを考えない。考えると集中できなくなる。

コンテスト後

  • twitterで他の方の解説や解法を確認する

さいごに

ここまで読んでくださった方、ありがとうございます。もしよろしければ是非感想をリプなりしていただけると嬉しいです。色変記事書くのは初めてなので、こういった情報もあると良いよなどあれば是非教えてください！

入水が目標だったので入青は今のところあまり考えてないのですが、もっとモチベが上がれば頑張ってみようと思います。入青出来た際にはまた記事を書こうと思うので読んでいただければと思います！