競技プログラミング

ABC167

はじめに

この記事では、AtCoder Beginer Contest 167のA~E問題を解説します。

A - Registration

https://atcoder.jp/contests/abc167/tasks/abc167_a

Pythonの場合、文字列のスライスが便利です。

1
2
3
4
5
6
S = input()
T = input()
if S == T[:-1]:
    print ('Yes')
else:
    print('No')

B - Easy Linear Programming

https://atcoder.jp/contests/abc167/tasks/abc167_b

minを使って、Kを減らしながらカードを取っていきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
A,B,C,K = map(int,input().split())

ans = 0
mn =  min(A,K)
K -= mn
ans += mn

mn =  min(B,K)
K -= mn

mn =  min(C,K)
K -= mn
ans -= mn
print(ans)

C - Skill Up

https://atcoder.jp/contests/abc167/tasks/abc167_c

bit全探索を行います。itertools.productが便利です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from itertools import product
N,M,X = map(int,input().split())
C = []
A = []
for n in range(N):
    a = list(map(int,input().split()))
    C.append(a[0])
    A.append(a[1:])
INF = 10**9
ans = INF
for p in product([0,1], repeat=N):
    sm = [0] * M
    cost = 0
    for i in range(N):
        if p[i]: # bitが立っていたら
            for m in range(M):
                sm[m] += A[i][m]
            
            cost += C[i] 
    #print (p,sm)
    if min(sm) >= X:
        ans = min(ans,cost)
if ans==INF: # 更新されていなければ-1を出力
    print (-1)
else:
    print (ans)

D - Teleporter

https://atcoder.jp/contests/abc167/tasks/abc167_d

ループを検知すれば良いです。その際に、いつループに入ったかを後ほど利用します。(bias)

具体的には一旦Kからbiasを引いて、ループの省略をした後に再度biasを足します。

これは、単純に周期で割ってしまうとループに入る前の遷移を無視することになってしまうためです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
turn = [-1] * (N+1) # いつ訪問したかを記録する
c = 1
for k in range(K):
    if turn[c]!=-1:
        T = k - turn[c] # 周期
        bias = turn[c] # バイアス
        break
    turn[c] = k
    c = A[c]
else:
    print (c)
    exit()

K -= bias 
K %= T
K += bias
c = 1 
for k in range(K):# 小さくしたKでシミュレーションし直す
    c = A[c]
print (c)

E - Colorful Blocks

https://atcoder.jp/contests/abc167/tasks/abc167_e

K=kとしてKを固定して考えて、全てのKについて足し合わせれば良いです。

ペアは全部でN-1個あるので、ペアの選び方は

1
nCk(N-1,k)

となります。
どのようにペアを選んでも、連続する同色ブロックをグループとみなすと、グループは全部でN-kとなります。

グループの列に色を塗っていきます。最初のグループはM色の何でもよく、それ以降のグループは前のグループとは違うM-1色から選ぶことになります。すなわち、グループの列に対する色の塗り方は

1
M * (M-1)^(N-1-k)

となります。

つまり、nCk(N-1,k) * M * (M-1)^(N-1-k)を求めれば良いですが、いずれも巨大になるため工夫してMODの計算をする必要が有ります。

前者はMODの逆元、後者はPythonのpow(a,b,MOD)により計算できます。

解答例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N,M,K = map(int,input().split())
MOD = 998244353
ans = 0

fact = [1] * (N+1) # 階乗を格納するリスト
factinv = [1] * (N+1) # 階乗を格納するリスト
for i in range(N):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
    factinv[i+1] = pow(fact[i+1], MOD-2, MOD)# MODを法とした逆元（フェルマーの小定理）

def nCk(n,k): # 組み合わせ(MOD)を返却する
    return fact[n] * factinv[n-k] * factinv[k] % MOD

def solve(k):
    r = M * pow(M-1,N-1-k,MOD) * nCk(N-1,k)
    return r

for k in range(K+1):
    ans += solve(k)
    ans %= MOD
print (ans)

失敗例

動的計画法による以下の実装はO(NK)となり間に合いませんが、参考として載せておきます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
N,M,K = map(int,input().split())
dp = [[0]*(K+2) for _ in range(2)] # 2行で十分
dp[0][0] = M
MOD = 998244353
for n in range(N-1):
    cur = n % 2
    next = (n+1) % 2
    dp[next] = [0]*(K+2) 
    for k in range(K+1):
        dp[next][k] += dp[cur][k] * (M-1)
        dp[next][k+1] += dp[cur][k]
        dp[next][k] %= MOD
        dp[next][k+1] %= MOD
print(sum(dp[(N+1)%2][:-1]))

関連記事

過去のABC解説記事です。

  • ABC166
    • A-F問題を解いています。
  • ABC165
    • A-F問題を解いています。
  • ABC164
    • A-E問題を解いています。
  • ABC163
    • A-D問題を解いています。
  • ABC162
    • A-E問題を解いています。

記事情報

  • 投稿日：2020年5月11日
  • 最終更新日：2020年5月11日