1/19 日記

おい!!!!!!今日は寝るぞ!!!!!!!

ぷらにゃ~が好きすぎるこの頃。

やったこと

・並列二分探索

CODE THANKS FESTIVAL 2017 H - Union Sets (並列二分探索解法) - ARMERIA (hateblo.jp)この記事にざっと目を通しただけ。明日ちゃんと読むよ。

・Sambo's Treasure

No.1354 Sambo's Treasure - yukicoder典型っぽそうだったのでチャレンジ。

チェックポイントをソートして、i番目を始点、i+1番目を終点とする。

始点から終点までいく間にcnt回トラと遭遇したときの場合の数を考えれば、あとでまとめてあげればいい。

dp[i][j]:=始点からi番目のトラとあったとき、合わせてj匹のトラとあっているときの場合の数

として、dp[i][j]=∑dp[k][j-1]*(k番目からi番目へ行く方法)-∑dp[i][x](x>=j)

というふうに計算できる。

まとめるパートは、チェックポイントで挟まれる区間を一つ見るごとに

dp[cnt]:=現在のチェックポイントに至るまでにcnt匹のトラとあう場合の数

をO(cnt^2)で更新していけばいい。

れたすさんの記事を見たらY - Grid 2 (atcoder.jp)を例題として挙げてくれていたので、これも解いた。

 

ぽや