ABC100-D 8通り場合分けの「正当性」について説明を試みる

タイトルの通りです。

D - Patisserie ABC

おそらく色々な説明があると思いますが、私なりにしっくりきた考え方を書きます。是非、他の人の考え方も読んでみたいです。

一般の問題ではなく問題例を1つ考えるだけなので、厳密な証明の形式にはなっていませんが、似たような思考で一般的な証明ができる…はずです。

推奨理解度

本記事を読んでいただくにあたっての、一応の推奨理解レベルです。必須ではないですが、特にまだACしていない方は是非そちらからやってみてください！

この問題を「8通り場合分け」の貪欲 or DPでACしている
「8通り場合分け」を行った際に、そのうちのどれかで最適値（出力すべき値）が得られることを理解している
「8通り場合分け」において、「実際には実現しない値」が出てくることを理解している（or そんな気がしている）

そのうえで、「実際には実現しない値が出てきちゃうけど、それでいいの？」という疑問を解消しよう、という試みです。

今回の問題設定について

問題の本質は変えずに、~~書く量を減らしてサボるため~~問題を単純にするため、以下のように問題を変更します。

選ばれるものの総数 $N = 3$ , 選ぶ数 $M = 2$
評価値は2種類（ $x_{i}, y_{i}$ だけ）

評価値が2種類なので、求めたい値（以降、目標値と呼びます）は以下になります。

$\max_{S} (|\sum_{i \in S} x_{i}| + |\sum_{i \in S} y_{i}|)$

ここで $S$ は「 $N$ 個のものから $M$ 個選ぶ選び方」の集合です。記載煩雑になるので、以降は省略します。

問題例

前節で定義した問題設定の条件を満たす、以下の問題を考えます。

$i$	$x_{i}$	$y_{i}$
0	1	-1
1	-2	2
2	1	-3

この問題を、

組み合わせ全列挙
符号パターン全列挙

の2通りで解いてみます。

組み合わせ全列挙で解く

こちらの解き方は、「厳密な最適解」として納得しやすいと思います*1。

与えられた3個の要素から2個選ぶ、全ての選び方を考えます。これは ${}_{3}C_{2} = 3$ 通りです。

選び方	$\sum x_{i}$	$\sum y_{i}$	$\|\sum x_{i}\| + \|\sum y_{i}\|$
(0, 1)	-1	1	2
(0, 2)	2	-4	6
(1, 2)	-1	-1	2

それぞれの選び方の目標値は一番右に書いています。この中で一番大きいものを見ればよいので、これで問題の答えは6です。

ここで終わらずに、もう少し考えてみましょう。それぞれの選び方について、 $\sum x_{i}$ と $\sum y_{i}$ の符号を見てみます。

選び方	$\sum x_{i}$ の符号	$\sum y_{i}$ の符号	$\|\sum x_{i}\| + \|\sum y_{i}\|$
(0, 1)	-	+	2
(0, 2)	+	-	6
(1, 2)	-	-	2

登場する符号の組み合わせは「-, +」「+, -」「-, -」、全部で3パターンです。

ただし、2つの値に対する符号のパターンは実際には4パターンですよね*2。上表には出現していないパターンがもう1つあります。それは、「+, +」のパターンです。

このことを意識しつつ…もう1つの解き方を考えてみます。

符号パターン全列挙で解く

元々のD問題の想定解法と同じように解くことを考えます。具体的には、4通りの符号パターンについて場合分けし、大きい方から貪欲に選んでいきます。

まずは、それぞれの要素に対して4通りの符号パターンに対応する値を考えます。

$i$	$x_{i}$	$y_{i}$	$+ x_{i} + y_{i}$	$+ x_{i} - y_{i}$	$- x_{i} + y_{i}$	$- x_{i} - y_{i}$
0	1	-1	0	2	-2	0
1	-2	2	0	-4	4	0
2	1	-3	-2	4	-4	2

各符号パターンについて、大きい方から要素を2つ取ります。合計値が最大になる選び方とその合計値は以下の通りです。

符号パターン	合計最大になる選び方	合計
$+ x_{i} + y_{i}$	(0, 1)	0
$+ x_{i} - y_{i}$	(0, 2)	6
$- x_{i} + y_{i}$	(0, 1)	2
$- x_{i} - y_{i}$	(0, 2) or (1, 2)	2

この最大値を取って、問題の答えは6です。

比較

これらの結果を比較してみましょう。もちろん答えは6で一致していますが、選び方と符号パターンの関係に着目してみます。

まずは「全部の選び方を考えたとき、それぞれの選び方で符号パターンがどのようになるか？」です。

選び方	$\sum x_{i}$ の符号	$\sum y_{i}$ の符号	$\|\sum x_{i}\| + \|\sum y_{i}\|$
(0, 1)	-	+	2
(0, 2)	+	-	6
(1, 2)	-	-	2

次に「全部の符号パターンを考えたとき、それぞれの符号パターンで最適な選び方がどのようになるか？」です。

符号パターン	合計最大になる選び方	合計
$+ x_{i} + y_{i}$	(0, 1)	0
$+ x_{i} - y_{i}$	(0, 2)	6
$- x_{i} + y_{i}$	(0, 1)	2
$- x_{i} - y_{i}$	(0, 2) or (1, 2)	2

見比べてみると、符号パターン「+, +」で得られる「0」という値については、これを実現する選び方が存在しません。これがつまり、冒頭で書いた「実際には実現しない値が出てくる」という現象です。

もしこの「実際には実現しない値」が全符号パターン中で最も大きい値になってしまう場合があれば、符号パターン全列挙の解き方には正当性がない、ということになります。

今回の「0」という値は他のパターンの値よりも小さいので、最大値を求めるにあたっては実害を及ぼしません。とはいえ気になるのは、これが偶然なのか？必然なのか？ですよね。もう少しだけ考えてみます。

表にしてみる

この2つの解き方の差を、このようにイメージしてみましょう。

f:id:betrue12:20180617120112p:plain

全ての選び方、全ての符号パターンに対する値を列挙しました。組み合わせ全列挙はこれを「行ごと」に、符号パターン全列挙はこれを「列ごと」に解いていく方法と言えます。

紫の丸が付いているものは、その選び方の絶対値として正しいもの、つまり「実現可能な値」です。

それぞれの行を見ると、紫の丸がついた値は、4つの値の中で最も大きいことがわかります。これは絶対値の性質を考えると確かにそうで、紫の丸がついていない値は「絶対値によって0以上になっているものを、わざわざ符号反転させたもの」ですので、必ず小さくなります*3。

さきほど登場した「実際には実現しない値」は、左上にある0です。この値は、その選び方の「絶対値として正しい値」である2よりも小さい。すなわち、この2が属している列である「-, +」の符号パターンにおける最大値よりも小さいことが保証されます。別の符号パターンで得られる最大値よりも小さいのであれば、それが全ての符号パターンの中での最大値（最終的な計算結果）になることはありません。

同じことを言っていますが、少し一般性を持たせて書くと以下のようになります。