差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | |||
| programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/17] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2018:0825_arc101 [2020/03/18] (現在) – [解法] ikatakos | ||
|---|---|---|---|
| 行 264: | 行 264: | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| - | あるロボットが出る出口は、初期位置の左右両脇にある2通りの出口しかあり得ない。 | + | あるロボットが出る出口は、初期位置の左右両脇にある2通りの出口のどちらかしかあり得ない。 |
| （ただし、左右最も外側の出口より外のロボットは1通りのため、考慮から除いてよい） | （ただし、左右最も外側の出口より外のロボットは1通りのため、考慮から除いてよい） | ||
| 行 272: | 行 272: | ||
| また、「①左まで3、右まで4」と「②左まで2、右まで5」というロボット①、②があったら、 | また、「①左まで3、右まで4」と「②左まで2、右まで5」というロボット①、②があったら、 | ||
| ①を左から出しつつ、②を右から出すことは出来ない。 | ①を左から出しつつ、②を右から出すことは出来ない。 | ||
| - | なぜなら、出す出口の左右を分けるにしても、まずは左右どちらかから一方を出さないといけないが、 | + | なぜなら、まずは左右どちらかから一方を出さないといけないが、 |
| - | ①を左まで持ってったら②が既に左から出ているし、逆も然り。 | + | ①を左まで持ってったら②が既に左から出ているし、逆も然りなためである。 |
| + | その他の左右の組合せは可能。 | ||
| で、こういう条件が沢山あるのをまとめ上げるのに、解説pdfに倣い、2次元座標に変換して考える。 | で、こういう条件が沢山あるのをまとめ上げるのに、解説pdfに倣い、2次元座標に変換して考える。 | ||
| - | 前処理として、各ロボットの「左までの距離の集合」「右までの距離の集合」の2つについて独立に座標圧縮をしておく。 | + | 「左出口までの距離」を「左距離」、「右出口までの距離」を「右距離」と言うことにする。 |
| - | （実際には、座標圧縮は「右までの距離の集合」のみでよいが、説明上、左も行っているものとする） | + | |
| - | 例えば左右の出口までの距離の集合が以下のようだったとして、 | + | 前処理として、各ロボットの「左距離の集合」「右距離の集合」の2つについて独立に座標圧縮をしておく。 |
| + | （実際には、座標圧縮は右のみでよく、左はソートさえすればよいが、説明上、左も行っているものとする） | ||
| + | |||
| + | 例えば左右距離の集合が以下のようだったとして、 | ||
| 左 右 | 左 右 | ||
| 行 301: | 行 304: | ||
| $(0,0)$ からスタートして、座標を「左右それぞれ初期位置から移動させたことのある最大距離」と解釈して移動を行う。 | $(0,0)$ からスタートして、座標を「左右それぞれ初期位置から移動させたことのある最大距離」と解釈して移動を行う。 | ||
| - | 上か右のみに移動することになる。 | + | つまり、上か右のみに移動することになる。 |
| - | 実際の移動ではなく、最大距離な点に注意。(左→左→右)の移動は(2, | + | 実際の移動ではなく、初期位置からの最大距離な点に注意。(左→左→右)の移動は(2, |
| 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 | ||
| 行 321: | 行 324: | ||
| これは何を示すかというと、 | これは何を示すかというと、 | ||
| - | 「左までの距離が $i$ のロボットに関して、右までの距離が $j$ 以下のロボットを右、$j$ より大きいロボットを左から出す」場合の組合せ数を示している。 | + | |
| - | $i-1$ 以前のロボットについては通った経路によって左も右もあり得るが、それらを踏まえた出口の組の個数を数え上げる。 | + | * 左距離が $i$ 以下のロボットについてのみ考える |
| + | * 左距離がずばり | ||
| + | * 左距離が | ||
| ただし $j$ については、必要無いのに無駄に右に進むことはせず、 | ただし $j$ については、必要無いのに無駄に右に進むことはせず、 | ||
| 行 330: | 行 335: | ||
| 座標上の動きで解釈すると、 | 座標上の動きで解釈すると、 | ||
| - | （" | ||
| $(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。 | $(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。 | ||
| + | （" | ||
| 右 4| | 右 4| | ||
| 行 342: | 行 347: | ||
| $i=2$ のロボットのうち、$(2, | $i=2$ のロボットのうち、$(2, | ||
| - | 「(1, | + | 「(1, |
| 右 4| | 右 4| | ||
| 行 355: | 行 360: | ||
| (1, | (1, | ||
| - | よって、遷移元とすることが可能な範囲は、$(1, | + | よって、遷移元とすることが可能な範囲は、$(1, |
| 右 4| | 右 4| | ||
