ABC216のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
よかったらLGTMや拡散していただけると喜びます！
目次
ABC216 まとめ
A問題『Signed Difficulty』
B問題『Same Name』
C問題『Many Balls』
D問題『Pair of Balls』
E問題『Amusement Park』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC216 まとめ
全提出人数: 7377人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 5分 | 5381(5135)位 |
| 400 | ABC----- | 600 | 58分 | 4412(4169)位 |
| 600 | ABC----- | 600 | 35分 | 3642(3399)位 |
| 800 | ABC----- | 600 | 19分 | 2859(2617)位 |
| 1000 | ABCD---- | 1000 | 83分 | 2154(1913)位 |
| 1200 | ABC-E--- | 1100 | 56分 | 1566(1329)位 |
| 1400 | ABCDE--- | 1500 | 77分 | 1112(879)位 |
| 1600 | ABCDEF-- | 2000 | 103分 | 767(548)位 |
| 1800 | ABCDEF-- | 2000 | 72分 | 527(316)位 |
| 2000 | ABCDEFG- | 2600 | 105分 | 336(167)位 |
| 2200 | ABCDEFG- | 2600 | 87分 | 217(82)位 |
| 2400 | ABCDEFG- | 2600 | 72分 | 147(38)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3267 | 92.1 % | 82.0 % | 53.0 % | 3.3 % | 2.7 % | 0.3 % | 0.1 % | 0.0 % |
| 茶 | 1291 | 98.9 % | 99.0 % | 92.3 % | 17.4 % | 14.6 % | 1.9 % | 0.3 % | 0.0 % |
| 緑 | 980 | 99.3 % | 99.3 % | 98.0 % | 50.3 % | 43.7 % | 6.1 % | 1.6 % | 0.0 % |
| 水 | 659 | 100.0 % | 99.7 % | 99.2 % | 82.2 % | 83.0 % | 40.4 % | 7.7 % | 0.0 % |
| 青 | 342 | 99.4 % | 99.4 % | 99.4 % | 96.8 % | 95.9 % | 84.5 % | 36.8 % | 0.3 % |
| 黄 | 175 | 95.4 % | 95.4 % | 96.0 % | 93.1 % | 96.0 % | 93.1 % | 68.6 % | 0.0 % |
| 橙 | 46 | 97.8 % | 97.8 % | 97.8 % | 93.5 % | 93.5 % | 100.0 % | 89.1 % | 2.2 % |
| 赤 | 25 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 28.0 % |
※表示レート、灰に初参加者は含めず
A問題『Signed Difficulty』
問題ページ：A - Signed Difficulty
灰コーダー正解率：92.1 %
茶コーダー正解率：98.9 %
緑コーダー正解率：99.3 %
入力
$X.Y$: 一つの正の実数（小数点のあるプラスの数字）
実装
split('.')を使って、整数部分 $X$ と小数部分 $Y$ を別に受け取って、if文で解きます。
コード
X, Y = map(int, input().split('.'))
ans = str(X)
if 0 <= Y <= 2:
ans += '-'
elif 7 <= Y <= 9:
ans += '+'
print(ans)
B問題『Same Name』
問題ページ：B - Same Name
灰コーダー正解率：82.0 %
茶コーダー正解率：99.0 %
緑コーダー正解率：99.3 %
入力
$N$: 人の数
$S_i$: $i$番目の人の姓
$T_i$: $i$番目の人の名
実装
setを使う方法
姓と名を別に受け取らずに、スペース入りの名前でそのまま受け取ります。これをset型に入れて、重複を省きます。
もし重複があれば、len(set) は $N$ より小さくなるので、"Yes"を出力します。len(set) が $N$ と等しいなら、重複がないので"No"を出力します。
二重ループで判定する方法
二重ループで問題文の通りに判定します。計算量は$O(N^2)$です。$N\le{1000}$ なので間に合います。
コード
setを使う方法
N = int(input())
S_set = set()
for _ in range(N):
S = input()
S_set.add(S)
print("Yes" if len(S_set) != N else "No")
二重ループで判定する方法
def solve():
for j in range(N):
for i in range(j):
if S[i] == S[j] and T[i] == T[j]:
return True
return False
N = int(input())
S = []
T = []
for _ in range(N):
s, t = input().split()
S.append(s)
T.append(t)
print("Yes" if solve() else "No")
C問題『Many Balls』
問題ページ：C - Many Balls
灰コーダー正解率：53.0 %
茶コーダー正解率：92.3 %
緑コーダー正解率：98.0 %
入力
$N$: 達成したいボールの数
考察
上の桁から決める方法
ボールの数を $2$ 進数表記にして考えます。たとえば、$5$ の $2$ 進数表記は $101$ です。$2$ 進数表記で操作を考えると、以下のようになります。
- 操作 $A$: 一番右の桁を $0$ から $1$ に変える
- 操作 $B$: 一番右に $0$ を付け加える
$N$ の $2$ 進数表記にして、上の桁から見ていきます。
- 操作 $B$ を行う
- $i$ 桁目が $1$ であれば、操作 $A$ を行う
$N$ は $N\le10^{18}$ です。$10^{18}\lt2^{60}$ なので、$N$ は $2$ 進数表記で最大 $60$ 桁になります。$1$ 桁ごとに操作 $B$ と操作 $A$ を両方行っても $120$ 回になるので、問題文の条件を満たします。
下の桁から決める方法
上の方法とほとんど同じですが、下の桁から決めていきます。
$rem=N$として、$rem=0$ になるまで以下の操作を繰り返します。
- $rem$ を $2$ で割った余りが $1$ なら 操作 $A$ を行い、$rem = rem -1$ とする
- $rem$ を $2$ で割った余りが $0$ なら 操作 $B$ を行い、$rem=rem/2$ とする
最後に、この方法は逆から考えているので、操作の文字列を反転して出力します。
コード
上の桁から決める方法
def main():
N = int(input())
b = format(N, 'b') # Nの2進数表記の文字列を得ます
ans = ""
for char in b:
ans += "B"
if char == "1":
ans += "A"
ans = ans[1:] # 先頭に余計なBがあるので、取り除きます（しなくてもACできます）
print(ans)
if __name__ == '__main__':
main()
下の桁から決める方法
def main():
N = int(input())
ans = ""
rem = N
while rem:
if rem % 2 == 1:
ans += "A"
rem -= 1
else:
ans += "B"
rem //= 2
print(ans[::-1])
if __name__ == '__main__':
main()
D問題『Pair of Balls』
問題ページ：D - Pair of Balls
灰コーダー正解率：3.3 %
茶コーダー正解率：17.4 %
緑コーダー正解率：50.3 %
入力
$N$: ボールの種類数
$M$: 筒の数
$k_i$: 筒 $i$ に入っているボールの数
$a_{i,j}$: 筒 $i$ の上から $j$ 番目のボールに書いてある数字
考察
有向グラフとみなし、閉路があるかないか判定する方法
グラフの問題とみまします。『あるボールの $1$ つ上のボールがなくなるまで、そのボールを取ることができない』という関係を、有向グラフ（向きのある辺のグラフ）で示します。
ある筒に上から $1,3,4,7$ という順でボールが置いてあるとすると、$1\rightarrow{3},\ 3\rightarrow{4},\ 4\rightarrow{7}$ の辺をグラフに追加します。
入次数が $0$ の頂点（他の頂点から矢印が入ってきていない頂点）は、ボールが $2$ つとも筒の一番上にあるので、取り除くことができます。頂点を取り除くとき、その頂点から出ている辺も一緒に取り除きます。
これを繰り返して、グラフが空にできるなら、すべての筒を空にする目的を達成することができます。
グラフを空にできる条件は、グラフに閉路がないことです。グラフに閉路がなければ、入次数が $0$ になった頂点から順に頂点を取り除いていけば、必ずグラフを空にできます。
反対に、グラフに閉路がある場合は、目標を達成できません。例えば、$1\rightarrow{2}\rightarrow{3}\rightarrow{4}\rightarrow{1}\rightarrow{2}\dots$ という閉路があるとします。ボール $4$ を取り出すには、ボール $3$ を取り出さないといけません。そのボール $3$ を取り出すにはボール $2$、ボール $2$ を取り出すにはボール$1$、ボール $1$ を取り出すにはボール $4$を取り出す必要がある……とループしてしまうので、結局閉路に含まれるボールを取り出すことはできません。
有向グラフの閉路検出は、トポロジカルソートをするとできます。詳細は省きますが、トポロジカルソートをすることができる場合、グラフは閉路を持ちません。逆にできなかった場合は、グラフは閉路を持ちます。
シミュレーションする方法
各ボールの数字ごとに、筒の一番上に何個あるかカウントしておきます。$2$ 個あれば取り除くことができるボールなので、キューに追加します。
キューから取り出したボールを筒から取り除き、新しく筒の一番上になったボールの数字のカウントを増やします。$2$ 個になれば、これもキューに追加します。
最後まで操作を完了できれば、筒をすべて空にすることができたことになります。
コード
有向グラフとみなし、閉路があるかないか判定する方法
def main():
def is_dag():
"""
トポロジカルソートを利用して、有向グラフに閉路がないかどうか調べる
（DAG, Directed Acyclic Graph, 有向非巡回グラフか調べる）
"""
L = [] # トポロジカルソートの結果が入るリスト（今回は不要）
S = deque([i for i in range(N) if cnt[i] == 0]) # 入次数が0の頂点を入れるdeque
while S:
u = S.popleft()
L.append(u)
for v in G[u]:
cnt[v] -= 1
if cnt[v] == 0:
S.append(v)
return all(x == 0 for x in cnt)
from collections import deque
N, M = map(int, input().split())
G = [[] for _ in range(N)] # 有向グラフを作ります
cnt = [0] * N # 入次数をカウントします
for _ in range(M):
k = int(input())
A = list(map(int, input().split()))
for i in range(k - 1):
prv = A[i] - 1
nxt = A[i + 1] - 1
G[prv].append(nxt)
cnt[nxt] += 1
if is_dag():
print('Yes')
else:
print('No')
if __name__ == '__main__':
main()
シミュレーションする方法
def main():
from collections import deque
def solve():
que = deque()
rem = N
cnt = [0] * N
for i in range(M):
front = T[i][-1]
cnt[front] += 1
if cnt[front] == 2:
que.append(front)
while que:
x = que.popleft()
rem -= 1
first, second = P[x]
T[first].pop()
T[second].pop()
if T[first]:
y = T[first][-1]
cnt[y] += 1
if cnt[y] == 2:
que.append(y)
if T[second]:
y = T[second][-1]
cnt[y] += 1
if cnt[y] == 2:
que.append(y)
return rem == 0
N, M = map(int, input().split())
T = []
P = [[] for _ in range(N)]
for i in range(M):
k = int(input())
a = list(x - 1 for x in map(int, input().split()))
for x in a:
P[x].append(i)
T.append(a[::-1])
print("Yes" if solve() else "No")
if __name__ == '__main__':
main()
E問題『Amusement Park』
問題ページ：E - Amusement Park
灰コーダー正解率：2.7 %
茶コーダー正解率：14.6 %
緑コーダー正解率：43.7 %
入力
$N$: アトラクションの個数
$K$: 高橋君がアトラクションに乗れる回数（$K$ 回より少ない回数乗っても良い）
$A_i$: $i$ 番目のアトラクションの「楽しさ」の初期値
考察
二分探索で解きます。
判定するのは「楽しさが $m$ 以上 の アトラクションにすべて乗ったとき、乗った回数の合計が $K$ 回以下になるか」です。
この $m$ がわかれば、
- 楽しさが $m$ 以上のアトラクション $A_i$ にすべてついて、$A_i - m + 1$ 回乗る（乗ったあと $A_i$ の楽しさは $m-1$になります）
- 余った回数はすべて楽しさ $m-1$ のアトラクションに乗る
コード
def main():
def judge(m):
cnt = 0
for x in A:
if x >= m:
cnt += x - m + 1
return cnt <= K
def solve(m):
rem = K
ans = 0
for i in range(N):
x = A[i]
if x >= m:
diff = x - m + 1
ans += diff * (x + m) // 2 # 等差数列の和の公式
rem -= diff
ans += rem * (m - 1)
return ans
N, K = map(int, input().split())
A = list(map(int, input().split()))
ok = 2 * 10 ** 9 + 5
ng = 0
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if judge(mid):
ok = mid
else:
ng = mid
print(solve(ok))
if __name__ == '__main__':
main()