モデル変換とアルゴリズム設計

本書の読み方

この章では、問題文の設定を、列挙する候補・保存する情報・集計する式へ置き換える練習をします。目標は、解説で知った手法を覚えるだけでなく、初めて見る問題でも「どこを変えれば計算を減らせるか」と、その変更が正しい理由を自分で説明できることです。

配列や集合の操作、ソート、基本的な探索と計算量の見積もりを知っていれば、章の最初から読めます。追加の知識が必要になったら、各単元の「前提と範囲」から該当する教材へ戻ってください。章の後半には複数の手法を組み合わせる発展項目もあります。一度に最後まで履修する必要はなく、前半の考え方を問題で使い、必要な項目へ進む読み方を勧めます。

章目次は学習を勧める順に並んでいます。隣り合う単元が必ず前提になるわけではなく、必要な前提は各ページに明示します。主配置の問題ではその単元の考え方を中心に学び、関連問題では別の主題との組合せを学べます。

対象色は、単元の中心となる考え方を道具として身につける時期の目安です。問題のDifficultyや、その単元の全問を解けるレートを表してはいません。章の導入と子単元では対象色を個別に定めています。色の境界はAtCoderのAlgorithmレーティング区分を使い(2026-11-04確認)、単元への割当ては本書の編集判断です。

全体の構成

本書はABCの過去問を通して典型知識を身につけ、ARC・AGC・CF Div. 1・UCUPなどの難関コンテストへ進むための教科書です。問題を読むときは、その問題の答えとともに、次に同じ考え方を使うための手がかりを持ち帰ってください。

本章で扱うモデル変換は、後の章でも使います。区間集約・データ構造では変換後に必要な情報を高速に管理し、動的計画法では同じ続きを扱える履歴を状態へまとめ、グラフでは操作や制約を頂点と辺で表します。本章では、そうした道具を選ぶ前の「何を計算すれば答えになるか」を定めます。

木構造と文字列では対象固有の構造を利用し、数論・組合せ、多項式、線形代数・幾何と凸最適化では数や式、図形の性質を計算へつなげます。どの章でも、問題文の表現から使える構造を取り出し、その構造で元の答えを求められる理由を確かめます。

概要

候補が多すぎる問題でも、多さの理由は一つではありません。同じものを異なる表現で調べていることもあれば、多数の候補で同じ加算を繰り返していることもあります。この違いを見つけると、試すべき変換が絞れます。

たとえば、いくつかの品物から合計金額が指定値になるように選ぶとします。まず「各品物を選ぶかどうか」を全部試せば、正しい基準解になります。そこから先は、何を利用できるかで方針が変わります。区別しなくてよい選び方があれば代表へまとめられます。求めたいものが全選択の費用の総和なら、各品物が何回使われるかを先に数えられるかもしれません。選び方を全部試すには多すぎても、前半と後半を別々に列挙して、合計の条件で照合できる場合があります。

モデル変換とは、答えに必要な条件を保ちながら、扱う対象や計算の順序を変えることです。 この章の入口では、次の四つを比べます。

素朴解法で調べたいこと変換の着眼点進む単元
候補を一つずつ試したい候補を決める少数の選択を見つけ、総数を数える有界全列挙
違う表現の候補を何度も調べている答えや今後の操作が同じものを、共通の表現へまとめる正規化
多数の対象で同じ要素を足している要素ごとに、使われる回数を数える寄与分解
全体の選び方は多いが、一部分なら列挙できる部分結果を作り、必要な条件だけで組み合わせる探索空間の分割

これは問題を一種類に分類するための表ではありません。一つの解法でも、部分候補を列挙し、同じ結果を頻度へまとめ、その頻度を使って寄与を足す、と複数の変換を組み合わせます。

考え方

まず、正しく全部試す方法を作る

値がそれぞれ 2,5,7,92,5,7,9 の四つの品物から、合計が14になる選び方を数えましょう。同じ品物は一度しか選べず、選ぶ順序は区別しないとします。

各品物について「選ぶ・選ばない」の二択があるので、候補は 24=162^4=16 通りです。たとえば最初の二つを選んだ途中状態は、選択が {2,5}\{2,5\}、合計が7です。次の7を選ぶと合計14になり、最後の9を選ばなければ一つの解が得られます。別の解は {5,9}\{5,9\} です。

