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)を例題として挙げてくれていたので、これも解いた。
ぽや