差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
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,​1)でなく(2,​0)である。(左→左→右→右→右)ではじめて、(2,​1)となる。+実際の移動ではなく、初期位置からの最大距離な点に注意。(左→左→右)の移動は(2,​1)でなく(2,​0)であり、(左→左→右→右→右)ではじめて、(2,​1)となる。
  
 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。 例えば $(2,2)$ のロボットは、下の点と右の点、いずれを通過するかで、左右どちらの出口から出るかが分かれる。
ライン 321: ライン 324:
  
 これは何を示すかというと、 これは何を示すかというと、
-までの距離が $i$ のロボットに関して、右までの距離が $j$ 以下のロボットを右、$j$ より大きいロボットを左から出す場合の組合せ数を示している + 
-$i-1$ 以前のロボットについては通った経路によって左も右もあり得るが、それらを踏まえた出口のの個を数え上げ+  * 距離が $i$ 以下ロボットについてのみ考える 
 +  * 左距離がずばり ​$i$ のロボットに関して、右距離が $j$ 以下のロボットを右、$j$ より大きいロボットを左から出す場合の組合せ数を示している 
 +  * 左距離が ​$i-1$ 以前のロボットについては経路によって左も右もあり得るが、それらを踏まえた組合せであ
  
 ただし $j$ については、必要無いのに無駄に右に進むことはせず、 ただし $j$ については、必要無いのに無駄に右に進むことはせず、
ライン 330: ライン 335:
  
 座標上の動きで解釈すると、 座標上の動きで解釈すると、
-("​左"​座標の正の向きが"​右"​なのでややこしいが、座標上の動きを説明するときは、上移動と右移動という言葉を用いる) 
 $(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。 $(0,0)$ からそのまま右に移動するか、上に3つ移動した上で右に1つ移動するかの経路がある、という感じになる。
 +("​左"​座標の正の向きが"​右"​なのでややこしいが、座標上の動きを説明するときは、上と右で表現する)
  
   右 4|       ​o ​ o   右 4|       ​o ​ o
ライン 342: ライン 347:
  
 $i=2$ のロボットのうち、$(2,​4)$ について右から出そうと思えば、 $i=2$ のロボットのうち、$(2,​4)$ について右から出そうと思えば、
-「(1,​0)から4つ上がる」「(1,​3)から1つ上がる」の経路がある。こは、(1,​3)を左右どちらに落としたかに相当する。+「(1,​0)から4つ上がる」「(1,​3)から1つ上がる」の2通りの経路がある。この2つは、(1,​3)を左右どちらに落としたかに相当する。
  
   右 4|     ​【2】o   右 4|     ​【2】o
ライン 355: ライン 360:
 (1,​3)の通り数の中に既に織り込まれていると解釈できる。 (1,​3)の通り数の中に既に織り込まれていると解釈できる。
  
-よって、遷移元とすることが可能な範囲は、$(1,​0),(1,1)$ に限られる。+よって、遷移元とすることが可能な範囲は、$(1,​0)$ に限られる。
  
   右 4|       ​2 ​ o   右 4|       ​2 ​ o
programming_algorithm/contest_history/atcoder/2018/0825_arc101.txt · 最終更新: 2020/03/18 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0