【AtCoder】地道に緑色になるためにやればいいこと #AtCoder

2023/11/26 問題数や傾向の変化により、情報が古くなっています。ご注意ください。

2024/3/9 この記事はもう完全に古いです。
D問題がDP, BFS, DPSのいずれかになっていた時代は終わりました。これからは SegTree の時代です。

導入

おととい、緑コーダーになりました。

インターネッツにはウナギ登りで楽々緑を突破して寒色に突入していくグラフばかり見られますが、僕はこの通り、ちょっと苦労して緑に辿り着きました。
途中で茶色より上のパフォーマンス出せね～と思って1年ぐらい放置して。（途中未練でちょこちょこやってたりもして）

しかし、ウチの大学の電子情報学科のアルゴリズムの講義（講義はこちらで公開されています）をきっかけに、もういっかい競プロ熱が入り、平均的に緑パフォーマンスを出し続けることで緑入りを果たしました。

現環境（ABC参加人数9000人）だと2200～3000位ほどが緑ゾーン、一般的に終了時間ギリギリでA～G(+Ex）のセットの中でD問題まで解ききれば、このゾーンに収まるかと思います。

このゾーンに収まるのは体感として高度な技術はいらず、勤勉な取り組みで緑入りを果たせるかと思いますので、緑入りするのに必要だと感じた技術項目について列挙してみたいと思います。

必要なもの

良い環境

筆者はC++で取り組んでいますが、こちらの環境構築を施しています。
要するに、コマンド一つでテンプレートがA～G問題まで用意され、ショートカットキーでビルドできるという環境です。
そして、テンプレートを充実させています。

記法の簡略化

入出力

それと、別のファイルにコピペ用の関数集を用意しています。

「めんどくせえけどよく書くだろうなぁ」という処理を順次追加していくことで、だんだん充実していきます。

時間計算量をおおざっぱに予測する姿勢

AtCoderの解説を見るとO(nm)とか書いてありますよね。あれはビッグオー記法というものです。
コードの速さは、単純なコード整形による定数倍高速化なんかよりも、計算量オーダーを減らした方が格段に向上します。これが競プロにおいてPythonでもC++でもいいといわれる理由ですね。筆者はC++使いますが。
例えば$O(n^2)$から$O(n)$に削減出来たら、n=1E5の場合単純に1E5倍高速になります。ちょっとコードを整形して重複をなくして2倍高速になったぐらいなどとは比べ物にならないですね。

計算量オーダーを予測するのはとりわけ難しいことではなく、単にforループをどれだけネストしているのか見て、何回計算することになるか掛け算することで事足りることが多いです。
例えば

for (int a = 0; a < n; a++){
    for (int b = 0; b < m; b++){
        //単純な処理
    }
}

このコードなら、とりあえずm回のループの中にn回のループがあるので$O(mn)$オーダーだとわかりますね。中身の処理も繰り返しになると増えますが。

あとは、例えばペアを組むなどで、$nC2$ならば、展開すると$(n^2 - n)/2$なのでオーダーは$O(n^2)$だね、あたりのことを把握しておけば大丈夫です。

オーダーの概算をどう活用するのか？
問題文の制約の欄で、各変数がどれまで大きいかを見ることが重要になります

例えばABC302 B問題
これは$m \times n$のグリッド上から文字列snukeを探せ、という問題。
単純な発想だと「全点についてsnukeがあるか判定する」という処理をすればいいですね？
そのオーダーは$O(mn)$。安直すぎないか、オーダーが大きすぎるんじゃないかという心配をするかもしれませんが、制約を見れば

こんな感じ。
すなわち、$m \times n$は高々$100 \times 100 = 10000$回分ですね。パソコン様ならそれぐらいの計算余裕でできる。
すなわち、制約で上限が小さい変数は、オーダーが多少大きくなっても耐えうるといえます。

一方で、例えばABC315 D問題
問題の説明はメンドウなので省きますが、これは安直な実装だと$HW(H+W)$オーダーになるところ、

このような制約で、けっこう大きくなる。そこで、cは英小文字→26種類であるところから、オーダーの変数を$H$ないし$W$から$c$にすり替えられないか、という発想が生まれます。まあ、この問題は難しいですけど＾＾；

要するに、計算量の概算と、制約の大小の確認の姿勢が重要となります。

アルゴリズム知識：全探索、再帰、DP

D問題まで解くだけなら、ダイクストラ法やらワーシャルフロイドやらの中等以上のアルゴリズムまで求められることは少なく、全探索、再帰、DPさえできればなんとかなることが多いです。

全探索

全探索といっても単純な全探索で、例えば先ほどの例のようにグリッドが与えられたらグリッドの全点を確認するなどといった素直な実装です。
先ほどのように「変数の上限が小さい場合」に有効で、B問題だと素直な実装で通る、C問題はオーダーを減らす一工夫が必要、といったイメージがあります。

再帰

全探索の特殊な場合です。
賢き皆様は幅優先探索、深さ優先探索、再帰を正しく使い分けていますが、D問題までなら再帰だけでこの3点を賄えます。

ABC315E

//ll = long long
void read(unordered_set<ll>& readed, queue<ll>& reading_queue, ll book, vector<vector<ll>>& p){
  if (setExists(readed, book)){
    return;
  }
  
  for (ll toRead: p[book]){
    if (!setExists(readed, toRead)){
      //再帰
      read(readed, reading_queue, toRead, p);
    }
  }

  if (!setExists(readed, book) && book != 0){
    reading_queue.push(book);
    readed.insert(book);
  }
}

こんな感じに！注意点としては、関数に集合などを渡すときは 参照渡し を行いましょう。でないとメモリが、死にます。

DP

再帰ほど頻度は多くないですが、DP問題もD問題として出題されることがあり、現環境ではだいたい2500人ほどがちゃんと対応できています。緑入りには必須技能でしょう。学びましょう。

適切なデータ構造の使用

「アルゴリズム本でデータ構造というのやったけど、全部リスト（C++ならvector）で済ませちゃってる、そして時々意味が分からず（解説とそんなに違わないアルゴリズムなのに）TLEしちゃう」茶コーダー、いらっしゃいますか。
僕も最近までそうでした。
しかし、特に リストと意識して使い分けるべきデータ構造があります。 それは集合(python:set, C++:unordered_set)です。
というのも、順序に特に意味のない、そして重複しない集合はsetを使うというのは原則として把握した方がいいです。
例えば、再帰(深さ優先探索)などでもうすでに探索したポイントを重複して処理したくない、処理すると無限ループになる、なんていうときに「もうすでに到達した点」リストを作りたい。
するとこういう処理になりますね？

if point_current in visited:

ここで、もしvisitedが単純なリストだと、in演算子のオーダーは$O(n)$になるわけです。このためだけに$n$回分の負荷が掛け算されます。
こういうときにsetを使うべきです。setはハッシュ化を施しているので、in処理が高速に($O(1)$)なされます。
「順序に特に意味のない、そして重複しない集合」なんてだいたいinを使う用途ですからね。

あとは頻度が少ないけど重要なものとして、ヒープがあります。
ソートしながら要素を追加していくべき時に高速です。

あとは複数のグラフ構造がある場場合はUnion-Find(D問題までで必要になることはあんまりないですけど、、)

いかがだったでしょうか？

競プロの勉強というと各メジャーなアルゴリズムを勉強していくイメージがありますが、緑までなら勤勉に地道に辿り着けます。
僕はこれから水色へ向かって頑張りますので、皆様も頑張ってください。