242.1

面倒くさいセット。かなり実装するだけの感が強い。

250

N行M列に並べられたカードを左上から縦方向に回収し、横方向に並べていくという操作を繰り返す。あるカードが1回目の操作の時にはK[1]列にあり、...i回目の操作の時にはK[i]列にある時、操作終了後にどの行にあるか答えよ、という問題。

シミュレーションするだけの非常に面倒な問題。カードが一意に定まらなくても、行が決まるケースがあることに注意が必要。

500

二人のプレイヤーについて、それぞれが特殊な目の書かれた6面のサイコロを持っている。各プレイヤーがサイコロを振る回数が与えられるので、プレイヤー1の合計がプレイヤー2の合計よりも大きくなる確率を答えよ、という問題。

それぞれのプレイヤーについて、合計の値の確率をDPで計算する。後はプレイヤー1の目について、プレイヤー2がそれよりも小さい確率になるものを覚えておきつつ順番に計算するだけ。

1000

NxMの紙を二つに分断することなく、K個の1x1が連結した図形を切り取る方法は何通りあるか、という問題。NとMはいずれもKよりも大きい。

まず、K個の1x1が連結した図形を全列挙する。途中で出てきた図形をメモしながらBFSなり何なりで図形を組んでいけばいい。その図形が、角から切るときに角を分断するかどうか、辺から切るときに辺を分断するかどうか、中央から切るときに中央を分断するかどうか、などを判定したうえで、それぞれの位置のうち何通りの切り出し位置があるかを計算すれば良い。