品物が NN 個なら、各候補を長さ NN の0と1の列で表せます。0は選ばない、1は選ぶという意味です。全ての列を一度ずつ生成すれば、各部分集合に対応する列もただ一つなので、漏れも重複もありません。候補ごとに全品物を調べて合計を作る方法は、時間 O(N2N)O(N2^N) です。一候補ずつ処理すれば全候補の保存は不要で、入力と現在の選択を合わせた空間は O(N)O(N) です。

この時点で大切なのは、「全探索は遅い」で考察を止めず、何通りを生成し、一通りの何を調べるのかを分けて書けたことです。次は、候補数を減らすのか、一候補の評価を速くするのかを選べます。バックトラックでは、この二択を再帰で進め、選択時の変更を取り消して別の枝へ進む方法を学びます。

数値の上限が大きくても、生成に必要な選択が少なければ列挙は使えます。ABC234 E「Arithmetic Number」では、整数を順に調べる代わりに、桁数・先頭の数字・隣の桁との差から候補を生成します。「値の範囲」と「合法な候補の個数」を分けて見る練習になります。公式問題・公式解説で、この候補の作り方を確認できます。

まとめる前に、区別が必要かを確かめる

値の並びが (1,4,4)(1,4,4) と (4,4,1)(4,4,1) の二つの状態を考えます。品物の順序を自由に並べ替えられ、以後の条件も値と個数だけで決まるなら、この二つを別々に扱う必要はありません。どちらも昇順に並べた (1,4,4)(1,4,4) へ写せます。このような共通の表現を標準形と呼びます。

標準形が一致するなら、元の値の種類と個数も一致します。逆に、種類と個数が同じなら、どちらも同じ昇順の列になります。したがって、並べ替えだけが違う状態を過不足なくまとめられます。長さ NN の列を比較ソートして標準形を作る時間は O(Nlog⁡N)O(N\log N)、元の列も保持してコピーを作る場合の全空間は O(N)O(N) です。

ただし、先頭の値が条件に使われるなら、上の二状態は1と4で異なります。並び順を捨ててよい前提が崩れます。また、同じ値を持つ並びを何通りと数えるかにも注意が必要です。値が1,4,4である三つの品物からできる異なる並びは3通りですが、標準形は一つです。数え上げでは、まとめた個数を別に保持する必要があります。操作を続ける問題なら、現在の評価が同じだけでは足りず、以後の合法な操作や追加費用まで一致するかを確かめます。

この「必要な違いだけを残す」考え方の近くに、座標圧縮があります。たとえば値 (100,10000,100)(100,10000,100) は、異なる値の小さい順に番号を付ければ (0,1,0)(0,1,0) と表せます。等しいか・どちらが小さいかは保たれますが、元の差9900は番号の差1から復元できません。距離が必要なら、元の値も保存します。

ABC242 E「(∀x∀)」では、回文の先頭側を決めると残りが決まることに注目します。こちらは、同じものをまとめるというより、候補を一意に復元できる短い表現を選ぶ使い方です。辞書順の上限との比較も保つ必要があり、先頭側が上限と一致した場合には、復元した文字列全体で比較します。公式問題・公式解説とともに、何を残せば判定できるかを考えてください。

対象ごとの計算を、要素ごとの寄与へ変える

今度は、配列 (2,1,3)(2,1,3) の空でない連続区間について、それぞれの区間和を求め、さらに全区間分を足します。区間は位置で区別します。

長さ1の区間からは 2+1+3=62+1+3=6、長さ2からは (2+1)+(1+3)=7(2+1)+(1+3)=7、長さ3からは 2+1+3=62+1+3=6 が加わり、答えは19です。区間和を一回の計算で取得できても、全区間を列挙するだけで二重ループが残ります。

ここで、同じ配列要素が何度も足されていることに注目します。最初の2が入る区間は、位置1から始まる三つです。中央の1が入る区間は、左端を位置1・2から、右端を位置2・3から選ぶ四つです。最後の3が入る区間は三つあります。

