ARMERIA

放置していたけど更新再開、Rubyと競技プログラミングの話が中心になっていく予定です

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が属している列である「-, +」の符号パターンにおける最大値よりも小さいことが保証されます。別の符号パターンで得られる最大値よりも小さいのであれば、それが全ての符号パターンの中での最大値(最終的な計算結果)になることはありません。

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

  • 符号全パターン列挙で、ある符号パターン(列)についての最大値として「実現可能でない値  A 」が得られたとする。
  • その値に対応する組み合わせ(行)の中で、絶対値として正しい値  B が存在し、 A \lt B である。
  •  B に対応する符号パターン(列)で得られている最大値 C について、 B \le C である。
  • すなわち、 A \lt C が成り立つため、 A は全ての符号パターンの中での最大値(最終的な計算結果)にはなり得ない。

おわりに

私含め、本当にこれでいいのかモヤモヤが残っている人が多そうだったので書いてみました。長文読んでいただきありがとうございました。

一般化、同一視、言い換え、図示、色々な説明方法がありそうな気がしています。冒頭にも書きましたが、「こう考えたらしっくりきた!」というものがあれば、是非とも書いて公開していただけると嬉しいです。

脚注

*1:AtCoderの元々の問題でこれをやると、余裕でTLEします。

*2:0を除いた場合です。0が出てきた場合は「どちらに含めても良い」と解釈してください。

*3:一般には絶対値は0以上なので「以下」とするべきですが、イコールになる場合は、それも正しい絶対値を実現する符号パターンである(紫の丸が両方についている)はずです。絶対値として正しくない値は、正しい値よりも厳密に小さくなります。