競技プログラミングで解法を思いつくための典型的な考え方
競技プログラミングの問題を解くためには２つのステップがあります。
- 問題で要求されていることを言い換える
- 知っているアルゴリズムやデータ構造を組み合わせて解く
必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。
しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。
そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。
- 問われていることを、計算しやすい同値なことに置き換える方法
- アルゴリズムを思いつくための考え方
- 競技プログラミングで「典型的」と思われる考え方
※一部問題のネタバレを含むので注意
※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。
入力の大きさ(制約)から考える
まずは多くの人が気にするであろうことから。問題をみて解法を考える時は、制約の大きさに注意してみると解き方を思いつくヒントになる場合があります。
解き方を先に考えてから、「問題文の言い換え」を後から考えることになるので、本来の解き方と逆転します。しかし、方針を考える上で非常に重要な情報なので、制約はまずはじめに見るべきポイントでしょう。
Nが8前後
\(O(N!)\)、Nの階乗通りの探索をする場合が多いです。順列の全探索などがあります。
Nが10~20前後
\(O(2^N)\)、2のN乗通りのbit全探索をする場合が多いです。
Nが大きすぎなければ bitDP で \(O(N^2 2^N)\) の計算量となるかもしれません。包除原理を使用する問題もあります。
例：[AtCoder] キーエンスプログラミングコンテスト2020 D – Swap and Flip（解説）
全探索をするとN! 通りですが、Nが18までなので間に合いません。bitDPを使用するとうまくできます。
例：[AtCoder] ABC152 F – Tree and Constraints（解説）
辺の数が最大20までとなっています。包除原理を利用すれば解ける問題です。
例：競プロ典型90問 002 – Encyclopedia of Parentheses（★3）
N が 30~40前後
半分全列挙により、\(O(2^N)\) の計算量を \(O(N 2^{\frac{N}{2}})\) 程度に減らせることがあります。
- [AtCoder] AGC 026 C – String Coloring
半分全列挙のことが頭に浮かぶと自然に発想できるかもしれません。
N が 50 前後
\(O(N^4)\) 程度の計算量なら間に合います。
例：[AtCoder] ARC 060 C – 高橋君とカード
動的計画法で \(O(N^3 X)\) になります。工夫すると \(O(N^2 X)\) にもなるようです。
N が 300~500前後
\(O(N^3)\) 程度の計算量なら間に合います。区間DPなどがあるでしょう。
N が 1000 前後
\(O(N^2 \log N)\) 程度の計算量なら間に合います。
- \(O(N^4)\) を半分全列挙などで高速化する
- 1回あたり \(O(N \log N)\) で判定できる二分探索を用いる
例：JOI 2008 本選 5 – ダーツ
4重ループの全探索では間に合いませんが、3重ループと二分探索で高速化できることに気がつくでしょう。
これでもまだ間に合わないので、2つずつに分けて考えるとうまくいきます。2つのダーツを使うとどのような得点の仕方があるかを予め計算しておき、\(O(N^2)\) の1重ループと二分探索で最終的に計算ができます。このようなアルゴリズムを半分全列挙などと言います。
例：[AtCoder] ABC 034 D – 食塩水
平均値の最大化を行います。典型的な二分探索と言えるでしょう。
N が 3000 前後
\(O(N^2)\) 程度の計算量なら間に合います。
Nが\(10^5\)
一番良く見る制約かもしれません。ナイーブに解こうとすると\(O(N^2)\)だけ時間がかかってしまうが工夫により高速化ができる問題が多いです。しかし他にも様々なバリエーションがあります。以下はそのほんの数例です。
- \(O(NlogN)\)でソートをすると\(O(N^2)\)もかからずに解ける
- 1重ループと二分探索(or set or map)などの組み合わせで\(O(NlogN)\)で解ける
- 動的計画法を使って、N×(定数) サイズの配列を更新することで解ける
- 二分探索の判定を\(O(NlogN)\)で行い \(O(N (\log N)^2)\) でギリギリ間に合う
例：[AtCoder] ABC138 E – Strings of Impurity
ナイーブに計算すると\(O(n^2)\)ですが、二分探索により\(O(NlogN)\)で計算できるようになります。
例：[AtCoder] ABC023 D-射撃王（解説）
一見したところ、制約が大きく全探索や貪欲法が使えないため難しく見える問題です。うまく求める答えを言い換えると二分探索が使えます。
Nが64bitに収まらない
扱う数が \(10^{18}\) よりも非常に大きい場合は、桁ごとに考えるのが良いです。文字列で入力を得ることが多いでしょう。
桁DPなどを用いて計算することも多いです。
例：[AtCoder] ABC135 D – Digits Parade（解説）
i桁目までの数 j は、i-1桁目までの数に、\(j \cdot 10^i\)を足して表現できます。うまく考えると動的計画法が使えます。
例：[AtCoder] ABC154 E – Almost Everywhere Zero (解説)
Kが3通りしかないので場合分けでゴリ押しもできますが、桁DPで計算できる問題です。
小さめのmodが与えられる
比較的小さい modの時 (数千程度で \(10^9+7\) とかでない場合）は、剰余を考えると上手くいくことがあります。
問題文中に意味深な定数がある
問題文で何か定数が与えられ、それを利用する場合は、「なぜその値でなければならないか」を考えてみるとうまくいくことがあります。
例としては、
- その数の性質が良いことを利用する（素数, 約数に特殊な数がある, など）
- その数が小さいことを利用する（メモリの確保が容易でDPが使える, など）
例：[AtCoder] ABC135 D – Digits Parade（解説）
問題文中に 13 という定数が与えられています。なぜ 13 でなければならないのかを考えてみると、DP が使えそうなことに気が付きやすいです。
基本：全探索で解けるか考える
数学が得意な人は忘れがちなポイントかもしれません。最終的にはコンピュータのパワーを使った全探索が必要となる問題は多いです。 \(10^7\) 回程度のループなら余裕をもって間に合う処理でしょう。
簡単な問題なら、プログラムの文法をある程度知っていて、全探索が書けるだけで解けることは結構あります。
また、難しい問題でも「計算量を落として最後は全探索」というパターンは非常に多いので、全探索で解けるかどうか考えるのは基本となるでしょう。
競技プログラミングで代表的な全探索は以下のようなものがあります。（問題例もリンク先に記載）
実務でも競技プログラミングでも同様だと思いますが、入力サイズが小さいならば、高度なアルゴリズムを用いるよりも愚直な全探索などを用いる方が良いです。バグを生む危険が減りますし、早く書くことができます。
また、はじめに全探索の解法を考えるのは、別の解法を思いつくのにも有効です。愚直な方法の計算量を先に見積もっておくことで、DP などの高速化が思いつきやすくなります。
基本：一気に2つ以上のことをしようとしない
2つ以上のものを同時に考えると難しくなってしまうような場合というのは非常によくあります。
分解して考える（シンプルな場合を考える）
通常の問題設定が複雑だとしても、単純な状況ではどうなるかを考えてみると解法を思いつきやすいです。
足し算を分けたり、操作によって得られる結果を分けたりすることで、問題設定が非常にシンプルになる場合があります。複雑なものを分解して、後で組み合わせることを考えてみましょう。
また、2次元の問題などは、実は1次元に分解して独立して考えることができる問題なども結構あります。
もしくは操作によって、シンプルな問題に分解や変更できることもあります。
例えば、
- 入力が「整数の範囲」なら、「正の数だけの場合」「負の数だけの場合」「0だけの場合」
- 「1, 2, 3 しか登場しない」なら、「2 と 3 だけの場合」
などを考えてみるとシンプルになります。
例：AtCoder Regular Contest 107 C – Shuffle Permutation
行列の問題です。実はシャッフルするとき行と列はそれぞれ独立に考えることができます。
例：[AtCoder] ABC099 C – Strange Bank
\(6^i\)と\(9^i\)を分けて考えてみるとうまく解けます。\(6^i\)だけや\(9^i\)の硬貨だけのときは、使う硬貨の最小枚数を貪欲に決定できます。値段を2つに分割して、それぞれを\(6^i\)の硬貨で支払う場合と、\(9^i\)の硬貨で支払う場合として考えてみましょう。
ちなみに動的計画法でも解ける問題でした。
例：[AtCoder] ARC 086 D – Non-decreasing
正の数と負の数両方が含まれる可能性があるので、どちらか一方だけしか無い時を考えてみるとうまくいきます。
固定して考える
変数がいくつかある時は、同時に考えるのではなく、あるものを固定して考えるとうまくいく場合があります。
２変数あって全探索すると計算量が \(O(N^2)\) となる場合は、１つを固定して考えると、もう片方を工夫によって高速に求められ、計算量が落ちる場合があります。
また、3つのものを考える時は、真ん中の物を固定すると上手くいくことがあります。
同様に、4つのものは3つの仕切りがあると考えることもできるので、2つずつに分けて捉えるとうまくいくかもしれません。
例：[AtCoder] ABC077 C – Snuke Festival
A,B,Cの3つの組み合わせが何通りか数える必要があります。同時に考えるのではなく、A,B,Cのどれかを固定して考えると上手くいく問題です。真ん中のBを固定したほうが計算しやすいですが、AやCを固定する場合でも累積和を用いればうまく計算することができます。
例：[AtCoder] ARC 100 D – Equal Cut
4つに分けるということは、3つの仕切りがあるということです。中心を固定してみると見やすくなります。
例：[AtCoder] ABC104 D – We Love ABC
B を固定して、A,B,Cと並ぶのは何通りあるのかを考えると解くことができます。
動的計画法を用いる方法もあります。
例：AtCoder Regular Contest 107 B – Quadruple
2つをまとめて固定しましょう。
対称性を活かす
対称性をうまく利用することで様々な問題を都合良く解くことができる場合があります。
対称となる部分と等しいとき：全体を求めて2で割る
求めたいものと、それと対になる部分（対称な部分）の値が等しいとき、その2つの和の方が計算しやすい場合があります。先に全体を求めてから、後で2を割ることを考えてみましょう。
例：AtCoder Regular Contest 106 D – Powers
対称式についての問題です。全体を求めてから余分なところを引いて2で割ると答えがでます。2次元のマス上に何を足したいかを並べてみると分かりやすいでしょう。
x座標とy座標の対称性から1次元の問題に帰着
正方形が登場するような問題は、x座標とy座標に対称性があるので、それぞれ独立した1次元の問題として考えることができる場合があります。
例：HHKB プログラミングコンテスト 2020 D – Squares
格子点上での、3つの正方形について考える問題です。数え上げ問題ですが、x,y座標の対称性に注目するとうまく解けます。
操作をする問題
不変量に注目する
ある操作を「K回以内行う」とか「好きなだけ行う」とか指定されている問題は、操作ごとに不変なものを考えてみると特徴を捉えられる場合があります。
偶奇性に注目する
操作をしても偶奇性が変化しない場合や、逆に変化する場合などがあります。このような部分に注目するとどのようにするべきか分かりやすくなる場合があります。
操作の順番を入れ替えてもよいか
操作の順番が決められている問題の時、結局どの順番で操作を行ったとしても結果が変わらない場合があります。
このような場合は、自分にとって都合の良い順番で操作を行うと良いです。
操作を逆順に考えるとどうか
問題文通りに操作をするのでは考えにくい場合、逆順に操作をすることを考えると分かりやすくなる場合があります。
特に操作の結果が最初から分かっている場合は逆順に考えたほうが見やすくなることが良くあります。
操作をして元に戻せるか
操作をして変換したものを、また操作することによって、元に戻すことが可能かどうかを見ると分かりやすくなる場合があります。
操作をすると同じものになるもの同士をまとめて、同値類（同じグループ）として考えられれば分かりやすくなるでしょう。
問題例
例：[AtCoder] ABC136 E – Max GCD（解説）
何回操作しても、合計値は変化しません。これに注目すると答えの候補は合計値の約数であることがわかります。
例：[AtCoder] ABC127 D – Integer Cards
操作の順番が定められていますが、どの順番で操作を行っても答えは変わりません。小さいカードから、大きい数字で書き換えるような順番で操作すれば良いです。
例：[AtCoder] ABC093 C – Same Integers
偶奇性に注目すると非常に見やすくなります。1つを2増やしても偶奇は変化しません。逆に2つを1ずつ増やすと、それらの偶奇は変化します。また、全体の和の偶奇はどのような操作をしても変化しません。
はじめに「+1の操作」を多くても1回行うことで、3つの偶奇性を合わせることができます。あとは「+2の操作」で全ての数を揃えるだけです。
例：[AtCoder] AGC C – Numbers on a Circle
操作結果が分かっているので、逆順に考えてみるとどのように操作したら良いかが分かります。
例：[AtCoder] ARC 071 E – TrBBnsformBBtion
操作で変換したものは、（完全に消去しない限り）元に戻すことが可能です。同値類として考えてみると性質が見えてきます。
数え上げ問題
「~が何通りか求めよ」系の問題です。単純に全探索をしても間に合わないことがほとんどなので、何らかの工夫をする必要があります。
動的計画法で状態をまとめ、全探索を高速化する
全探索で探索する状態をいくつかにまとめて同一視することで、動的計画法を使えることがあります。DPを「全探索の高速化」とみなすことになり、どのような状態をまとめられるかを見抜く必要があります。
平均が K となる組み合わせ
いくつかの数列があり、平均が K となる組み合わせを求めるときは、
- 「合計値が K × 個数」となる組み合わせ
- 「元の値をすべて-K した数列で、合計値が 0」となる組み合わせ
というように変更すると考えやすくなることがあります。
例：[AtCoder] ARC 060 C – 高橋君とカード（既出）
区間問題
典型と言っても良い累積和系の問題。様々なバリエーションがあります。
累積情報か、セグメントツリーを利用して解ける場合があります。
左右両方から累積情報を前処理しておく
左右両方から累積和を前処理して保存しておくと、後の計算を効率よくできる場合があります。
一つだけ除いたものを考える場合なども有効です。
例：[AtCoder] ABC098 C – Attention
ある地点の左側に’W’がどれだけあり、右側に’E’がどれだけあるかを計算するのに単純に計算するとO(N)だけかかります。
これを累積和を用いると、前処理にO(N)かければ、１回あたりのクエリにO(1)で計算できるようになります。
例：[AtCoder] ABC125 C – GCD on Blackboard
一つだけ除いた最大公約数を考える問題です。左右からの累積最大公約数を保持しておくと除いたものを考えることができます。セグメントツリーでも解くことができます。
区間に足す時
imos法や、区間和対応のBITなどで解ける場合があります。
区間を削除・圧縮・合成する時
区間DPを使うことがあります。
等差数列の加算は差をみる
公差 d の等差数列を区間に加算する場合は、加算した値に差がどれだけ変化するかに注目してみると、そのほとんどが公差 d だけ変化するのに注目すると分かりやすくなる場合があります。
例：[AtCoder] AGC 010 B – Boxes
1からNまでの公差1の等差数列を区間に足す操作をします。これも差に注目してみると、加算する際は差はほとんどが 1増加して、1つだけ(N-1)減ります。
区間を反転させる問題
ライツアウト系の問題です。以下のことに注意すると分かりやすくなるでしょう。
- 同じ操作を2回やると元に戻る
- 操作の順番を入れ替えても同じ
- [l1, r1]と[l2, r2] の反転は、[l1, r2]と[l2,r1] の反転と同じ（区間の左端はどのように反転させても左端、右端はどのように反転させても右端）
- 反転区間の端点に注目するとgreedyに決まることがある
例：第一回日本最強プログラマー学生選手権-予選- C – Cell Inversion
区間反転の様々な典型が詰まっています。隣り合う2つの頂点に注目すると、反転区間のどちらの端点になるかわかります。
ゲーム
基本的には最善戦略を探すことになります。
不偏ゲームはGrundy数を考える
不偏ゲームの場合は、Grundy数で先手後手のどちらが必勝かを判定することができます。
後退解析をする（最後から考える）
ゲームが終了した時からさかのぼって考えると最適な行動が分かることがあります。
同じ手段を選び続けるのが最善
いくつか手段があるときは、同じ手段を取り続けるのが最善の時があります。
一方が最大化・他方が最小化
場合分けなどで何らかの最善戦略を探す
まず基本となるのは最善となる戦略を先手・後手ともに見つけることです。
後手は「先手がどう動くか」が分からないと方針が立たないことが多いので、先手の行動を場合分けしてみると分かりやすいです。
最大化側はx以上・最小化側はx以下を達成できるか考える
最善戦略を探す時や、その戦略かを確かめる時は、以下を考えてみましょう。
- 最大化したい側は、最適に行動すれば少なくとも x 以上になる。
- 最小化したい側は、最適に行動すれば多くても x 以下になる。
すると、両方が最適に行動した際に x になることが分かります。
これほど分かりやすく無くても、「仮に先手がこのように行動すると、後手は必ず x 以下にできる」というように場合分けした後で使えることもあります。
例：[AtCoder] ARC 094 E – Tozan and Gezan
例：[AtCoder] ABC 076 D – ABS
先手の行動を場合分けをして、得点の上限や下限が抑えられるかを考えるとうまくいきます。
制約を満たすものを数えるとき
直接考えるのが難しい時は余事象を考える
Aとなる数を数えるときは、¬Aとなる数を考えてみるとうまく数えることができる場合があります。
特に「〜が1つ以上」のような条件のときは、その否定を考えると「〜が0」になるので問題がかなりシンプルになります。大学受験の数学でも似たような考え方をすることが多いですね。
あとは全体の数から余事象の数を引いてあげれば、求めたいものが得られます。
例: [AtCoder] ABC152 F – Tree and Constraints（解説）
「黒く塗られた辺が1つ以上存在する」の否定を考えると「黒く塗られた辺が存在しない」となるので問題がかなりシンプルになります。
構築系問題
条件を満たす何かを作る問題です。
「構築できない場合」が存在しないことがある
「○回以内で構築できない場合は -1 を出力せよ」という問題も、実は必ず ○回以内で構築できることがあります。
上限ギリギリでの構築法が全てに当てはまることがある
「○回以内で構築できない場合は -1 を出力せよ」や「N個以内で構築せよ」とあれば、○回ギリギリやN個ギリギリの構築法が全ての場合に適用できることがあります。
「2N 回以内に終了」ならN回以内に特殊な状況にもっていく
「2N 以内に操作を終了せよ」などと制約にあれば、全要素に対して 1 回ずつ合計 N 回操作を施して、「N回以内に簡単に解ける特殊な状況」に持っていくと解けることがあります。
さきほどの「上限ギリギリでの構築法が全てに当てはまる」というのにも当てはまります。「2N 回」という上限ギリギリでの構築法を考えることになります。
問題例
例：[AtCoder] ABC 067 D – Decrease (Contestant ver.)
「50個以内」とありますが、50個の数列ですべての場合を構築することができます。何種類かやり方があるようです。
例：[AtCoder] ARC 086 D – Non-decreasing（既出）
「2N 回以内に終了」とあるので、N回以内に特殊な状況に持っていきましょう。
K番目の数を求める
K 番目の数を求めさせる問題というのは結構あります。
要素の値が小さい時
BIT などで K 番目の数を求めることができます。
二分探索で求める
以下の言い換えによって、K番目の数 X を二分探索によって高速に求めることができます。
「小さい方からK番目の数が X」
⇔「X-1 以下の数は K個未満で、X以下の数は K 個以上」
⇔「X以下の数が K 個以上 となる最小のX」
Xの値の二分探索は、O(log(Xのサイズ))回だけ「X以下の数が K 個以上か」という判定をすることになります。つまり、「条件 C(X)：X以下の数が K 個以上」という条件を満たす最小の X を求めれば良いです。
「X以下の数が K 個以上か」という判定自体にも二分探索を用いることもあります。
中央値（N/2+1番目）を求める
中央値を求めるような問題は以下が同値であることを利用することがあります。
- 中央値が X 以下である
- X 以下の数が N/2+1 個以上
つまり、先程の二分探索が上手く使えます。
「小さい方からN/2+1番目の数が X」
⇔「X-1 以下の数は N/2+1個未満で、X以下の数は N/2+1個以上」
⇔「X以下の数が N/2+1個以上 となる最小のX」
問題例
例：[AtCoder] ARC037 億マス計算
K番目の数 X を二分探索によって求めることができます。
例：[AtCoder] ABC155 D – Pairs (400点) (解説)
上の問題の上位互換です。Xが正の時・負の時・0の時で処理を分けなくてはならないので実装が重いです。
xor系の問題
xor を「繰り上がりのない足し算」と見る
xor は「繰り上がりのない足し算」とも言えます。あるビットについて、同じ数字 (「0と0」 or 「1と1」) だったら0に、違う数字 (「0と1」or 「1と0」) だったら 1 にします。
逆に、繰り上がり部分というのは \(2(a\)&\(b)\) で表現することができ、ここから以下の式が成り立つことが分かります。
- \( a+b=a \oplus b + 2(a\)&\(b)\)
xorを桁ごとに考える
xor が「繰り上がりのない足し算」ということは、ある桁がどんな数であっても、xorをして他の桁に影響を与えることがありません。
故に、xor を何度も使用する問題には「桁ごとにxorを計算して最後にまとめる」という手法が使えることがあります。特定の桁において、xorをする数それぞれで1が出現する回数が偶数なら最終的な答えは0、奇数なら1になります。
同じ数をxorするともとに戻る
同じ数をxorすると元に戻ります。つまり、
- \(a \oplus a = 0\)
- \(a \oplus a \oplus b = b\)
という性質が使えることがあります。
問題例
例：[AtCoder] ARC021 B – Your Numbers are XORed…
「同じものを xor すると元に戻る」という性質を知っていれば、答えを思いつきやすいです。B を全てを xor すると、A をそれぞれ 2 回ずつ xor することになります。条件を満たす A が存在するならこの値は 0 になるはずです。
例：[AtCoder] ABC129 E – Sum Equals Xor
xor は「繰り上がりのない足し算」ということを知っていれば、足し算とxorが一致するのは 1 が立つビットが被らない時であると分かります。あとは桁数が多いので「桁ごとに考える」と上手くいきます。
例：[AtCoder] ABC098 D – Xor Sum 2
xor は「繰り上がりのない足し算」なので、繰り上がりが生じなければ普通の足し算と同じと言えます。それぞれの l に対して、繰り上がりが生じない最大の r を高速に求めることができれば答えがわかります。
例：[AtCoder] ABC147 D – Xor Sum 4
桁ごとに考えると、\(A_i xor A_j\)が1になるのは\(A_i \neq A_j\)のときです。このような組が何回あるかと、桁ごとの足し算は同値になります。
例：[AtCoder] ABC121 D – XOR World
AからBまでの数について、桁ごとに出現する1の数を数えることで解けます。もしくは、同じものをxorすると元に戻ることから、\(F(A,B) = F(0,A − 1)~ xor~ F(0,B)\) であることが使えます。考察により、実は桁ごとに計算するよりも更に早く、定数時間で解くことができます。
例：Codeforces Round #628 (Div. 2) D. Ehab the Xorcist
xor系の構築問題です。「繰り上がりの無い足し算」や「同じものを足すと元に戻る」などの性質が上手く使えると見えてきます。
マンハッタン距離
45度回転させる
座標を45度回転させることにより、あるマンハッタン距離dで移動可能な範囲は正方形の形になります。
元の座標が (x, y) であれば、新しい座標で (X,Y)=(x+y, x-y) などと変換してみます。すると、[X-d, X+d] かつ [Y-d, Y+d] の範囲が元々の座標で移動可能だった範囲です。
例：[AtCoder] ABC018 C – 菱型カウント
累積和の特殊系っぽく解くこともできますが、45度回転させた後に、通常の累積和や二次元BITを用いることでも解けます。
差の最小化は中央値を用いる
\(\displaystyle\sum_{i = 1}^{n} |A_i – x|\) を最小化するような x の値を求める際は、中央値を用いると最小化できることが知られています。
例：[AtCoder] ABC102 C – Linear Approximation
差の最小化の問題です。1次元のマンハッタン距離を考えると差の最小化に中央値を用いることができます。
グラフ系
代表的なグラフで実験してみる
以下の代表的なグラフを考えた時にどのようになるかを考えてみると様子をつかめる場合がある。
- パスグラフ（直線上に繋げたグラフ）
- スターグラフ（一つの頂点から、他のすべての頂点に1つずつ辺が出ているグラフ）
- 完全グラフ（任意の２頂点間に辺があるグラフ）
- 完全二部グラフ（二部グラフのうち、可能な限り辺をつないだもの）
- パスグラフに少し辺を足したグラフ
例：[AtCoder] ABC131 E – Friendships
完全グラフやスターグラフに注目してみると上手くいきます
木は二部グラフであることを利用する
木は二部グラフであることを利用して、2つにグループ分けをすると分かりやすくなる場合があります。偶数回の移動で同じグループに戻ってきますし、奇数回の移動で違うグループへ移動します。
例：[AtCoder] 日立製作所 社会システム事業部 プログラミングコンテスト2020 C – ThREE
距離が3の頂点は、二部グラフで考えた時のもう一方のグループに存在していることを表します。
木の直径を考えてみる
木の直径について考えると性質が見えることがあります。（また、直径のみを考えればパスグラフとも言えます。）
例：[AtCoder] AGC 033 C – Removing Coins
木の直径について考えてみると良くある不偏ゲームに帰着できます。
条件を満たす最大値or最小値を求める
条件を満たすように最大化/最小化は二分探索
ある条件 C(x) を満たすような x を最大化したり、最小化する場合は二分探索が使えることがあります。特に多いのは、
- 平均の最大化・最小化
- 最大値の最大化
- 最小値の最大化
などがありますが、これ以外にもあります。
選択肢が少ない方から見て貪欲
候補を選んでいくような問題で、制約の簡単な方から見ると候補がたくさんあり、制約の厳しい方から見ると候補が少ないような時に使える考え方です。
例えば、「時間が経つにつれて取れる選択肢が少なくなる」とか「前半に選択したものが後半に影響して選択肢が少なくなる」などで使える考え方です。
このような問題では、候補が少ない方から考えると見通しが良くなることがあります。
問題例
例：[AtCoder] ABC137 D – Summer Vacation
初日に選べる仕事の選択肢は多いのに比べて、最終日を考えると制約が厳しくなっているので選択肢が少なくなります。最終日から考えて、使える選択肢の中から報酬が最大のものを取れば最適です。
例：[AtCoder] ABC134 D – Preparing Boxes
ボールを入れるか入れないかを箱ごとに考えます。\(a_1\)は他の箱のボールの入れ方が関係してきますが、\(a_N\)は自身に入るボールの入れ方のみを定めます。これも後ろのほうが制約が厳しく候補が少ないと言えます。この時は、前から見るとボールの入れ方は定まりませんが、後ろから見ると1通りに定まります。
例：DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 本選 B – DDPC特別ビュッフェⅡ
条件を満たすように最大化する問題なので、二分探索を利用することができます。
また、時間が立つにつれて段々と取れる料理が少なくなっていきます。こういう時は、後半から貪欲に取っていくと良いです。
偶奇性に注目する
abs(x-y)・差の計算
abs(x-y) などの計算では、偶奇性（パリティ）などに注目すると上手くいくことがあります。
- abs(x-y) が奇数：x と y の偶奇が異なる
- abs(x-y) が偶数：x と y の偶奇が同じ
2を法としたときに以下の式が成立することを頭に入れておくと良いでしょう。
- \(|x-y| \equiv x \oplus y \equiv x + y ~(mod ~ 2)\)
xor で偶奇を見る
先程の abs(x-y) でも出てきた xor を使って偶奇を見ると捉えやすくなります。
奇数を偶奇性でみる
3 などの奇数が出た場合は、偶奇性に注目すると良いことがあります。
木においては、木を二部グラフとしてみると、偶奇性が分かりやすくなります。
例：[AtCoder] AGC 043 123 Triangle（解説）
偶奇性の典型がわかっていれば、いいところまで考察できるはずです。
最大マッチング
フローを利用した二部グラフの最大マッチング
フローを利用して二部グラフの最大マッチングを求めるのは有名なアルゴリズムなので、まずはそれを疑ってみると良いでしょう。
貪欲にマッチングできることがある
二部グラフではなかったり、エッジの数が膨大になりそうな時は、貪欲にマッチングが取れることがあります。その場合は、「選択肢が少ない方から見て貪欲」に取るのが最適なことが多いです。
例：[AtCoder] AGC 029 B – Powers of two
貪欲なマッチングができます。
その他
積の総和は分配法則で和の積にする
積の総和を求めさせるような問題は、分配法則を考えて、和の積の形に変形できれば計算量が落とせることがあります。
例えば、以下のような変形ができます。
$$ \sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc = (1+2+…+A)(1+2+…+B)(1+2+…+C)$$
例：AtCoder Regular Contest 107 A – Simple Math
シグマの外に余計な文字を出すと簡単に計算できてしまうのですが、積の総和を、和の積の形に変更してみることでも解くことができます。（上の例の変換そのままです）
二次元座標を二部グラフで考えてみる
二次元の平面上にあるいくつかの点を、以下のような二部グラフで表現してみるとうまくいくことがあります。
- 二部グラフの左側：x座標
- 二部グラフの右側：y座標
- 二部グラフの辺 (x,y)：点 (x,y) に対応
例：[AtCoder] ABC 131 F – Must Be Rectangular!
二次元座標の点を二部グラフで考えると、各連結成分ごとに完全二部グラフにすれば良いことが分かります。
順序がある場合は有向グラフで考えてみる
順序関係が存在するような問題設定の場合は、有向グラフの問題に帰着できる場合があります。
特に半順序集合の場合は、閉路のない有向グラフ(DAG)によって表現することができ、これはトポロジカルソートすることができます。（半順序というのが分からない場合は「閉路のない有向グラフで表現できるもの」と思っておけばとりあえずは大丈夫です。正確には集合論を勉強してみると分かります。）
例：[AtCoder] ABC139 E – League（解説）
試合には順序関係が存在し、全ての試合を行うことができる場合、試合は半順序集合になっておりDAGで表現できます。
逆に全ての試合を行うことができない場合は、有向グラフに閉路が存在することと同値です。
凸関数の極値は三分探索
凸関数の極値を求める問題では、三分探索や黄金分割法などを用いて求めることができます。
例：[AtCoder] ARC054 B – ムーアの法則
x に対して、計算が終わるまでの時間を f(x) とすると、この関数は凸関数になります。f(x)の最小値を求めたいので、三分探索を用いることができます。
微分したものを考えると、f(x)が最小となる x の右側では正、左側では負になることが分かるので、実は二分探索でも求めることができます。
数列の番号に対する単調増加な性質はしゃくとり法
l を固定したときに、数列の l 番目から r 番目が条件を満たすような最大の r を f(l) と表せる時を考えます。この f が単調増加のときにはしゃくとり法を用いることができます。
数列の長さを N とすると、それぞれの l に対して条件を満たす最大の r を求める時、しゃくとり法を用いることで O(N) で計算することができます。
例：[AtCoder] ABC098 D – Xor Sum 2
l を固定したとき、条件を満たす最大の r を f(l) とすると、この f は単調増加です。しゃくとり法で高速に計算ができます。
等比数列や○進数は割った余りで考える
等比数列や○進数のような問題は、割った余りに注目してみると良いです。
例：[AtCoder] ABC105 C – Base -2 Number
-2進数表現という見慣れない表現ですが、公比が-2の等比数列で表現するとも言えます。実は余りに注目すると、小さい桁から決定していくことができます。
括弧列は山の上り下り(折れ線)として考える
'(' や ')’ が並んだ文字列を考える問題では、括弧がうまく閉じるかどうかなどを考えることがあります。このような問題では、
- '(' の時は上に 1 上る
- ')’ の時は下に 1 下る
というようにすると、考察しやすくなります。
この時、括弧がうまく閉じる条件は
- はじめと終わりは0
- 途中で0未満になることはない
と言い換えることができます。
例：[AtCoder] ABC167 F – Bracket Sequencing
上り下りすると考えると、並び替えて括弧がうまく閉じる状況を考えやすくなります。上る部分を左側、下る部分を右側に分けて考えると、ソートして貪欲法で解くことが可能です。右側の下る部分は、左側の上る部分の反転と同じだと考えると処理しやすいでしょう。