297.1

昔似たような500をやったことがあるので、同じ方針でやったらTLEするという悲しい500が...。他の方針が浮かばなくなるくらい普通の方針なんだけどなぁ...。

250

N人待っている人がいて、それぞれの待っていた時間が与えられる。K人まで並列処理ができ、一人当たりTだけ時間がかかるとき、N人のうちの最大の消費時間として最小の値を求めよ、という問題。

最大時間についてバイナリサーチする。たくさん待っている人から順に、自分がその時間に間に合う中で一番長い列に並ぶようにすれば良い。

500

NxMの盤面が与えられて、初期位置として可能な場所がいくつか与えられる。1行ないし1列の単位で壁を追加して、外に出られなくなる初期位置を作るとき、必要な最小壁数を答えよ、という問題。

初期位置がすべて脱出可能なケースを除けば、高々4つ壁があればいずれかの初期位置を封鎖することができる。(4方向をふさげば良いので。)なので任意の三つの行と列(高々2行と高々2列)について、封鎖するところを選んで、外側からBFSして到達できない初期位置があるかどうかを判定すれば良い。N=M=40なのでO(40^5)になるのだけれど、微妙に終わらない。

最悪のケースは4個置かないとダメなケースで、その場合BFSはどうやっても盤面全部舐めることになるのが難点。初期位置として可能な点をすべてメモしておいて、脱出可能位置のいずれかに到達したら脱出、という判定を全部にやる方が若干高速なので、もしかしたらそれだけで追い付くかも知れない。(もっと劇的な解決策があるのかも知れないので実装する気分になれない。)

1000

立方体の箱が2x2xHの形に並んでいる。それぞれの箱に50％の確率で爆弾が仕掛けられており、隣接するものをグループとみなす。最大のグループの爆弾数がN以上となる確率を求めよ、という問題。

2x2の状況における爆弾配置は16通りある。これをH個積んでいく。16x16の遷移を考慮しつつ、現在つながっているグループの数を覚えておく。2x2なので、可能なグループ数は高々2個だけ。各グループについてN未満のままH個2x2を積めれば良いので、16xNxNのテーブルを持っておけば良い。後は状態間の遷移をすべて考えてDPするだけ。

2x2のうち斜めに2つ並んでいる時だけ、グループが分かれているかくっついているかを覚えておく必要があるので注意が必要。

Expected:
7.52316384526264E-37

Received:
3.973461317744941E-15

TopCoderルールだと絶対誤差が1.0e-9以下だったら良かったりするので、凄く小さい値のときは適当な値が入ってる。他のケースであってるから、やり方とか誤差の積み重ねとかが違うだけなので、特に問題はないけれど、なんだかなぁ、な結果が見えてしまう。