250の早解きセット。
250
x軸に垂直に置いてある複数のものがある。貫通するレーザーをランダムに照射するとき、当たる数の期待値を答えよ、という問題。
衝突するレーザーの照射角度の最小値と最大値をそれぞれのものについて求めて、レーザーの照射可能範囲に占める割合を計算するだけ。
500
各桁の数字が昇順に並んでいる数を、K個の部分に分けたとき、すべてが等差の桁からなるような分割が存在し、K-1個の部分に分けたときそのような分割が存在しないものを答えよ、という問題。
数字は9個しかないので、どんな数もK>=10個の部分に分割可能ならばK-1個の部分に分割可能。Kが小さい範囲をうまいことメモ付き探索でもするんじゃないかなぁ、という感じ。
1000
NxNの盤面上にいくつかの使えない領域がある。使えない領域を含まない任意の矩形領域について、他のそのような領域に完全には含まれないものの個数を求めよ、という問題。
Nビットの数に各行をエンコードして云々、みたいなことはできないかなぁ...。O(N^3)で良ければ簡単にできそう？
取り敢えずO(N^3)のアルゴリズムを実装してみたら10倍くらいの高速化が必要そう。盤面をlongか何かにエンコードすると、パターンマッチにビット演算が使えるようになるので、10倍くらいなら早くなるかも。(そういう問題じゃないと思うけど...。)
