Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

AtCoderで青になるまでに「できた」こと

昨日上げた記事「AtCoderで青色になるまでにやったこと」は本当にただ「やったこと」だけをまとめた記事だったが、他の方の記事を見ているとどうも「持っている知識」とかをまとめる傾向にあるらしい。

実際に何をしたかを書き連ねるよりも「青色になったとき何ができたか」をまとめた方が確かに為になるだろうと思い、続編としてこの記事を書くことにした。

目次

探索系

深さ優先探索(DFS)

全探索の基本中の基本。再帰関数の一部を抽出したようなアルゴリズムだと思っている。

主な用途はグラフの頂点の全探索だが、「高橋くんのバグ探し」で多重forループをDFS(というよりは再帰関数)で書けると知ってからその手の問題にも対応できるようになったりした。

幅優先探索(BFS)

DFSの兄弟的なやつ。迷路や重みなしグラフの最短路探索に大活躍。

最初の頃は「DFSより難しそうだなぁ」とか思っていたが、今の私はDFSの10倍くらいこっちの方が好き。main関数の中に埋め込めるからかな。

next_permutation

アルゴリズムではないが、順列を昇順に全探索できるalgorithmライブラリの関数。

最初はよくわからないやつという印象だったが、「Diverse Word」の解法で衝撃を受けてから付き合い始めて今ではだいたい使いこなせるようになった。

bit全探索

全要素の「使う/使わない」を愚直に全通り調べる。ザ・全探索というアルゴリズム

シフト演算子や論理演算子を駆使するので、分からないうちはコードの解読に苦労した。 発展的な回し方(要素数が一定とか)はまだよく分かっていない。

動的計画法(DP)

一部の結果をメモすることで、愚直な全探索を効率よくやる手法。 代表的な応用例として「ナップサック問題」が挙げられる。 応用の幅が広く、「メモ化再帰」「累積和DP」「bitDP」とか色々ある。

確かに汎用性は高いのだが、高すぎて

  • 気づくのが難しい
  • 漸化式に漏れが出る
  • 実装でバグる

という正に競プロの闇的なアルゴリズム。 行き当たりばったりでやると99%バグるので、漸化式をきっちり立ててから実装するようには意識している。

二分探索(にぶたん)

探索範囲を半分にしていくことで、logオーダーで目的の要素を探し出すアルゴリズム

2ヶ月ほど前までは終了判定でバグりそうなイメージがあって苦手だったのだが、区間を半開区間でもつ方法1に出会ってからめっきりバグらなくなった。圧倒的感謝。

尺取り法

探索区間の右端を伸ばせるだけ伸ばして、伸ばせなくなったら左端を右に1つずらして、ってのを繰り返すアルゴリズム。名は体を表す。

左端が右端を追い越さないようにとか番兵を置いたりとか、少し頭を使わないとバグりがち。にぶたんで代用できることもままある。

グラフ

Dijkstra

負の経路がないグラフの最短経路を求める代表的なアルゴリズム。BFSの進化系的なやつ。

みんなだいすきDijkstra法。最初は実装が重くて手が出しづらい印象だが、慣れた今となってはお友達。 つい先日「Dijkstraに関するn考察」という記事も書いたりした。

Bellman-Ford法

負の経路を含むグラフでも最短経路を求められるアルゴリズム。負のループも見つけられる地味にスゴイやつ。

やはり競プロの世界ではDijkstra法の影に隠れてしまう印象がある。 私自身、「Score Attack」以外でまともに扱ったことがない。 いつまたこれを使った問題が出るかとヒヤヒヤしているが、意外と出ない。

Warshall-Floyd法

全部の2頂点間の最短距離(全点対最短経路)を出せるアルゴリズム。実装がforの3重ループだけで書けて非常に楽。

たまにforを回す順番を間違えたり対角成分を0で初期化し忘れるのが怖い。実のところ、なぜこれでちゃんと動くのかをよく理解していなかったりする。

Union-Find

互いに辺で繋がった頂点の集合を管理するデータ構造。

これも最初は理解に苦労した。今でも完全に理解してるかというと少し怪しいところがある。 実装は面倒なのでクラスライブラリをぺたーで済ませている。オブジェクト指向バンザイ。



