10年間の競プロAdventCalenderの記事を振り返る

競プロAdventCalender2020の21日目の記事です。2011年から始まったこの競プロAdventCalenderも今年でついに10年目。この間に日本ではAtCoderが誕生し、IOIの日本大会が行われるなどますます競プロ界隈は広がりを見せています。自分もその中で毎年AdventCalenderに記事を投稿し続けて来たので、10周年記念ということで振り返っていこうと思います。

ちなみに自分の去年までの記事ははてなグループに書いてきたのですが、はてなグループ閉鎖に伴う移行作業をすっかり忘れていたために闇に葬られ…そうになったのですが、しょラーさん(@shora_kujira16)がアーカイブを作成してくださったことにより無事に振り返りを行うことができます。この場を借りて感謝いたします。

1年目：好きなアルゴリズムとSRMの問題について

好きなアルゴリズムとSRMの問題について - skyaozoraの日記 - TopCoder部

記念すべき初の競プロAdventCalender、そこに私が投稿した記事がこちらになります。当時はまだAtCoderは無く、Codeforcesも出来てから日が浅かったということで競プロ＝TopCoderという時代でした。当時のTopCoderで個人的に印象深い問題をいくつか紹介しています。最近のAtCoderでもよく出るような問題かとか、難易度を比較してどんな感じかとかは正直よく分かりませんが、どれも割と面白い問題だと思いますので是非解法を考えてみて下さい。

2年目：競技プログラミングの練習法について

競技プログラミングの練習法について - skyaozoraの日記 - TopCoder部

今度は特定のアルゴリズムや問題という方向ではなく練習法について書いてみました。正直今見てもいい内容だなと自画自賛するというか、今だったら練習にはTopCoderよりAtCoderの問題を使うべきだとは思いますが、それ以外の内容に関しては今見てもかなり多くの人にとって役に立つのではないかと自負しています。ただ練習環境という点では、今はバチャコンがあったりとか色々本当に進化しましたねぇ。

あと練習法と直接関係はないですが、やっぱりオンサイトイベントに行って他の競プロerの方々と交流するのはめちゃくちゃモチベーションが上がります。最近はこんな情勢でオンサイトイベントは壊滅状態ですが、来年はまた開催されるようになるといいな…。

3年目：解法に衝撃を受けた問題たち

解法に衝撃を受けた問題たち - skyaozoraの日記 - TopCoder部

この年はネタが思いつかなかった上に卒論の提出直前で時間がなかったのでそうとう簡素な内容になってます。ただ2つ目のWindPassagesは本当に解法を知った時に衝撃でした（実際AOJ-ICPCでも☆が相当ついていますね）またこの記事を書いた約半年後のGCJ14R2のC問題がこのアプローチで解ける問題で、自分もここでまとめておいたお陰かすぐ解法が浮かんで解けましたし、他の参加者の方にも「この記事を読んでたお陰で解けました」と言ってもらえたりと、長さの割には役に立った記事なんじゃないかなと思っています。

4年目：競技プログラミングでたまに使われる名前の付いてないテクニックについて

競技プログラミングでたまに使われる名前の付いてないテクニックにつ - skyaozoraの日記 - TopCoder部

(これタイトルが長すぎた所為か途中で途切れちゃって修正できないんですよね…ｗ)

4年目にして初めて特定のアルゴリズム・テクニックについて説明した記事になります。このテクニックは最初それを使う問題に出て全然何のことかわからなかったものの、他人のコードを読んだりしてるうちにようやく理解できて、自分でこうやって説明できるまでになった、ということで自分の中でもかなり印象深かったりします。ただこうやってsetのiteratorを使っていろいろやって…みたいなのは、最近はそれが本質みたいな問題はまず出なくて、あくまでもっと難しい問題の一部として出るって感じですよね。時代の流れを感じる。

5年目：もうひとつの箱根駅伝(AOJ2439箱根駅伝裏話)

もうひとつの箱根駅伝（AOJ2439箱根駅伝裏話） - skyaozoraの日記 - TopCoder部

