分割統治法の薦め

分割統治法という考え方があります。複雑な問題は、より簡単な小さな問題に分割して、順番に解いていく、という思考法です。難問に取り組む際の基本中の基本の思考法です。Scala では分割統治法が徹底されていて、ちょっとでも構造が違えばクラスを分けることが推奨されています。

さて、この、分割統治法ですが、注意事項があります。

たとえ重複していても、一度分割したものはまとめるな!

これ、僕、何度となくやってしまって、失敗しています。難しいから分けたものを、重複しているからといってもマージはしないほうがいいです。マージすることにより、状態数が減り、より簡単になる、というケースは統計的には少ないです。

僕が知る範囲において、結城浩さんの最高傑作だと思われる、『C言語プログラミングのエッセンス』(isbn:4890524312)の、僕が中学生のときに買った旧版の p.99 にも似たような話が書いていますよると、

ここは大切な点ですので、もう一度。
ふと思いついたから、何だかよくわからないけど if 文を使ってみよう、
というやり方はよくありません。
そうではなく「私はいま問題を分けて考えているのだ」と意識してみてください。
if 文は、大きな問題を小さな問題に分けているのです。
そのことをはっきりと意識していただきたいと思います
(Essence 3-1「問題の分割」参照)。

IOI世界大会2007年度の第1日目「帆」を解くにあたっても、同じミスをやってしまいました。擬似コードは以下のとおりです。ここにたどり着くまでも、面白い話があるのですが、まぁ、いつかの機会にでも。

マストの高さでソート
低いマストから
  NES : 高さ(>= 1) -> 累積帆数。これは管理しない。概念上のみ。
  step : 高さ -> ひとつ上の高さからの累積帆数の増分 = NES(h) - NES(h + 1)
  stepHeight: step(h) != 0 となる h の TreeSet
    step を更新するときに、前後を見て、add, remove を判断する
    zoneMin = 同じNESが連続する下限の高さ
    zoneMax = 同じNESが連続する上限の高さ
  h = 今回の高さ - 今回の帆数 + 1
  h == 1
    step(マストの高さ)++
  h == マストの高さ
    // ありえない(帆を必ずつける)
  h == zoneMin
    step(zoneMin - 1)--   // zoneMin >= 2 のみ
    step(マスト高さ)++
  h == zoneMax
    step(zoneMin - 1)--   // zoneMin >= 2 のみ
    step(zoneMin)++
    zoneMax != マスト高さ
      step(zoneMax)--
      step(マスト高さ)++
  else
    w = zonMax - h + 1    // w >= 1
    step(zoneMin - 1)--   // zoneMin >= 2 のみ
    step(zoneMin + w - 1)++
    zoneMax != マスト高さ
      step(zoneMax)--
      step(マスト高さ)++

h == zoneMax は else の一部なんです。重複しているにもかかわらず、ここをあえて分離することが重要なんです。

  1. 1, 高さの上限(マストの高さ)
  2. zoneMin, zoneMax
  3. それ以外

これらで網羅しているということを、この if 文でしっかり意識しておくことが大事なんです。やろうと思えば、5つに分けているのも実は1つにまとめられると思います。最初、擬似コードを書く時点で、この5パターン以外ありえないことはすぐにわかります。そして、それぞれについて解法を考えます。しかし、それをやりながら、「1つにまとめられるんじゃない?」と欲を出すと、失敗します。難しくて分割したなら、まとめちゃいけません!

リアルソースコードでも、h == zoneMax と else は分離しました。