ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AtCoderで青色になりました

番外編

ということで、色が変わると自分語りの記事が書ける(要出典)ので、書いていきたいと思います。この手の記事は初めてなので、今までの推移をまとめて書きます。

目次

それぞれのレート帯でやったこと(だいたい)

～緑

AtCoderを始める前、大学の講義でDFSや再帰を多少書いたことがありました。
プログラミング自体はその講義中では得意だったので、ABCのA、Bレベルについては（文字列でなければ）ある程度、はやときができる、というレベルでした。
AtCoderを始める段階で蟻本を買ったのですが、当時は初級編の序盤を少し読む程度でしたし、特別モチベがあるだけ精進をひたすらやる、といったことはしてなかったと思います。
アルゴリズムのテクニックとしては、累積和、基本的なDFSといったぐらいで、あとは多少の高校数学の知識といった感じです(記憶があいまいなので違っていたらごめんなさい)。

～水色

まずやったのは、けんちょんさんによる蟻本類題まとめをひたすらとくことです。
これにより、競プロで頻出のアルゴリズムの知識を習得、定着させていきました。
と言いたいのですが、実はDPが出てきたあたりまでしか埋まっていません…
ICPCの過去問も合わせてちらほら埋めつつ、基本的にはコンテストに出て、そこで知らなかった知識やテクニックをどんどん蓄えていく、というような形で実力を伸ばしていきました。

～青

ひたすら過去問を埋めました。いろんな方法でモチベを維持しつつ(元々好きなので全く苦ではないですが) 、考察力や知識を増やしました。
現時点で知っている知識(?)を羅列していくと、
BIT、最大流・最小カット(燃やす埋める)、LIS(二分探索のDP)、LCA、RMQ、セグ木、Trie木、Union-Find木(重み付きも)、DP(通常、bit、戻す、桁、区間、etc)、累積和・いもす法、しゃくとり法、エラトステネスの篩、グランディ数、ダイクストラ法、ベルマンフォード法、ローリングハッシュ、ワーシャルフロイド法、二分探索、全探索、包除原理、区間スケジューリング、半分全列挙、BFS、DFS、座標圧縮、GCD・LCM、最小全域木、貪欲法、逆元、行列累乗
ぐらいですかね…？(漏らしがある可能性もあります)
ちょろっとした知識で殴る、といった解き方をするためにとりあえず身に着けた、みたいな浅い知識もあります。

心がけたこと

あくまで個人の経験から出た1つの考えなので、参考程度です。

コンテストに出る

これだけ頻繁にコンテストがあるので、これに出ない手はないです。

復習をする

できなかった問題をそのままにすると、類題が来ても解けるはずがないです(解説を読んだだけでできるようになる人、見かけるのですがうらやましいです)。基本的には、自分がある程度考察を行った問題については近いうちに実装するようにしています。が、これを最近怠っているので今後の課題です。
似たような理由で、考察を終わらせた問題を放置しないようにしています。実装面で複雑な、ミスの起こりやすい箇所がわかったり、実はこういう部分がまだよくわかってなかった、というのはよくあります。

no submissionをしない

これは賛否両論あります。自分がこれをしないのは、レートの価値がうんぬんとかではなく、単純につまらないからです。
自分は一回だけno subをしたことがありますが、その日のコンテスト後は非常につらかったです。というのも、Twitterを見ていると、色が変わった人、それに対しておめでとうリプを送る人、考察ツイートをして議論している人、といったように、皆楽しそうにしているのにも関わらず、自分だけno subをしていたため、孤立感がありました。

とりあえず、しばらくはこの方針を続けようと思っています。

ブログで解説記事等を書く

自分の考察仮定や、このような問題ではどういう解き方だったか、このアルゴリズムを使う問題はどんなものがあったのか、等を調べるのに向いています。あとは、解説記事を書くことで、実際は抜け落ちていた考察や、あいまいな理解をしていた部分が浮き彫りになったりもします。加えて、これだけの量解いたんだ、という自信にもつながります。
そして、自分がわからなかった場合にほかのブログを参考にすることが多いので、少しでも恩返しになればと思っています…
単純に自分の思考をアウトプットできるのが楽しいです。コミュ力がないわりに語りたい人間なので。
最近は説明が難しい問題の解説記事を断念していたりもするので、今後はそれが減っていくといいですね…

ライバル、友人を作る

一緒に競い合えるライバルがいると、モチベーションはもちろん向上します。できれば、実際に会っていろいろ話せる人だとなおいいかと思います。
また、強い人をTwitterでフォローしたり、大学の先輩を探すといいと思います。何かあったときに聞けるというのは、それだけで安心感が違います。基本的に自分は強い人を見たときに、憧れ、いつかああなりたい、と思うタイプなので、またモチベーションが向上します(これは人それぞれで、落ち込んでしまうタイプの人もいると思います、自分も落ち込む場合もあります)。


