差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン最新のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/17] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/17] – [解法] ikatakos | ||
|---|---|---|---|
| 行 300: | 行 300: | ||
| 0 1 2 3 4 左 | 0 1 2 3 4 左 | ||
| - | $(0,0)$ からスタートして、座標を「左右それぞれ移動させたことのある最大距離」と解釈して移動を行う。 | + | $(0,0)$ からスタートして、座標を「左右それぞれ初期位置から移動させたことのある最大距離」と解釈して移動を行う。 |
| 上か右のみに移動することになる。 | 上か右のみに移動することになる。 | ||
| + | |||
| + | 実際の移動ではなく、最大距離な点に注意。(左→左→右)の移動は(2, | ||
| 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | ||
| 行 315: | 行 317: | ||
| これを踏まえて、以下のDPを考える。 | これを踏まえて、以下のDPを考える。 | ||
| - | * $DP[i][j]= (i-1,j)$ まで移動したときの、下を先に通過したロボットと左を先に通過したロボットの組み合わせ数 | + | * $DP[i][j] = (i-1,j)$ まで移動したときの、下を先に通過したロボットと左を先に通過したロボットの組み合わせ数 |
| * $DP[0][0] = 1$ | * $DP[0][0] = 1$ | ||
