こんにちは、ふるやん（@furuya1223）です。
先日、スライド投稿サイト SpeakerDeck に「ABC 緑 diff を攻略する」というスライドを投稿しました。
スライド URL : https://speakerdeck.com/furuya1223/the-view-of-green-difficulty-problems
このスライドは、最近の ABC（いわゆる令和 ABC）の緑 difficulty の問題を解くための考察のコツをまとめたものです。
もともと、スライドを基に動画を作って YouTube に投稿する予定だったのですが、動画にするメリットも無いかと思って（面倒なのもあって）諦めました。
とはいえ、動画で補足するためのスライドであるため、スライドだけではわかりにくい部分もあります。
ということで、この記事で補足します。
ただ、メインパートの「考察のコツ」の部分以降については補足することが少なそうなので、とりあえずその手前までの補足を書いておきます。
（眠くなってきたからというのもある）
ちなみに、ちょうど同じようなタイミングで kami さんが考察のコツに関する素晴らしいドキュメントを公開されています。
競技プログラミングについて「アルゴリズムの典型」ではなく、「考察の典型」をまとめてみました
不十分なので少しずつ書き足すつもりです
競技プログラミングで解法を思いつくための典型的な考え方 | アルゴリズムロジック https://t.co/MPNUv07Bu0
— kami (@634kami) May 4, 2020
こちらは難易度に制限が無いぶん、かなり豊富な内容になっています。
また、私のスライドは汎用性の高い方針を載せていますが、こちらの記事はアドホックな考察方法もたくさん載っています。
もっと難しい問題の考察方法を知りたい方や、私のスライドでよく分からなかった方はぜひ御覧ください（勝手に宣伝）。
それでは、スライドの章立てごとに補足を書いていきます。
まだスライドを見ていない方は、上のリンクから見てみてください。
競プロで測られる能力
特に補足することはありません。
「暗記・パターンマッチだけではないんだぞ」ということが伝えたかったという部分です。
この部分は採用関係の方にも見ていただきたいですね。
あと、このスライドの内容はすべて私個人の見解であるというおことわりです。
強くなるために必要なもの
予てから私が考えていたイメージをようやく公開しました。
戦いにおいて勝敗を左右する要素は「体力」「戦術」「戦略」に大きく分けることができると私は考えています。スポーツとか、白兵戦を想像してください。
競プロの場合、「体力」はアルゴリズム・データ構造・数学の知識、言語仕様の知識、典型パターンの知識・経験、などが該当します。
「戦術 (tactics) 」が、今回テーマにしている、問題ごとの考察の方針です。
どういう方法で問題を言い換えるのが良さそうか、強い人はすぐに気配を察知して綺麗に変換していきます。
「戦略 (strategy)」は、コンテスト全体での立ち回り（順位表から取り組むべき問題を選ぶ、ペナを少なく済ませるか恐れず提出するか、など）や、勉強方法（過去問をどう使うか、新しいアルゴリズムをどう学ぶか、ライブラリをどう整備するか、など）が該当するかなと思います。
本スライドの扱う部分と、「各自でやってちょうだいね」という部分を切り分けています。
緑 diff で要求される知識
個別の記述について補足していきます。
負の数の除算・剰余
整数除算（int, long long など整数どうしの割り算）や剰余（mod、つまり割った余りの計算）は、割る数と割られる数が両方が正の場合だけにしましょう。
負でも動くことは動きますが、挙動がイメージと異なるので、使わないのが無難です。
GCC だと、-5 % 3 の値は 1 ではなく -2 になります。
計算途中のオーバーフロー
|
1 |
long long a = 1000000 * 1000000 |
と書くと、GCC では a の値が -727379968 になります。
|
1 2 |
int b = 1000000, c = 1000000; long long a = b * c; |
でも同じです。
これは、イコールの右辺が int と int の積なので、計算結果が一旦 int の領域に格納され、その結果が a に代入されるため、代入前にオーバーフローが起こっていることによる挙動です。
これを避けるため、結果が int の範囲を超える場合は、(long long) でキャストするか、long long b = 1000000 というように long long の変数に代入して計算しましょう。
long long と int の積は long long であると判断される（大きい方の型に合わせられる）ので、片方を long long にするだけで良いです。
数学の知識
知らないものがあれば調べてみてください。
計算量の基礎知識
log がつくパターンは、緑帯では知らなくても困らないとは思います。
緑帯では、log は「定数ではないけど思ったよりめっちゃ速い」ぐらいに捉えておけば大丈夫だと思います。
C++ で使える標準機能
知っておくと楽できそうなものを羅列しましたが、緑帯で特に知っておくべきなのは
vector, string, pair, set, map, queue, priority_queue, sort+begin/end
ぐらいですかね。
sort は、
|
1 2 3 |
vector<int> a = {3, 1 4, 1}; sort(a.begin(), a.end()); // ここで a の内容が {1, 1, 3, 4} になっている |
のように使います。sort(ソートする区間の開始位置、終了位置) という指定で vector などをソートできるので、begin と end で最初と最後を指定しています。
string は辞書順で比較・ソートできますが、実は vector, pair もソートできます。
A[i] でソートして、A[i] が同じ部分は B[i] でソートする、みたいなのが vector<pair<int, int>> で簡単に実現できます。
Union-Find 木は標準機能（？？？）
嘘です。Union-Find 木は標準機能ではないです。
セグメント木などのデータ構造の自前実装に手を出すのはちょっとハードルが高いかと思いますし、緑帯では必須ではないと思います。
Union-Find 木を除いて。
ということで、「Union-Find 木は実装が軽量で汎用性が高いので、自前データ構造に手を出す気持ちではなく、持ってて当たり前みたいな気分で用意しておこう」という気持ちを表現したらこうなりました。
両端から累積を計算して「1 つ以外」を高速計算
長さ $N$ の数列 A[0], …, A[N-1] が与えられたときに、「A[i] を除く数全体の最大公約数」を、$0 \le i \le N-1$ の全てについて計算したいとします。
このとき、
left[i] = A[0] から A[i-1] までの最大公約数（left[0]=0）
right[i] = A[i] から A[N-1] までの最大公約数（right[N]=0）
をそれぞれ前から、後ろから $O(N)$ で計算することができます。
これを用いて、
A[i] を除く最大公約数 = left[i] と right[i+1] の最大公約数
として計算することができます。（ $0$ と $x$ の最大公約数が $x$ になるようにしておきましょう）
めぐる式二分探索
二分探索の 2 点を表す変数を l, r というわかりにくいものにするのではなく、ok, ng というわかりやすい名前にして、更新や結果の利用をわかりやすくしよう、というようなものだと私は認識しています。
実数での二分法
実数の場合、整数のように while(ok – ng > 1) という継続条件が使えません。
while(ok – ng > eps) と十分小さい値を設定すると、誤差が原因で無限ループになる可能性があります。
なので、100 回ったら終了、など回数を固定して区間を狭めましょう。
100 回やれば区間の幅が $2^{100}$ 分の $1$ になり、これは $10^{-30}$ 倍よりも小さいので、だいたい十分でしょう。
ちなみに、最近知ったのですが、実数で二分法による探索を行う問題では、相対誤差が要求されるので、更新を $m=\sqrt(lr)$ で行うのが良いらしいです。別に気にせず $m=\frac{l+r}{2}$ とやっても問題無いです。
グラフを扱う
最初は、グラフは
vector<vector<pair<int, int>> G;
とするので良いと思います。G[i] が頂点 $i$ から出る辺の配列を表し、辺は (行き先頂点番号, コスト) の pair になっています。
辺にコストが無い場合は、vector<vector<int>> で良いです。
コスト 10 の辺 0→1 を追加する場合は、G[0].push_back(make_pair(1, 10)) などとすれば良いです。
複雑なグラフアルゴリズムを扱うようになると、クラスを作れば良いと思います。
デバッグ力（りょく）
d という名前の変数を作ってあるのに新たに rep(d, 4) をしてドツボにはまった経験があります。
開発環境やコマンドでデバッガを使うともっと良いと思うのですが、緑帯では printf デバッグで問題無いと思います。
私なんかいまだに printf デバッグです。
興味のある人はデバッガについて調べてみるのも良いと思いますよ。
以上、とりあえず途中までのスライドの補足でした。
この後の内容については、気が向いたら補足を追記するかもしれませんし、しないかもしれません。
質問などあれば私のツイッターアカウントか匿名質問サービス「マシュマロ」に投げてください。
私のマシュマロのページ : https://marshmallow-qa.com/furuya1223