問題を解くにあたって

とりあえず、現時点での自分の思考方針を書いておきます(今後時がたったときに思考過程を比較したいためです)。

計算量を見る

自分の中ではこれが最重要と言っても過言ではないぐらい大事に思っています。
特に、 N \leqq 12みたいな制約は、自分の中では現状O(2^{N})が絡むような問題しか解いたことがないので、だいたいbitDPを思い浮かべます。
他にも、O(N^{3})が通らないからO(N^{2})を考えよう、もしくは高速化してどうにかしよう、とか、N \leqq 10^{18}なのでO(1)、O(log N)か、もしくはそもそもこの部分は最終的な計算量には絡んでこないだろう、とか、自分の知っているアルゴリズムの計算量と照らし合わせて方針を立てたり、もしくは何も想像がつかなければとりあえず飛ばしたり、実験をしてみたりしよう、となります。
ので、問題を読んだ時点でこう！とならなければ、まず制約を見ます(なにか思い当たる解法があっても、通ることを確認するために見る必要がありますしね)。

典型知識と照らし合わせる

例えば、”最大値の最小値を求めよ”みたいな問題に置き換えられると、とりあえず二分探索をしたくなります。
正直、これ以外にはっきりこれ！みたいなのが思い浮かばないのですが、後ろから貪欲したくなる問題、ソートして見通しをよくしたい問題、偶奇や余り、真ん中に注目したい問題等々ふわっとした方針を探ってみたりします。

実験する

本当に何もわからなければ、小さなケースで実験をしたり、いろいろこねくり回して重要な法則等を見つけます。この部分がかなり運なので、ここら辺をどうにかしていきたいと思っています(上記で終わるような問題を増やすことも大事なのでしょうか…)
難易度が近い問題がほかにあれば、そっちに一旦逃げるときもあります。

その他、競プロ関連でやったこと等

オンサイトのイベントに出る

青になるまでに、オンサイトのイベントにいくつか参加しました。
一応、日経コンの懇親会にも参加はしましたが(順位が4桁だったのですが繰り上がりに繰り上がった結果参加することができました)、予選を通過してオンサイトのコンテストに出たことはまだないです。
応募制のオンサイトイベントにも参加しました。 ACPC,ゆるふわ競プロオンサイトです。
どちらも、目の前で有名な競プロerさんたちがわいわいやっているのを見たり、実際にチームを組んだり、お話することができたので、いい経験になりました。

会津大学競技プログラミング合宿2018参加記 - ツバサの備忘録

ゆるふわ競プロオンサイト参加記 - ツバサの備忘録

ICPCに出場する

大学の同学年の友人と一緒に国内予選に出場しました。
当時は2完でしたが、今年は頑張りたいです。

ICPC国内予選2018に参加してきました - ツバサの備忘録

有志のコンテストを開く

大学の先輩方のお手伝いをして、WUPCを開催しました。
作問するのは初めてだったのですが、2問も出題できたので、とても嬉しかったです。

WUPC2019のお話(解法編) - ツバサの備忘録

WUPC2019のお話(有志コンテストの準備編) - ツバサの備忘録

マラソンに出場する

初めてマラソンにも挑戦しました。
いきなり2週間のコンテストだったので、時間の使い方は間違いなく失敗しましたが、そこそこの順位で入賞できたので良かったです。

北大・日立新概念コンピューティングコンテスト2018 - ツバサの備忘録

バチャコンを開く

定期的に開きました。
AtCoderのものもそうですが、一時期AOJでICPCのバチャを開いたりもしました。
大学の空きコマ等を利用し、友人たちで集まって、勉強会のような形でバチャコンを開催し、感想戦をやってワイワイします。他にも、大学の先輩達が行っているICPCの練習会に参加したりもしました。
加えて、WAsedapracticeというバチャを開催し、大学の友人に競プロを布教したりもしました。
毎回参加してくれる方や友人には感謝しています。
(が、今は中断しています)

WAsedapracticeについて - ツバサの備忘録

これからやりたいこと

もちろん黄色にもなりたいのですが、まずは青パフォを安定させたいです。
まだ700点問題をあんまり解いていないので、それらを解けるようにすることと、5~600点問題を現在の400点ぐらい安定させたいです。
そして、ICPCの国内予選を抜けたいです…
同学年の3人でチームを組み、抜けたいですね。今年はしっかり練習もしたいところですが…？
あとは、競プロに限らず情報系のいろいろな知識をつけたいです。
上位勢のツイートを見ていると、競プロに限らず深い知識を身に着けている印象があります。僕もああなりたいです。
めちゃくちゃスマブラをやりたいです！！！！

終わりに

ここまで見ていただきありがとうございました！！！！
しばらくは浮かれていそうです