みんなのプロコン 2019 C,D,F問題メモ

Yahoo Programming Contest 2019

• みんなのプロコン 2019 解説放送 - YouTube

C - When I hit my pocket...

• 最初、ビスケットが1枚あり、お金は持っていない
• 以下の操作を好きな順に $K$ 回ちょうど行う
  • ビスケットを1枚増やす
  • ビスケット $A$ 枚を1円に交換
  • 1円をビスケット $B$ 枚に交換
• $K$ 回の操作の後のビスケットの枚数の最大値を求めよ

思考問題。

交換をした方が得なら元手となるビスケット $A$ 枚を用意した後、交換し続ける。

損なら1枚ずつ増やし続ける。

得か損かは、一瞬 $A<B$ なら得かと思ってしまうが、よく考えると交換にも手数がかかるので

         増やし続ける    交換する
N  回目       A             A
N+1回目      A+1          (1円)
N+2回目      A+2            B

なので、$A+2<B$ でないと得にならない。

D - Ears

問題文の設定が常軌を逸しているので適当に変更。

• 数直線上の $0～L$ の範囲をすぬけ君が連続的に移動する
  • 方向転換は整数座標の点でのみ行える
• 空の箱が $L$ 個ある
  • $i$ 番目の箱は、座標 $i-1$ と $i$ の間に置かれている
• すぬけ君は、座標 $i-1$ と $i$ の間を通過するたびに $i$ 番目の箱に石を1個入れる
• 最終的に、$i$ 番目の箱に入っている石を $A_i$ 個に近づけたい
• ぴったり $A_i$ 個に出来なかった箱は、実際に入っている個数を $x_i$ として、$|A_i-x_i|$ のコストがかかる
• 移動を自由に決められるとき、全ての箱のコストの総和を最小化せよ

DP。

すぬけ君が取るべき行動を色々洗い出してみる。

左の箱から順番に入れていくことを考える。

各座標間は個別に何度でも往復できるので、必要な分だけ2ずつ増やせる。左から来て右に抜けないといけないので、入る石の数は奇数個になり、コストは $A_i$ が奇数なら0、偶数なら1となる。

①
      ---|-----|-----|-----|---
Ai    ...   1    101    1   ...
行動  ---------------,
               '-------------->
                  ↑50往復

ただ、途中の点から出発して端で折り返すことができるので、左右それぞれについて端から連続する区間を任意に選ぶと、その中では入る石の数は偶数個になる。コストは $A_i$が 偶数なら0、奇数なら1とできる。

②
      |-----|-----|-----|-----|---
Ai       2     2     1     1   ...
行動   ,---------出発
       `------------------------->

だが、通過したら最低1個は入れないといけないので、たとえば端の方で $A_i=0$ が続くようであれば、そもそも行かない方が良い場合もある。入る石の数は0になり、コストは $A_i$ となる。

③
                 |-----|-----|-----|-----|---
Ai                  2     0     0     0   ...
実際に入る数
  端の方から出発    2     1     1     1       先頭4つのコスト = 3
  端は無視          0     0     0     0       先頭4つのコスト = 2

以上をまとめると、こんな感じになる。各区間は存在しない（長さ0）こともある。

      0      D        S        T        U      L
      |-|-..-|-|-..-|-|-|-..-|-|-|-..-|-|-..-|-|
          ③     ②       ①       ②     ③
行動         ,--------o         <-------,
             `--------------------------'

左右を同時に考えるのは難しいので、分けて考える。ある座標 $d$ で行動を分割する。

• $DP_f[d]=d$ より左から出発して、$d$ に戻ってくる部分の最小コスト（$0～D～S$ と $S～T$ の前半）
• $DP_b[d]=d$ から出発して、$d$ より右で行動を終える部分の最小コスト（$S～T$ の後半と $T～U～L$）

$DP_f[d]+DP_b[d]$ が総コストになるので、$0 \le d \le L$ まで計算し、その最小値が答えとなる。

計算には、動的計画法で3つの状態のコストを管理する。

• $DP_f'[i][p=1/2/3]=$ 座標 $i-1～i$ 間のパターンが $p$ だった時の、コストの最小値
  • $i-1$ より前にどういうパターンだったかは問わない
• $\displaystyle DP_f[i]=\min_{p=1,2,3}(DP_f'[i][p])$

遷移は、以下の通り。行動を考えると、③→②→①の順にしか遷移できないことに注意。

• $\displaystyle DP_f'[i+1][1]=\min_{p=1,2,3}(DP_f'[i][p])+(A_{i+1}が奇数=>0,偶数=>1)$
• $\displaystyle DP_f'[i+1][2]=\min_{p=2,3}(DP_f'[i][p])+(A_{i+1}が0=>2,奇数=>1,2以上の偶数=>0)$
• $\displaystyle DP_f'[i+1][3]=DP_f'[i][3]+A_{i+1}$

$DP_b$ も、末尾から同様に考えることができる。

F - Pass

• $N$ 人が前後一列に並ぶ
• 各々は、赤いボール2個、赤青1個ずつ、青いボール2個のいずれかを持っている（入力で与えられる）
• 空の列がある
• 次の操作を $2N$ 回行う
  • 先頭以外のボールを持つ人は、自分の持つボール1個（2つある場合は好きな方）を前の人に渡す
  • 先頭の人は、列の末尾に自分の持つボール1個（同上）を並べる
