169.1

SRM

250

マインスイーパの地雷の位置が与えられるので、9x9の盤面を答えよ、という問題。


本当は配列に一つ一つ配置して、いくつ隣接しているかを計算すべきなんだろうけれど、9x9の位置について、3x3方向に地雷があるかどうかを毎回処理した方がルーチン自体は楽に書けるのかも知れない。(入力が正しいなら、配列からはみ出す心配しなくてもいいし。)

500

K個のタスクをN人で分割する時に、最大のタスク割り当て量が最小になるものを答えよという問題。ただし、i番目の人はj番目の人よりも後ろのタスクをやることはできない。


単純にDPでも解けるらしいけれど、タスク量を制限した時に何人必要か、という判定を行って、N人のもののうち最小のものを答えれば良い。


普通はバイナリサーチをやるけれど、15個のタスクで大きさ1000が最大だから、全部で15000回試してみるのでもいい。

900

N鉱山に対して高々6人を割り当てる。鉱山にはK人分の仕事があって、人数が超過すると損をして、逆に少ないと頑張るのでちょっと利益が上がる。全体の利益を最大にするようにM人を余らせないように割り当てよ、という問題。ただし鉱山にある仕事は確率的に与えられる。


すべての鉱山に対して人数に応じて利益の期待値が求まるので、単純DPでX人をY鉱山に対して割り当てた時の最大利益が求まる。最初の鉱山を除いてM-6からM人までを割り当てた時の最大値から、最初の鉱山に何人割り当てれば良いかを決めることができる。これを繰り返せばおしまい。


最後の鉱山に割り当てるときには、残り全員という処理を入れないとダメだったのは、利益がマイナスにもなり得るので初期値を適当に入れていて、その関連でうまくいっていない部分があったんだろうなぁと。(アドホックなことしないで、ちゃんと書きなおすべきだとは思いつつ...。)


頭のいい人は一回の試行で全部の鉱山への割り当てを覚えておくようにルーチンを組むんだろうなぁ。実際そんなに手間じゃないと思うけれど。