review-F

Problem F [1 of 4]
: Northeastern 2001
► 岩に長方形の穴（niche）をほって、そこに杭を打って
棚板を載せて本棚を作った
► ところが、棚の位置や長さを変えないと入らないような
本（tome）が見つかってしまった
► 出典
tome
Problem F [2 of 4]
► 本棚と本のサイズ、および棚、杭の位置と長さ
が与えられる。本をおくために抜かなければな
らない杭の最低本数、およびそのときにおける
棚板の切断部分の最短の長さを計算するプロ
グラムを作成せよ。なお、本はどの棚の上に、
またどの位置においても構わない。
Problem F [3 of 4]
► それぞれの棚に対する可能な操作






そのままにしておく
棚を左または右に移動する
棚板を切り落とす
一方の杭を別の場所に移す
一方の杭を別の場所に移す + 棚板を切り落とす
棚および両方の杭を取り除く
Problem F [4 of 4]
► 移動後に棚が満たすべき条件
 棚が両方の杭の上にのっている
 棚の中央が 2 つの杭の間にある（両端も含む）
► その他の条件




本棚のサイズは最大で 1000×1000
棚数は 1～100
棚の移動および切断は整数単位に限られる
棚をうまく移動すれば本は絶対における
Solution of Problem F [1 of 5]
► 本をおく位置さえ決まれば、それぞれの棚の操
作は決められる
 棚を左にのけた場合と右にのけた場合とでコストを
計算して、小さいほうを採用する
 ここでのコストは、抜かなければならない杭の本数
と切り落とさなければならない棚板の長さ
► 本をおけるようなすべての位置についてコスト
を計算すれば、当然最小値も出る
 本棚の幅が最大 1000 であるため、実は横に 1 イ
ンチずつ動かして計算しても間に合う
Solution of Problem F [2 of 5]
► コストの計算
 杭を動かさない場合と動かす場合にわける
 棚板のとりうる長さを考えれば、棚板の切断する部
分の長さは自然に決まる
 棚を右にのける場合は、左右を反転させれば、左
にのける場合に帰着できる（そこで、以降は左にの
ける場合のみを考えることにする）
Solution of Problem F [3 of 5]
► 杭を動かさない場合
 移動限界
►棚の右端が右側の杭に到達するまで
 とりうる棚板の長さ
►左側の杭と棚の右端との距離の倍
►左側の壁から棚の右端までの距離
►もとの棚板の長さ
これらの最小値
Solution of Problem F [4 of 5]
► 杭を動かす場合
 移動限界
►棚の右端が左側の杭に到達するまで
►ただし左側の杭が左端にあるときはその 1 インチ右側
 とりうる棚板の長さ
►杭の位置を選べることから、棚板が壁にぶつからない限
りは棚板を切断する必要はない
►残りの杭が棚の中央より左側にあるならば棚の右端に、
そうでなければ棚の左端に杭を打ちこむ
Solution of Problem F [5 of 5]
► 補足
 左側あるいは右側のどちらにものけることができな
いときのみ、棚を取り外す
► 注意点
 左端あるいは右端に長さ 0 の棚を作らないこと
► その他
 本問題は内容の整理がとても難しい
 コード自体は比較的単純

Download Report