AtCoder 茶～緑はバケツ（バケット）道を極めるべき！
まえがき
茶コーダーの皆さん、緑色になりたいですよね。
緑コーダーの皆さん、水色になりたいですよね。
それで、DPを勉強しなきゃ、DFS・BFSに慣れなきゃ、数学力をつけなきゃ、ライブラリを充実させなきゃ、と色々努力してると思います。
私は基礎力向上のため AtCoder Problems でDifficulty（diff）が低い問題から埋めているのですが、
茶diff上位の問題（650～700強）を解いていくうち、
「茶～緑上位で一番重要なのは、バケツとmap（連想配列）を使いこなすことじゃないか！？」
と思い始めました。
そのくらい、この辺りのdiffでバケツ・mapを活用できる問題が多いのです。
茶diff上位の問題がある程度サクサク解ければ緑どころか水色も見えるので、この辺りの問題をしっかり固めるのは重要です。
実際、私は前回のABCではのD問題（茶diff上位でした）を比較的素早く解くことができ、1382パフォが出ました。えへん。
また、前回のABC-E ・(Bullet) では、mapにpairを入れて賢く使うというバケツ道（バケツを使いこなすプログラミング術のこと）中級のテクが問われ、なんとこれは青diff中位（1836）だったのです。
その問題については記事を書きましたが、数学要素があったり、数え上げが難しかったりするとはいえ、mapが賢く使えればかなり正解に近付けた問題です。
問題の例
ここで、「この記事で言うバケツ（バケット）ってバケットソートのこと？ 何を指してるの？」という疑問を持った方や、「そもそもバケツって知らないんだけど……」という方もいるかもしれませんが、一旦置いておきまして、バケツを賢く使う＝バケツの使い方で特に差がついた問題を中心に挙げてみます。
※「バケツが使える問題」というだけの条件だと、無数にありすぎて挙げきれないためです。
ABC061-C Big Array / Diff : 745（茶）
これはバケツ（バケットソート）そのものの問題。
2017年のコンテストとはいえ、この問題まで素早く（例えば合計30分で）解ければ、パフォーマンスはなんと1349です。
AGC002-B Box and Ball / Diff : 693（茶）
なんとAGC-B！
しかも8位のsnukeさんが解いていない問題！！（もちろん、他の問題に時間をかけていたといった事情もあるでしょうが……）
ARC033-B メタ構文変数 / Diff : 704（茶）
公式解説PDFだと「ソートして二分探索」とか「setを使う」とか書いてあります。
二分探索は難しそう。setは集合演算のやり方とか計算量が大丈夫か（私は）分からない。
でもバケツなら？ シンプルに素早く書けます！
ABC159-D Banned K / Diff : 504（茶）
これ、私は詰まってしまって、解説を読んで通しました。（ていうか解説を読んでも最初分かりませんでした。）
なぜ詰まったのか？ バケツの有用性を知らなかったからです。
（diffは低いですが、上2つより難しいと思ったのでこの位置に載せました。）
ABC168-E ・（Bullet） / Diff : 1836（青）
青ォォォォいッ！！ 説明不要！！
ABC167-D Teleporter / Diff : 705（茶）
Kが物凄く大きいですが、「鳩の巣原理」とバケツを使って周期性を見つけることで解ける問題です。
これは多分緑～水以降でたまに出てくる典型なんじゃないかな？ と予想しています。
（まだ緑以降のdiffをあまり埋めていないため、本当かは知りません）
AGC036-B Do Not Duplicate / Diff : 1770（青）
これは「バケツを使って解く問題」とは言い難いですが、「高難易度帯ではバケツの考え方は活用できるのが当たり前」という例として挙げてみました。
周期性を使う解法とダブリングを使う解法があるようですが、周期性を使う場合は、上と同じく鳩の巣原理とバケツが使われます。
詳しくは、この記事にまとめました。
あとは…… けんちょんさんのブログの「バケット」カテゴリを見てください。（ひどい）
ていうか、けんちょんさんがカテゴリ作って13個も問題突っ込んでる時点で、私が記事書かなくても超重要に決まってますよね。
drken1215.hatenablog.com
バケツって何？
一番有名なのは「バケットソート（バケツソート）」ですが、この記事ではもう少し一般化した意味で使っています。
ここで言うバケツとは「配列の使い方」のことです。
くだけた言い方をすれば、バケツとは「各要素を表すラベルを貼った、各要素の情報を入れる配列」です。
（細かく言えば、「ある数列（または集合）の要素そのものを配列の添字（もしくは連想配列のキー）として使い、配列の値には出現個数や状態などの『その要素の情報』を入れる考え方」です。）
基本のバケツ
具体例と図で説明します。
＜問題例＞
「以下の入力が与えられます。各Kjにつき、数列A内に存在する各Kjの個数（Kj = AiとなるようなAiの個数）を出力してください。」
N, M, X
A1, A2, ... , Ai, ... , An （1 <= Ai <= X）
K1, K2, ... , Kj, ... , Km
（1 <= N <= 10^5, 1 <= M <= 10^4, 1 <= X <= 10^5）
＜入力例＞
5 3 9
2 1 2 7 4
7 2 3
（答え：1 2 0）
制約が小さければ、以下のような配列を作って、2重ループを回せばいいです。
（Kjについてループを回し、その中でAiについてループを回してKj=Aiとなるものを数える）
しかし、これは計算量がO(N*M)なので、制約が大きければTLEとなってしまいます。
ここで、バケツを導入します。
下図のような配列を用意して、配列の添字（0～9）を、Aiの要素としてありえる数（0～9）に見立てて、バケツ配列の値には「添字の値が登場した個数」を入れます。
（Ai=0は実際には登場しませんが、これで大丈夫）
このようにすると、今回の制約下でも間に合います。
具体的には、まず上記の配列を全て初期値「0」で作成してから、入力を受け取る時に、配列[Ai] の値に1ずつ足していきます。
入力が終わると図のような状態になりますが、ここで配列に入っている {0, 1, 2, 0, 1, 0, 0, 1, 0, 0} という値が、0～9の登場回数を示しています。
あとは、j = 1～Mについてループを回し、各ループ内で配列の値を1つずつ取り出せば、ACとなります。
＜疑似コード＞
配列
for ( i : 0 to N ) buckets[Ai] += 1;
for ( j : 0 to M ) 出力( buckets[Kj] );
ちなみに、下図のようにバケツ配列の上から順に値を取り出すと、自動的に昇順ソートが完了します。
これがバケットソート（バケツソート）です。
配列の要素にN回の +1 をして、あとはただ取り出すだけなので、O(N) でソートが完了します。
バケツの有用性
このように、バケツは要素の個数を数える問題に強いです。
せっかくなので応用をきかせたいところですが、他にはどのような問題に使えるのでしょうか？
具体的には「バケツの賢い使い方」の章でやるとして、ここでは一般的性質について書きます。
＜バケツにできること＞
・沢山ある「要素」のうちのどれかについての「情報（個数、状態、Yes/Noなど色々）」をO(1)で高速に取得・更新できる
ということで、「沢山の要素の集計」をしたり、「沢山の要素から特定の要素を選んで何度も処理をする」といったことに強いです。
＜具体的な応用例＞
・添字が順番に並んでることを利用してバケツソート
・要素を集計して、確率や場合の数などの数え上げに利用
→（応用）要素をグループに分けて数え上げ（ABC168-Eのイワシや、平方分割）
・鳩の巣原理＆隣接リスト表現で周期性を利用（後述）
バケツの注意点
このように、単純なやり方で非常に大きな計算量改善をすることができるバケツですが、弱点もあります。
＜弱点１＞
・とりえる値の数と同じ量の添字を用意しないといけないので、1 <= Ai <= 10^9 のように数列の要素の範囲が大きいと MLE してしまう
＜弱点２＞
・値が実数や文字列など、整数以外だと添字で表現できない
特に弱点1が重要で、要素の値の制約を大きくしてバケツ対策をしてある問題も多くあります。
しかしそれはバケツの強力さを表しているとも言えます。
場合によっては、これらの弱点は解消できることもあります。
ここからは、バケツの応用例を挙げていきたいと思います。
ここからが本番！ バケツの賢い使い方
連想配列（map）でバケツを作る
そもそも連想配列はバケツの進化系と考えられます。
例えば制約が「値の範囲が -1*10^9 <= Ai <= 10^9 で通常のバケツには入れられない」というとき、連想配列なら（値の種類数さえ大きすぎなければ）何でも入れられます。
バケツに bool を入れる
ここから、一気に「差がつく」テクニックになっていきます！
AGC002-B Box and Ball / Diff : 693（茶）
上の問題に目を通してみてください。
すぐ解法を思いついた人は凄いですが、茶～緑では苦戦する人も多いのではないでしょうか。
（私は非常に苦戦しました。というか解説ACしました。）
この問題は、バケツを応用（以下の3つの応用を使います）して解くことができます。
1. バケツに「個数」ではなく「今の状態（各箱に入っているボールの数）」を入れる
2. バケツを2つ使う- 1つの箱につき1つのバケツしか作れない、というルールはありません。
3. バケツに「bool」を入れる
3つ目で大ヒントを出してしまいましたが、これ以上言ってしまうと解けた時の感動が無くなりそうなのでこのくらいにします。
ぜひやってみてください。
私はこの問題でバケツが本当に好きになりました。
バケツにタプルを入れる
バケツの「値」にタプル（C++ならpairやvector）を入れたり、連想配列バケツの key や value にタプルを入れるテクニックが頻出です。
ARC033-B メタ構文変数 / Diff : 704（茶）
この問題は、大雑把に言えば「AntさんとBugくんの両方が使った単語の数 ÷ AntさんとBugくんの少なくとも一方が使った単語の数」を出力する問題です。
もちろん、制約が小さければ単に集合（set）を使えばいいですが、TLEが怖いです。
そこで、このような「2つに仕切られたバケツ連想配列」を用意します。
そうして、1つ1つのバケツのvalueには pair
＜疑似コード＞
連想配列（key := int, value := pair
for ( i : 0 to NA-1 ) buckets[i][0] = true;
for ( i : 0 to NB-1 ) buckets[i][1] = false;
これで、あとは連想配列の value を前から順番に見ていって、{true, true}だったら「または」と「かつ」の両方に入れ、{true, false}, {false, true} だったら「または」だけに入れれば完了です。
前計算 O(NA+NB), 最後の計算部分 O(NA+NB) で解くことができました。
＜発展問題＞
ABC168-E ・（Bullet） / Diff : 1836（青）
なかなか恐れ多い難易度の問題ですが、バケツ連想配列が使えれば、あとは少々の数学と、丁寧な組合せ計算（あと、MODに気を付けないといけないですが……）の問題です。
この問題を解いて、私はますますバケツ信者になりました。
バケツで「組み合わせ」を見つける
AtCoderなどの競プロの問題では、「何らかの条件を満たす組み合わせ」に関する問題が多いです。
例）条件を満たすものの個数、条件を満たす組のうち最小の○○、など
実は、このタイプの問題とバケツは非常に相性が良く、頻繁に解法として使われます。
「何かの組み合わせだ……」→「バケツか！？」と考えると、割と早く解法にたどり着く気がします。
基本的な考え方について、架空の問題例で紹介します。
＜問題例＞
N人が相互に全員とじゃんけんをします。各人（i : 1～N）の出せる手が決まっている（H1～HN）時、各人i～Nが勝てる相手の人数を出力しなさい。
＜解法＞
これは結局、ある人iについて、（ i , iが勝てる相手 ）という組み合わせの総数を求めるという「組み合わせの問題」です。
よってバケツを考えます。
＜バケツの使い方＞
すごく単純なように思えますが、緑～水くらいのDiffでも、これをするだけで解ける問題が結構あり、頭に入れておくべきだと感じます。
また、バケツに入れたものをソートしておき、二分探索などをすることによって、より複雑な「条件を満たす組み合わせ」を求めることもできます。
先日の M-SOLUTIONS プロコンオープンでは、F問題として、まさにこの考え方で解ける問題 / Diff : 2004（黄）が出ました。
（実装を簡単にするため、解説PDFを参考に座標の回転を行っていますが、座標の回転を行わなくてもACすることができると思います。）
「自分が衝突してしまうような飛行機を探す」というのは、結局「自分がじゃんけんで勝利できる相手を探す」と本質的に変わらず、あとは「どのようにバケツ分けをすればいいか」という問題と言えます。
もちろん、変数の範囲その他諸々の理由で、明確にバケツ分けができない問題も多くあると思いますが、今回は座標の範囲が限られており、直角にぶつかる場合をうまく工夫すればバケツ分けができる問題でした。
＜問題例＞
ABC152-D Handstand 2 / Diff : 1063（緑）
これは正直、バケツ分けをして数えるだけの、バケツ好きとしては非常に簡単な問題ですが、
結構最近のコンテストにも関わらず、緑Diff中～上位になっています。
なんとお買い得な問題でしょうか。
ARC048-B - AtCoderでじゃんけんを / Diff : 1281（水）
先程のじゃんけんの例を少し複雑にした問題です。
M-SOLUTIONSプロコンオープン2020-F - Air Safety / Diff : 2004（黄）
この回はE問題も難しく、F問題に置かれたせいでDiffが実際以上に上がっている面もあると思いますが、本質的にはバケツ（と座標を上手いこと工夫する）だけで解ける問題で黄色Diffというのはなかなか非自明です。
茶～緑はバケツを極めるべきという記事ですが、水～青くらいでもまだまだバケツ道を極めるには至っていないのかもしれません。