• このようにしてできる列の並び順の数を、$\mod{998244353}$ で答えよ

r: 赤  b: 青
N=3        1   2   3
          rr  bb  rb
 1 r      rb  bb  r
 2 rb     rb  rb
 3 rbb    rr  b
 4 rbbr   rb
 5 rbbrr  b
 6 rbbrrb

他にも、rrbbrb や rbbbrr など、10種類の並び順ができうる。

まず、可能な並び順、出来ない並び順は何か、と考える。

たとえば先頭の人が赤を2つ持ってると、列の先頭に青いボールは来ない。

         1   2
        rr  bb
r       rb  b    ←どうしたって青は先頭になれない

同様に、先頭から5人が赤2つ持ってると、6人目が青いボールを持っていたとしても、列の先頭から5つは青いボールは来ない。各人がいくら青を優先的に先頭に移動させても、伝播するのに人数分だけかかる。

         1   2   3   4   5   6
        rr  rr  rr  rr  rr  rb
r       rr  rr  rr  rr  rb  r
rr      rr  rr  rr  rb  rr
rrr     rr  rr  rb  rr  r
rrrr    rr  rb  rr  rr
rrrrr   rb  rr  rr  r
rrrrrb  rr  rr  rr

さらに拡張して、先頭から $i$ 人までに青いボールが $j$ 個しか無いと、列の先頭から $i$ 番目までに青いボールは多くとも $j$ 個までしかこれない。

         1   2   3   4   5   6
        rb  rr  bb  rr  rr  rb  ←┬先頭から1人までに青は1個
b       rr  rb  rb  rr  rb  r     ├先頭から2人までに青は1個
br      rb  rb  rr  rb  rr        ├先頭から3人までに青は3個
brb     rb  rr  rb  rr  r         ├先頭から4人までに青は3個
brbb    rr  rb  rr  rr            └先頭から5人までに青は3個
brbbr   rb  rr  rr  r
~       青は多くとも1つまで
~~      青は多くとも1つまで
~~~     青は多くとも3つまで
~~~~    青は多くとも3つまで
~~~~~   青は多くとも3つまで

赤についても同様のことが言える。

逆にこれさえ満たせば、（rとbの数が合っていれば）どんな列でも可能、らしい。これが十分条件である、という理屈がよくかみ砕けていない……。

前半の $N$ 個の並び順について、DPを行う。（後半の $N$ 個については、特にr,bの個数以外の制限は無いので、Combinationで計算できる）

$DP[i][j]=i$ 回の操作後、列に並べた赤いボールが $j$ 個の時の並べ順の数

先頭 $i$ 個の中の赤いボールの個数 $j$ が同じ（＝青いボールの個数も同じ）なら、$i$ 個の具体的な並び順はその後に影響しないので、まとめてしまえることが重要。

遷移は、制限を無視して考えると、1つずらして足し合わせる感じ。これだけだと二項係数になる。

   j     0   1   2   3   4  ...
DP[i]    1   3   3   1   0  ...
         ↓↘↓↘↓↘↓↘      ↓: 青いボールを置く
DP[i+1]  1   4   6   4   1     ↘: 赤いボールを置く に相当

そして制限を考慮に入れると、$i$ 人目までの赤と青のボールの数を数えておき、

• 青いボールの数が足りないなら左端の↓の遷移が無理
• 赤いボールの数が足りないなら右端の↘の遷移が無理

なので、その遷移を除く。端以外はそれぞれ青、赤のボールがまだ余っているので、端のみ考慮すればよい。

   j     0   1   2   3   4  ...
DP[i]    1   3   3   1   0  ...
         ×↘↓↘↓↘↓↘    青いボールが足りない
DP[i+1]  0   4   6   4   1   

DP[i]    1   3   3   1   0  ...
         ↓↘↓↘↓↘↓×    赤いボールが足りない
DP[i+1]  1   4   6   4   0   

こうして$DP[N][j]$ まで計算すると、「前半の $N$ 個までに赤を $j$ 個置いた場合の並び順の数」が各 $j$ についてわかる。

すると、後半に赤をいくつ、青をいくつ並べればよいかが、$j$ より計算できる。赤の総数を $r$ とすると、$r-j$ となる。

後半の並べ方は特に制限は無いので、Combinationを用いて ${}_NC_{r-j}$ となる。

前半と合わせて、$\displaystyle \sum_{j=0}^N(DP[N][j] \times {}_NC_{r-j})$ が答えとなる。

遷移が、配列を1つずらして足し合わせる（あと制限による微調整）だけなので、PythonならNumPyを使って高速化できる。

numpy.roll(a, n) で、配列aをnだけ後ろに回転させた配列を得ることが出来るので、それを足し合わせればよい。 roll()は末尾要素が先頭に来てしまうが、今回の場合、1しかずらさないし、$i=N$ までずっと末尾要素は0なので、影響が無い。

ただ、その過程で気付いたのだが、配列に自身をずらして足し合わせる方法は、この他に、スライスで一部に加算代入する方法もある。しかし、この方法はAtCoderのNumPyのVersionではバグ？があるっぽい。

これまで、NumPyを使うとWAになることがあったが、ひょっとしてこれだったか……