これは自分の数少ない作問の中で唯一の良問である箱根駅伝の作問の裏話および別のアプローチでの解き方を紹介しています。ここに書いてある通り設定は見たまんまだし、解法は自分以外の人から降ってきてそれがかなり綺麗かつ応用範囲の広い解き方で、その結果今でも言及が行われるくらいの人気問題になって、我ながら凄く運がよかったなと思ってます。この解法のような考え方は順列関連のDP・数え上げで必要になる事は今でも相当ありそうですね。

6年目：競プロを始めての10年を振り返る

競技プログラミングを始めての10年間を振り返る（前編） - skyaozoraの日記 - TopCoder部

競技プログラミングを始めての10年を振り返る（後編） - skyaozoraの日記 - TopCoder部

(今並べてみて初めて前編と後編のタイトルが微妙に違うことに気が付きました)

自分は2006年にJOIの予選に初参加したので、そこから競プロを始めたと考えるとこの年にちょうど10年経ったことになります。なので競プロを始めてからこの時までの10年を、1年ずつその年にあったイベントや各種コンテストサイトでのレーティングの変化も交えつつ振り返ってみました。

今見てもさらに懐かしいです。最初は全然問題が解けなくてTopCoderの灰色から抜けられなくて、それを思うとよくここまでこれたなと。あと実力もそうですが、ここまで長い間競プロを好きでいられたこと自体が嬉しいです。というか今見たら競プロ始めてから14年なのでもう人生のほぼ半分は競プロをやってることになりますね（まぁ最近はやってると言えるかというとだいぶ怪しいですが…）

7年目：インラインDPというテクニックに関して

「インラインDP」というテクニックに関して - skyaozoraの日記 - TopCoder部

恐らく自分のAdventCalenderで一番多くの人に読まれたであろう記事。よく「実家DP」とか言われたりするのは中身を表してなさすぎだろと思ったので、テクニックをまとめるとともに妥当っぽい名前として「インラインDP」を提唱しました。後から「In-PlaceDP」の方がより表しているのではないかという意見が挙がってなるほどなと思いましたが、まぁどちらでも分かりやすい方をお使い下さい。

この概念も自分は最初はよく理解できて無くて、やっと理解できて暫くは「知ってることで他の人に差を付けられる」状態だったのですが、これもあっという間に「知らないと他の人に置いて行かれる」レベルの知識になってしまいましたね。

8年目：ConvexHullTrickを分割統治法で殴る

ConvexHullTrickを分割統治法で殴る - skyaozoraの日記 - TopCoder部

ConvexHullTrick(よくCHTと略されますね)は一時期それなりの頻度で出題されていました。それをちょっと別の角度から解いてみようという記事です。個人的にはCHTを素で書こうとするとかなりバグが怖いのでこっちの方針の方が好きなのですが、まぁここは個人差ですね。

9年目：数学とゲームが大好きな競プロ勢の皆様へ

数学とゲームが大好きな競プロ勢の皆様へ - skyaozoraの日記 - TopCoder部

さて、最後はほぼ競プロが関係ない記事です(笑)バックギャモンというボードゲームを数年前から始めたのですが、最近特にハマってきたので紹介しました。まぁ全く競プロに関係ないわけではなく、このバックギャモンではサイコロを振るゲームなので最善手(最も勝つ確率が高い手)を選ぶために常に確率計算が必要なので、そういう意味でも競プロ勢の皆さんも楽しめそうということで紹介させていただきました。

10年目：10年間の競プロAdventCalenderの記事を振り返る

当記事

という訳で10年間の記事を振り返ってまいりましたが（本当は9年しか振り返ってないのは秘密）、改めて自分が競プロをやって来た時間の長さを感じましたね。最近はコンテストからも離れがちですけど、それでも自分が競プロをやってきたことで得られた繋がりとか諸々は本当に大きいなとたびたび実感します。

競プロAdventCalender主催のmatsuさん、そしてかつて主催をされていたtanzakuさん本当にありがとうございます。来年も競プロ界隈がさらに盛り上がることを期待しつつ、そしてコロナが収まってまた各種オンサイトイベントが開かれるようになることを祈りつつ、よいお年を！