プログラミングコンテストチャレンジブック 3-2, 3-3

第3章 3-2 二分探索からです。

二分探索というと木やヒープからの探索をまっさきに想像しますが、本章では「○○という条件を満たす最大(最小)の N を求めよ」という問題で「n が ○○を満たすか」は高速に判定できるような場合に n について二分探索する方法が主に紹介されています。これは問題についてちょっと見方の転換が必要なのでおもしろいですね。

• cable master
  • N 本の紐を切り出すことができるか、はすぐ判定できるのでそれを 0..INF(充分に大きい数)の区間で二分探索
• Aggressive cows
  • 最大値の最小化、最小値の最大化という問題は二分探索が使えることが多い
  • 最大の牛の間隔を二分探索する
• 平均最大化
  • これも平均値について、それを満たす選択が可能な上限を探索

3-3 「厳選! 頻出テクニック(1)」より。事実上「その他」という分類みたいな章題ですね。

• しゃくとり法
  • 二分探索で解く方法もあり
  • 区間の先頭と末尾をそれぞれ動かしつつ数列をしゃくとりむしがはうように探索する
• Jessica's Reading Problem
  • なんでそんな効率の悪い本教科書にするんだよ、という無粋なつっこみをつい問題文に入れてしまう
  • これも連続した区間を探すのでしゃくとり法で解ける
• Face The Right Way
  • なんでそんな使いづらい装置を導入するんだよ、とこれまた無粋なつっこみを……
  • 一度に反転する数Kを固定した時の解の求め方の工夫がみそ
• Fliptile
  • 指定したタイルの上下左右も白黒反転する操作で全体を白にする操作回数を求める
  • 操作順序が関係ない、同じタイルは2度操作する必要がない、など Face The Right Way と同類。ただし2次元
    • 一番上の行の操作を決めるとあとの操作も決まる