[[みんなのプロコン 2019 C,D,F問題メモ]]
現在位置: トップページ » アルゴリズム » contest_history » 索引 » 2019 » みんなのプロコン 2019 C,D,F問題メモ
管理サイトマップ

目次

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

Yahoo Programming Contest 2019

C - When I hit my pocket...

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$ でないと得にならない。 

k, a, b = map(int, input().split())
if a + 2 >= b:
    print(k + 1)
elif k <= a - 1:
    print(k + 1)
else:
    remain = k - (a - 1)
    d, m = divmod(remain, 2)
    ans = a + (b - a) * d + m
    print(ans)

D - Ears

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$ も、末尾から同様に考えることができる。 

import sys


def calc(itr):
    dp = [0]
    turn, no_turn, no_visit = 0, 0, 0
    for a in itr:
        b = a % 2
        new_turn = min(turn, no_visit) + (2 if a == 0 else b)
        new_no_turn = min(turn, no_turn, no_visit) + (b ^ 1)
        new_no_visit = no_visit + a
        dp.append(min(new_turn, new_no_turn, new_no_visit))
        turn, no_turn, no_visit = new_turn, new_no_turn, new_no_visit
    return dp


l = int(input())
aaa = list(map(int, sys.stdin))

dp_f = calc(aaa)
dp_b = calc(reversed(aaa))
dp_b.reverse()

print(min(map(sum, zip(dp_f, dp_b))))

F - Pass

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の数が合っていれば）どんな列でも可能、らしい。これが十分条件である、という理屈がよくかみ砕けていない……。

DPの構築

前半の $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})$ が答えとなる。

NumPy

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

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

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

import numpy as np

a = np.array([1, 2, 4, 8])
a[1:4] += a[0:3]
print(a)

# [1, 2+1, 4+2, 8+4] => [1, 3, 6, 12] になってほしい
# 手元のNumPy 1.14.x で実行すると、ちゃんとそうなる

# AtCoder(NumPy 1.8.2)のコードテストで実行すると、[ 1  3  7 15] になる
# [1, 2+1] まで計算して、次に 4+a[1] を計算する時、計算済みの'3'を参照している模様

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

import numpy as np


def prepare(n):
    f = 1
    for i in range(2, n + 1):
        f = f * i % MOD
    inv = [1] * (n + 1)
    inv[n] = pow(f, MOD - 2, MOD)
    for i in range(n, 0, -1):
        inv[i - 1] = inv[i] * i % MOD
    return f, inv


MOD = 998244353
s = input()
n = len(s)
dp = np.zeros(n + 1, dtype=np.int64)
dp[0] = 1
b_all = 0
i, j = 0, 1
for k in range(n):
    b_all += int(s[k])
    ball = 2 * (k + 1)
    dp += np.roll(dp, 1)
    dp %= MOD
    if j <= ball - b_all:
        j += 1
    else:
        dp[j] = 0
    if k - i < b_all:
        pass
    else:
        dp[i] = 0
        i += 1
r_all = 2 * n - b_all
f, inv = prepare(n)
ans = 0
for k in range(i, j):
    r = r_all - k
    b = n - r
    ans += dp[k] * f % MOD * inv[r] % MOD * inv[b]
    ans %= MOD
print(ans)

programming_algorithm/contest_history/atcoder/2019/0209_yahoo-procon2019-qual.txt · 最終更新: 2019/02/11 by ikatakos
メディアマネージャー文書の先頭へ
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0