うにゅーん、って感じだ

SRM, CF, AtCoder黄. SRM highest:1746. C#を書きます.

No.335 門松宝くじ, No.336 門松列列

奇跡的に全完できたけど、普通にクソ苦手なセットだった
門松列の流行早く終わってくれ

No.335 門松宝くじ - yukicoder
No.336 門松列列 - yukicoder



門松宝くじは、当確率である2つの数字が選ばれたとき、3つの数字が門松列かつ3つの数字のmaxが最大になるようにもう1つの数字を選ぶようにして、そのときのmaxの期待値を出す問題(自分でも何を言っているのかわからない…)

普通に全部の選ばれる数字の組({_nC_2}通り)に対して ({n-2})通り全探索すると {O(n^3)} となりダメ(最初、800^3 = 2400万だと勘違いしてこれで出した)


そこで、選ばれた2つの数字について具体的に考えていきます

  • 選ばれた2数a, b(a < b)について、元の順列におけるindexが index[a] < index[b] のとき

下図(横軸 : index, 縦軸 : 数値)で適当に赤く塗られたところの数をあと一つの数として選べば、3数は門松列になります
f:id:riantkb:20160118132310p:plain

ここから、実は区間のMaxとminさえ持っていれば良いことがわかります

max[i][j]を区間[i, j]におけるMax、min[i][j]を区間[i, j]におけるminとすると、

max[0][index[b] - 1] > b のとき ...... 得点は max[0][index[b] - 1]
max[0][index[a] - 1] > a のとき ...... 得点は b
min[index[b] + 1][n - 1] < b のとき ...... 得点は b
min[index[a] + 1][n - 1] < a のとき ...... 得点は b
上のいずれにも適さないとき ...... 門松列を作れないので得点は 0

max[i][j], min[i][j] を前もって {O(n^2)} で求めておけば、各組に対して定数時間で求めることができ、結果 {O(m n^2)} となります

index[b] < index[a] のときも同じような感じで求めることができます



門松列列は、順列の並び替えの中でジグザグな列は何通りあるか、という問題
(どっかで見たことある気がするけど、題意は {a_i < a_{i + 1} < a_{i + 2}} または {a_i > a_{i + 1} > a_{i + 2}} となる i が存在しないことと同義)


まぁ、DPを考えます。


i - 1番目の数がi番目の数より大きかったかどうかで、i + 1番目にどのような数を置けるかが決まります
(例えば ......, 6, 4 というところまで数列を作っていたら、次の数は5以上でなければならない)


使える数字は決まっていて、一度使った数字は使えないので、次に置ける数字がm個、次に置けない数字がn個だとすると下図のようになります
f:id:riantkb:20160118135420p:plain

このとき、次のような漸化式が成り立ちます

dp[m + n][m] = dp[m + n - 1][n] + dp[m + n - 1][n + 1] + ... + dp[m + n - 1][m + n - 1] (dp[0][0] = 1)
(dp[m + n - 1][k] は、次に置ける数の中でk - n + 1番目に小さい数を選んだときの場合の数)


これをこのままループを回すと {O(N^3)} となりますが、
sum[i][j] = {\sum_{k = 0}^{j - 1}} dp[i][k]
を順次求めておけば {O(N^2)} となり、間に合います


求めるものは、sum[N - 1][N] * 2 です


なんかすごい変なDPをしている自覚はあります......


それぞれ、提出はこんな感じです
#71404 No.335 門松宝くじ - yukicoder
#71459 No.336 門松列列 - yukicoder