128. AtCoder参加記録（AtCoder Beginner Contest 263）

先週は体調不良のためお休み。

32回参加でレート 1336 です。

今回はパフォーマンス 1495 です。

ABCDを通して、FGExは未解答です。Eは通せず。

各問題の思考過程など。

3分22秒。

制約の文どういうこと…？と思いましたが、あんまり関係なさそうなので気にしないことにしました。

Dictionary で枚数を保持して判定しましたが、なんか無駄に複雑になったような気もします。

3分13秒。

$i \rightarrow P_i$ の有向辺を張って、 $N$ から辿って $1$ に辿り着いたときの深さが答え。

5分35秒。

辞書順に順列を生成するのはライブラリ化していたので、これを少し調整して狭義単調増加列のみ生成するようにしました。

13分34秒。

すぐには分からなかったので、入力例 1 を書き出して考えてみる。
貪欲に考えてみるが、ちょっと無理そう。
$x$ と $y$ 両方あるのが厄介なので、 $x$ だけ考えてみる。
全部 $L$ に置き換えてみて、各項の差分を考える。 $x$ を決めた時の総和への影響は、差分の累積和（ $c_i$ とする）によって $O(1)$ で求められる。 $y$ についても同様。
$y$ が決まっているなら、最適解は $\displaystyle \min_{1 \le i \le N - y}c_i$ である。これはセグメント木で $O(\log N)$ で求められる。
あとは $y$ を全探索すれば $O(N \log N)$ で間に合う。

初回提出51分44秒。解けず。

最初20分くらい考えていた方針は破綻してそうだったので、EDPCの似た問題を思い出し、解き方がすぐ思い出せなかったので解説記事を読む。これと同じことをすればよさそう。
$dp[i] := i にいるとき N へ辿り着くまでにサイコロを振る回数の期待値$ とすると、 $\displaystyle dp[i] = 1 + \frac{1}{A_i + 1}dp[i] + \frac{1}{A_i + 1}\sum_{j=1}^{A_i}dp[i+j]$ 。
式を整理して $\displaystyle dp[i] = \frac{A_i + 1}{A_i}\left( 1 + \frac{1}{A_i + 1}\sum_{j=1}^{A_i}dp[i+j] \right)$ 。
総和計算で TLE しそうだが、ここは累積和なりで何とかなりそう…だけど、ゴチャってきたので一度投げてみる。