競技プログラミング

ABC164

はじめに

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

A - Sheep and Wolves

https://atcoder.jp/contests/abc164/tasks/abc164_a

S = Wの場合を処理し間違えないようにしましょう。

1
2
3
4
5
S, W = map(int,input().split())
if S <= W:
    print ('unsafe')
else:
    print ('safe')

B - Battle

https://atcoder.jp/contests/abc164/tasks/abc164_b

除算をしても良いし、数が小さいのでシミュレーションをしても良いです。

1
2
3
4
5
6
7
8
9
10
a,b,c,d = map(int,input().split())
while(1):
    c -= b
    if (c<=0):
        print ('Yes')
        break
    a -= d
    if (a<=0):
        print ('No')
        break

C - gacha

https://atcoder.jp/contests/abc164/tasks/abc164_c

Pythonの場合setを使うと楽です。

1
2
3
4
5
N = int(input())
ls = []
for n in range(N):
    ls.append(input())
print (len(set(ls)))

D - Multiple of 2019

https://atcoder.jp/contests/abc164/tasks/abc164_d

動的計画法を用いて解くことができます。

解法1

2019で割った余りがxである文字列が何通りかをサイズ2019のリストに記録していきます。

具体例として、2019の倍数である18171が入力となった場合について考えます。

リストcntは以下のように遷移します。（値が0の要素は省略）

1
2
3
4
5
6
7
8
9
10
# 1文字目の入力
cnt[1] = 1
# 2文字目の入力
cnt[18] = 1, cnt[8] = 1
# 3文字目の入力
cnt[181] = 1, cnt[81] = 1, cnt[1] = 1
# 4文字目の入力
cnt[1817] = 1, cnt[817] = 1, cnt [17] = 1, cnt[7] = 1
# 5文字目の入力
cnt[0] = 1, cnt[8171] = 1, cnt[171] = 1, cnt[71] = 1, cnt[1] = 1

cnt[0]に0以外の値が入るごとに、その値をansに足していけば良いです。

Pythonだと計算量がギリギリなので、PyPy3を使いました。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
N = 2019
cnt = [0] * N
S = input()
ans = 0
for s in S:
    s = int(s)
    new = [0] * N
    for n in range(N):
        idx = (10 * n + s) % N
        new[idx] += cnt[n]
    cnt = new
    cnt[s] += 1
    ans += cnt[0]
print (ans)

解法2

公式の解説にしたがって解きました。

右端を含む文字列集合と文字列0の和集合を考えます。
例えば入力が12345であった場合、以下のような集合です。
集合A

1
{12345, 2345, 345, 45, 5, 0}

この集合からL > Rとなるように二つの数を選び、L-Rを適切に10^nで割ってあげること（シフトするイメージ）で、Sの部分文字列を列挙考えることができます。

1
2
2345 - 45 = 2300
2300 / 100 = 23

ところで2019と10は互いに素なので、2019を法として、

1
2
3
     L/(10^n) - R/(10^n) ≡ 0
<=>                L - R ≡ 0
<=>                    L ≡ R

が成り立ちます。そのため、2019を法とした時に同じ値になる数を数え上げ、ペアの作り方をシグマ計算すれば良いです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
S = input()
MOD = 2019
cnt = [0]*MOD
cur = 0 # 現在考えている部分文字列
cnt[cur] = 1 # 部分文字列'0'も作れたと考える
d = 1 # 位を表す
for s in S[::-1]: # 右から作る
    cur += int(s)*d # 新たな桁を追加
    cur %= MOD
    cnt[cur] += 1
    # 後処理
    d *= 10 # 位を上げる
    d %= MOD # ただし数が巨大になるため、計算量を減らすために剰余をとる
ans = 0
for c in cnt:
    ans += c*(c-1)//2
print (ans)

E - Two Currencies

https://atcoder.jp/contests/abc164/tasks/abc164_e

A,Nの最大値は50なので、銀貨は2500枚あれば十分です。つまり、(現在の頂点, 所持している銀貨の枚数)の状態数は最大で50*2500なので、ダイクストラ法を用いて解くことができます。

公式の解説にしたがって、状態(現在の頂点, 所持している銀貨の枚数)を要素数2のリストで表現しています。これらの組み合わせを考えて要素数1のリストを考えることもできますが、前者の方が実装が楽だと思います。

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import heapq
INF = 10**20

N, M, S = map(int, input().split())
adj = [[] for _ in range(N)]
for m in range(M):
    u,v,a,b = map(int, input().split())
    u -= 1
    v -= 1
    adj[u].append((v,a,b))
    adj[v].append((u,a,b))

C = []
D = []
for n in range(N):
    c, d = map(int, input().split())
    C.append(c)
    D.append(d)

M = 2500
S = min(S, M-1) # 2500枚あれば十分
dist = [[INF]*M for _ in range(N)] # dist[都市][銀貨の枚数]
dist[0][S] = 0
pq = [(0,S,0)] # (時間、銀貨の枚数、都市)

while pq:
    d, sil, node = heapq.heappop(pq)
    if dist[node][sil] < d: # 探索の対象にする必要があるか確認
        continue 
     # 銀貨に交換したとして、上限を超えないか、探索の必要があるか
    if sil+C[node] < M and d+D[node] < dist[node][sil+C[node]]:
        dist[node][sil+C[node]] = d + D[node] # 時間の更新
        heapq.heappush(pq, (d + D[node], sil+C[node] ,node))
    for next, a, b in adj[node]:
        # 銀貨が足りるか、探索の必要があるか
        if sil >= a and d + b < dist[next][sil-a]:
            dist[next][sil-a] = d + b
            heapq.heappush(pq, (d + b, sil-a ,next))

for i in range(1,N):
    print(min(dist[i])) # 残っている銀貨の枚数は問わない

関連記事

過去のABC解説記事です。

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

記事情報

  • 投稿日：2020年4月26日
  • 最終更新日：2020年4月27日