差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/16] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/16] – [解法] ikatakos | ||
|---|---|---|---|
| 行 315: | 行 315: | ||
| これを踏まえて、以下のDPを考える。 | これを踏まえて、以下のDPを考える。 | ||
| - | * $DP[i][j]=左出口までの距離がi$ であるロボットまでを見て、最後に左に1つ進めるまでの右に進んだ最大距離が j だった時の、出口の組の個数 | + | * $DP[i][j]= |
| * DP[0][0]=1 | * DP[0][0]=1 | ||
| + | |||
| + | これは何を示すかというと、 | ||
| + | |||
| + | * 左出口までの距離が i 以下のロボットだけを考える | ||
| + | * 座標 i のロボットに関して、右出口までの距離が j 未満のロボットを左、j 以上を右から出している | ||
| + | * i−1 以前のロボットは、通った経路によって左も右もあり得るが、それらを踏まえた出口の組の個数を示す | ||
| ただし j については、必要無いのに無駄に右に進むことはせず、 | ただし j については、必要無いのに無駄に右に進むことはせず、 | ||
