差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/16] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/17] – [解法] ikatakos | ||
|---|---|---|---|
| 行 278: | 行 278: | ||
| 前処理として、各ロボットの「左までの距離の集合」「右までの距離の集合」の2つについて独立に座標圧縮をしておく。 | 前処理として、各ロボットの「左までの距離の集合」「右までの距離の集合」の2つについて独立に座標圧縮をしておく。 | ||
| + | （実際には、座標圧縮は「右までの距離の集合」のみでよいが、説明上、左も行っているものとする） | ||
| 例えば左右の出口までの距離の集合が以下のようだったとして、 | 例えば左右の出口までの距離の集合が以下のようだったとして、 | ||
| 行 314: | 行 315: | ||
| これを踏まえて、以下のDPを考える。 | これを踏まえて、以下のDPを考える。 | ||
| - | * | + | * $DP[i][j] = (i-1,j)$ まで移動したときの、下を先に通過したロボットと左を先に通過したロボットの組み合わせ数 |
| * | * | ||
| + | |||
| + | これは何を示すかというと、 | ||
| + | 「左までの距離が のロボットに関して、右までの距離が 以下のロボットを右、 より大きいロボットを左から出す」場合の組合せ数を示している。 | ||
| + | 以前のロボットについては通った経路によって左も右もあり得るが、それらを踏まえた出口の組の個数を数え上げる。 | ||
| ただし については、必要無いのに無駄に右に進むことはせず、 | ただし については、必要無いのに無駄に右に進むことはせず、 | ||
| 行 335: | 行 340: | ||
| のロボットのうち、 について右から出そうと思えば、 | のロボットのうち、 について右から出そうと思えば、 | ||
| - | 「(1, | + | 「(1, |
| 右 4| | 右 4| | ||
| 行 467: | 行 472: | ||
| そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。 | そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。 | ||
| - | 割り算遅いっすね。いや、どちらかというと多倍長が（表面上は）何の工夫もせずに書ける割に高速なのか。 | + | 割り算遅いっすね。いや、どちらかというと多倍長が（表面上は何の工夫もせずに書ける割に）高速なのか。 |
