差分
このページの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 | ||
---|---|---|---|
行 275: | 行 275: | ||
①を左まで持ってったら②が既に左から出ているし、逆も然り。 | ①を左まで持ってったら②が既に左から出ているし、逆も然り。 | ||
- | で、こういう条件が沢山あるのをまとめ上げるのに、2次元座標に変換して考える(解説pdf)。 | + | で、こういう条件が沢山あるのをまとめ上げるのに、解説pdfに倣い、2次元座標に変換して考える。 |
- | <wrap hi>前処理として、各ロボットの右までの距離の集合について座標圧縮をしておく。</ | + | 前処理として、各ロボットの「左までの距離の集合」「右までの距離の集合」の2つについて独立に座標圧縮をしておく。 |
+ | (実際には、座標圧縮は「右までの距離の集合」のみでよいが、説明上、左も行っているものとする) | ||
例えば左右の出口までの距離の集合が以下のようだったとして、 | 例えば左右の出口までの距離の集合が以下のようだったとして、 | ||
行 299: | 行 300: | ||
0 1 2 3 4 左 | 0 1 2 3 4 左 | ||
- | $(0,0)$ からスタートして、座標を「左右それぞれ移動させたことのある最大距離」と解釈して移動を行う。 | + | $(0,0)$ からスタートして、座標を「左右それぞれ初期位置から移動させたことのある最大距離」と解釈して移動を行う。 |
上か右のみに移動することになる。 | 上か右のみに移動することになる。 | ||
+ | |||
+ | 実際の移動ではなく、最大距離な点に注意。(左→左→右)の移動は(2, | ||
例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | ||
行 314: | 行 317: | ||
これを踏まえて、以下のDPを考える。 | これを踏まえて、以下のDPを考える。 | ||
- | * $DP[i][j]=$ | + | * $DP[i][j] = (i-1,j)$ まで移動したときの、下を先に通過したロボットと左を先に通過したロボットの組み合わせ数 |
* $DP[0][0] = 1$ | * $DP[0][0] = 1$ | ||
+ | |||
+ | これは何を示すかというと、 | ||
+ | 「左までの距離が $i$ のロボットに関して、右までの距離が $j$ 以下のロボットを右、$j$ より大きいロボットを左から出す」場合の組合せ数を示している。 | ||
+ | $i-1$ 以前のロボットについては通った経路によって左も右もあり得るが、それらを踏まえた出口の組の個数を数え上げる。 | ||
ただし $j$ については、必要無いのに無駄に右に進むことはせず、 | ただし $j$ については、必要無いのに無駄に右に進むことはせず、 | ||
行 335: | 行 342: | ||
$i=2$ のロボットのうち、$(2, | $i=2$ のロボットのうち、$(2, | ||
- | 「(1, | + | 「(1, |
右 4| | 右 4| | ||
行 467: | 行 474: | ||
そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。 | そのため、Pythonなら逐一割るより、MODを全く無視して計算して、最後に1回だけ割った方が高速となった。 | ||
- | 割り算遅いっすね。いや、どちらかというと多倍長が(表面上は)何の工夫もせずに書ける割に高速なのか。 | + | 割り算遅いっすね。いや、どちらかというと多倍長が(表面上は何の工夫もせずに書ける割に)高速なのか。 |