TopCoder SRM 494 (Div 1)

Result

153.00 / Opened / Unopened
チャレンジ4ミス
518位

1710 ->1627

Painting

問題

グリッドにBまたはWの文字が書かれている。
グリッドは最初全てWで、Bの文字の書かれたグリッドだけをSxSの正方形のブラシを使ってすべて塗りつぶしたい。
描く正方形は何度重なってもいいが、グリッドの外や、Wのグリッドにはみ出てはいけない。

与えられた図形を描ける最大のブラシのサイズはいくつか。
盤の一辺は50以下。

試行錯誤

まずは愚直なアルゴリズムを考える。O(n^5)？
50^5だと間に合わないのでは……どうしよう。

随分難しい250じゃないの……
正方形数えのDPとか使うんだろうか。（しばらく悩む）
あ、ビット使えばO(n^4)で出来る。

書いた。送信。

AlternatingLane

問題

木の列がジグザグであるとは、
h[0] > h[1] < h[2] >…または
h[0] < h[1] > h[2] <…が成り立つこと。

ある木の列があったとして、それがジグザグでないなら、途中の木を切り倒す。
そのようにして得られたジグザグな列に対して、スコアを次のように定める。

S=Σabs(h[i+1] - h[i])
ただしn=1のときはスコアは0である。

それぞれの木の高さはlow[i]以上high[i]以下の整数を同じ確率で取るとき、
Sの期待値を求めよ。

試行錯誤

DPっぽいのきた。
O(n H^2)の自明な解法はTLEなのでそれをO(nH)に落とすんだろうか。

考えてみる。
dp[i][j][k]にi番目まで木を見て、i番目の木の高さがjで、今増加してきたならk=1,減少してきたならk=0
のときのスコアを入れておくみたいな表を持っておく。

すると……？次のスコアの期待値を求めるには今の確率も覚えておかないといけない？
じゃあp[i][j][k]みたなテーブルが必要になって？
dp[i+1][j][k]にはjがlow[i]からhigh[i]を動きながらdp[i][j][k]*p[i][j][k]+スコア更新分みたいなのが足されて、
んで最後にp[i+1][j][k]で割られるとかそんな感じだろうか。

うげー解ける気がしない。

しばらく考えて時間切れ。

Challenge

O(n^5)のやつに適当にでかいケースを投げてみる。
みんな普通に時間内に答えを返す。何でだろう……

System Test

通った。。。