上を見ての通り、青になった時点で「最小全域木(Prim法, Kruskal法)」「ネットワークフロー(Ford-Fulkerson法, Dinic法等)」は使えなかった。後者はともかく、前者は意外と今まで出てこなかった。

今では「Built?」で Kruskal法 、「浮気予防」で Dinic法 のクラスライブラリを作ったのでこの2つは一応使えるが、自力で一から実装するのはしんどい(特にDinic法)。

データ構造

セグ木? BIT? RMQ? 知るかんなもん。 というわけで青になった時点ではUnion-Find、STL以外の主要なデータ構造はまるで使えなかった。これはひどい

今では「プレゼント」で実装した BIT のクラスライブラリを持っているが、セグ木はまだ実装したことがない。

実のところ、ARC-Dレベルでは上のようなデータ構造を扱う問題はまず出てこない。これでも青色まではたどり着けるものなのだ。 ただARC-Eではバンバン出てるはずなので黄色はその限りではなさそう。蟻本読みます。

数学的知識

これでも大学生なので高校数学の基礎は一通りマスターしているつもりだが、果たして。

それに加えて線型代数の基本くらいはわかる。 競プロでもたまに行列の積でダブリングする問題とかあるので、線型代数もないがしろにできたものではない。

競プロで主に使われる数学的知識も知ってる範囲でまとめておく。

組合せ、確率

下手なアルゴリズムよりよほど大事。 当たり前のように重複組合せを使う問題が出てくるのでビビる。

ただ、下手に知識があると数え上げ問題も数学的知識で上手いことやろうとしてしまうので、その辺の切り替えが難しい。

整数論

N進法とか最大公約数とか素数判定とか。

この手の問題は数に対する深い洞察が必要なことが多いので、日常的に数に触れている人は本当に強い。 一方で典型的な思考方法は過去問から得られるものが非常に多いので、経験値がものを言う分野でもあると思う。

modulo演算

「109+7で割った余りを求めよ」系の問題で必要となる知識。高校数学でもそこまで深くやらないので、ちゃんと勉強する必要がある。

Fermatの小定理」とか「中国余剰定理」なんて競プロやる前は名前くらいしか知らなかった。「逆元」に至っては感動すら覚えたしめっちゃ便利。

幾何問題

図形とか距離に関する問題。苦手とする人が多い印象がある。

幾何問題の厄介なところは、解法がたくさんあること。実装がクソ重い解法しか浮かばないと鬱になる。

あと浮動小数点を使わないといけないのもツラい。誤差でWAになるとなんとも言えない気持ちになる。

行列

先にも述べた通り、行列の積をダブリングと組み合わせた問題が稀にだが出る。フィボナッチ数を高速に求められたり、地味に実用性が高い。

その他

imos法

「特定の区間に一気に同じ値を加える」というクエリを、処理→累計という過程を踏むことで高速に行えるアルゴリズム。詳しくは本家解説ページをどうぞ。

とある問題の解説で知って、初めて上の本家解説ページを読んだときはとても感動した。考案者は天才か?

ダブリング

累乗のような繰り返しの操作を、半分に分割していく(?)ことでlogオーダーまで計算回数を減らすアルゴリズム、というよりテクニック。

主には階乗の逆元を求めるときに使うが、他にも応用できる場面は多い。 これは勉強したというよりは自然と身についていた印象がある。



この系統でまだ使えない技術として「座標圧縮」とか「Grundy」がある。前者は何がしたいのか自体は分かるが実装が大変そう、後者はゲーム問題に使えるくらいしか分からん。どちらも今後使う機会がありそう2なので、なんとか克服せねば。

あとがき

以上が私の使える主なアルゴリズム、データ構造、テクニックである。またずいぶんと長い記事になってしまった。

ただ、正直なところ私がここまで来たのは知識より地頭によるところが大きいと思っている。事実、ここ最近でのAGCとARCの成績は前者の方が全て上回っている。

しかし、ここから先は地頭でなんとかなる領域ではないだろう。やはりしっかりと知識を身につけ、練習して使いこなせるようにならねば。


  1. 一部で「めぐる式にぶたん」と呼ばれているもので、こちらが名前の元となったツイート。めぐるちゃんかわいい。

  2. そんなこと言ってる間に先日のcodeFlyer予選で座標圧縮の問題が出てしまい、お気持ちになるMisterであった。