固定する要素その要素を含む区間数答えへの寄与
位置1の21×3=31\times3=32×3=62\times3=6
位置2の12×2=42\times2=41×4=41\times4=4
位置3の33×1=33\times1=33×3=93\times3=9

寄与の合計も 6+4+9=196+4+9=19 です。区間を一つずつ見る代わりに、各要素の加算をまとめました。

長さ NN の配列を A1,…,ANA_1,\ldots,A_N とし、区間の左端・右端を l,rl,r とします。位置 ii を含む条件は 1≤l≤i≤r≤N1\leq l\leq i\leq r\leq N です。左端には ii 通り、右端には N−i+1N-i+1 通りあり、どの組も有効な区間になります。したがって、

∑l=1N∑r=lN∑i=lrAi=∑i=1NAi i(N−i+1)\sum_{l=1}^{N}\sum_{r=l}^{N}\sum_{i=l}^{r}A_i =\sum_{i=1}^{N}A_i\,i(N-i+1)

と変形できます。両辺とも「区間と、その中の一位置」の組ごとに同じ値を一回ずつ足しています。これが漏れ・重複を生まない理由です。

右辺を使う手順は、答えを0で初期化し、各位置で Ai i(N−i+1)A_i\,i(N-i+1) を加えるだけです。要素を保存する場合の全空間は O(N)O(N)、時間は O(N)O(N) です。NN が先に分かり、値を順番に読めるなら、保存するのは位置と累計などだけなので全空間を O(1)O(1) にできます。負の要素があっても加算の順序交換は成立し、N=1N=1 なら唯一の要素が一回加わります。整数型は、要素単体でなく回数を掛けた寄与と総和を格納できるものを選びます。

区間の最大値の総和を求める場合には、この式をそのまま使えません。たとえば区間 (2,1)(2,1) の最大値2は、要素を足した3と異なります。寄与分解では、最初に「一つの対象の答えを、何の和として表せるか」を定める必要があります。

ABC308 E「MEX」では、三つの添字を全部試す代わりに中央を固定し、左右を値ごとの個数へまとめます。どの添字を選んだかが違っても、値の組が同じなら同じ量が加わります。区間に含まれる回数を数えた上の例から、条件を満たす組の個数を数える寄与分解へ進む接続になります。公式問題・公式解説を参照してください。

分けた後の組合せを、全部試さずに済ませる

合計14になる品物の例へ戻ります。四つを前半 {2,5}\{2,5\} と後半 {7,9}\{7,9\} に分けると、それぞれの部分集合和は次のとおりです。何も選ばない場合の0も含めます。

部分部分集合和
前半0,2,5,70,2,5,7
後半0,7,9,160,7,9,16

前半で5を選んだなら、後半で探す和は 14−5=914-5=9 だけです。前半で7なら後半でも7を探します。これで、{5,9}\{5,9\} と {2,5,7}\{2,5,7\} の二つが見つかります。

各部分集合は「前半で選んだ集合」と「後半で選んだ集合」の組へ一意に分かれます。逆に、その二つを合わせれば元の品物の部分集合になります。目標を TT、前半の和を xx とすれば、後半の和が T−xT-x の組だけを足せばよく、各解を一度ずつ数えられます。

大きい側の品物数を m=⌈N/2⌉m=\lceil N/2\rceil とします。各半分で「選ぶ・選ばない」を再帰し、現在の和を引き継げば、一方の和の列挙は O(2m)O(2^m) 時間です。後半の和をソートし、前半の各和について T−xT-x の出現範囲を二分探索すれば、ソートと全検索を含む時間は O(m2m)O(m2^m)、入力・二つのリスト・再帰の作業領域を含む全空間は O(N+2m)O(N+2^m) です。前半を空、後半だけを選ぶ解も0を含めたことで数えられます。

単に二つに分けて全ての組を比較すると、2⌊N/2⌋×2⌈N/2⌉=2N2^{\lfloor N/2\rfloor}\times2^{\lceil N/2\rceil}=2^N 通りへ戻ってしまいます。分割が効くのは、片側の結果から、もう片側に必要な条件を絞って検索できるからです。 同じ和になる部分集合が複数ある場合も、数え上げでは頻度を残します。たとえば値2の品物が二つあれば、和2を作る選び方も二つあり、和の集合だけでは一つに潰れてしまいます。

これが半分全列挙の基本です。ABC271 F「XOR on Grid Path」では、格子上の経路を途中で分け、両端からの経路を照合します。合流するマスと、そこまでの排他的論理和(XOR)が接続条件になり、合流マスを二重に数えない調整も必要です。公式問題・公式解説から、単なる「半分」よりも接続条件の設計に注目してください。

一方、分割統治では、小さな部分問題を再帰的に解いて結果を合成します。たとえばマージソートは、左右を別々に整列し、両側の先頭を比較して小さい方を出すことで、全体を一度の走査で整列します。長さ NN に対して一段の合成が合計 O(N)O(N)、段数が O(log⁡N)O(\log N) なので時間は O(Nlog⁡N)O(N\log N) です。作業配列を再利用すれば、入力・作業配列・再帰の領域を合わせた空間は O(N)O(N) です。半分全列挙と比べ、何を部分問題の答えとし、合成の仕事量をどう抑えるかに注目します。

成立条件と計算量

変換を思いついたら、元の候補が変換先のどこへ行き、変換先の結果を元の答えとしてどう読めるかを確認します。正規化なら代表に必要な情報が残るか、寄与分解なら同じ加算を過不足なく数えるか、探索の分割なら合法な解が一意に接続されるか、という違いがあります。

要求が変われば、必要な情報も変わります。「存在するか」なら同じ和を一つにまとめられても、「何通りか」なら頻度が要ります。「最小値」なら各グループの最良候補だけで足りる場合でも、「具体的な選び方」まで出すなら元の候補へ戻る情報が要ります。何を求める問題なのかを、変換の前後で揃えてください。

計算量には、表現を作る前処理と、作った結果を全体で何回使うかを含めます。正規化にソートが必要ならその時間を数え、半分全列挙では候補生成だけでなく照合も数えます。寄与を一回で計算できても、対象が二乗個のままなら全体は線形になりません。この章の小例では、整数の加算・乗算・比較を一回 O(1)O(1) として評価しています。

この章を進む順序と、その理由

最初は有界全列挙とバックトラックで、候補を正しく生成する基準を作ります。続く正規化・座標圧縮・寄与分解では、候補の表現や集計する単位を変えます。その後に探索空間の分割へ進むと、元の候補との対応を保ったまま探索範囲を広げる、という共通点を捉えやすくなります。

次の単調探索・尺取り法・交換論では、調べない候補を作る根拠を学びます。判定が一方向に変わる、区間端が戻らない、選択を交換しても悪化しない、といった性質を証明してから候補を捨てます。bitごとの可否判定と構成解の復元では、その判断を積み重ねて具体的な答えへ戻します。

続く逆順処理・イベント走査では、計算する順序を変えて、必要な情報を更新しやすくします。償却解析と軽重分類からは、一回の処理が重くても全体の仕事量が小さいことを示す見方へ進みます。さらに、多数の探索の判定を共有する方法や、答えが変わり得る変更だけを調べる方法を扱います。

後半のゲーム、対話と情報量、乱択では、何を知れば判断できるかに加え、勝敗の保証・質問回数・誤り確率などを評価します。最後の順序変化やXORのマッチングは、複数の性質を組み合わせる発展です。下の章目次と各単元の前提を使い、今必要な知識へ進んでください。

問題を解いた後は、使った手法名とともに、素朴解法のどの仕事を減らし、何を根拠に減らせたかを言葉にしてください。同じ条件が別の設定に現れたとき、それが次の解法を選ぶ手がかりになります。

章の構成

項目は各章の読書順に並べています。親子関係は順序と独立しているため、階層を字下げで表さず、子Unitには「概念上の親」を示します。導入項目は関連手法の見取り図で、発展的なUnitは対象色を目安に後から戻って学べます。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。探索や集計を選ぶときに、答えに必要な条件と、計算を減らす根拠を言葉にするための入口です。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-chapter-modeling

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

問題文の操作を再利用可能な対象・不変量へ言い換え、探索・貪欲・分割手法を選ぶ共通の視点を最初に作る。

このUnitでは扱わないもの

  • なし

根拠