AtCoder Beginner Contest 190のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター までどうぞ！
Twitter: u2dayo
目次
ABC190 まとめ
A問題『Very Very Primitive Game』
B問題『Magic 3』
C問題『Bowls and Dishes』
ABC190 まとめ
全提出人数: 9310人
下の表のデータを見られるアプリ AtCoder Facts を作りました。使ってくれたらよろこびます。
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 27分 | 7098(6871)位 |
| 400 | AB---- | 300 | 13分 | 5868(5641)位 |
| 600 | ABC--- | 600 | 73分 | 4826(4600)位 |
| 800 | ABC--- | 600 | 14分 | 3738(3516)位 |
| 1000 | ABCD-- | 1000 | 82分 | 2732(2514)位 |
| 1200 | ABCD-- | 1000 | 44分 | 1922(1706)位 |
| 1400 | ABCD-F | 1600 | 99分 | 1315(1104)位 |
| 1600 | ABCD-F | 1600 | 61分 | 881(675)位 |
| 1800 | ABCDEF | 2100 | 94分 | 583(383)位 |
| 2000 | ABCDEF | 2100 | 73分 | 377(197)位 |
| 2200 | ABCDEF | 2100 | 56分 | 233(94)位 |
| 2400 | ABCDEF | 2100 | 47分 | 145(42)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 4018 | 94.8 % | 91.2 % | 20.6 % | 13.6 % | 0.3 % | 1.4 % |
| 茶 | 1591 | 98.9 % | 98.7 % | 72.2 % | 45.5 % | 0.6 % | 5.6 % |
| 緑 | 1299 | 99.3 % | 99.2 % | 94.4 % | 76.1 % | 4.4 % | 23.2 % |
| 水 | 733 | 99.6 % | 99.6 % | 98.6 % | 88.0 % | 29.5 % | 61.5 % |
| 青 | 393 | 99.5 % | 99.5 % | 99.2 % | 95.9 % | 77.3 % | 91.1 % |
| 黄 | 171 | 95.9 % | 95.3 % | 95.3 % | 95.3 % | 90.1 % | 95.9 % |
| 橙 | 41 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % |
| 赤 | 15 | 93.3 % | 93.3 % | 93.3 % | 100.0 % | 93.3 % | 100.0 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (8916人AC)『Very Very Primitive Game』
- A問題とは思えないほどめんどくさいです。
条件文を考えてもいいですが、何も考えずにシミュレートしたほうが楽かもしれません。 - B問題 (8636人AC)『Magic 3』
- A問題より簡単だと思います。
『詠唱が $S$ 秒より短い』かつ『ダメージが $D$ より大きい』ならダメージが通ります。 - C問題 (4698人AC)『Bowls and Dishes』
- 『bit全探索』です。
- D問題 (3619人AC)『Staircase Sequences』[この記事では解説しません]
- がんばって数式をこねこねすると、$2N$ の約数を列挙して判定すればいいことがわかります。
- E問題 (821人AC)『Magical Ornament』[この記事では解説しません]
- この問題はグラフ問題です。
まず、$K$ 個の魔法石 $C_i$ 間の最短距離を幅優先探索（BFS）で求めます。
その後、巡回セールスマン問題と同じ要領でbitDPをすればいいです。
（巡回セールスマン問題とは違い、始点に戻る必要はありません） - F問題 (1510人AC)『Shift and Inversions』[この記事では解説しません]
- 転倒数の求め方さえ知っていれば、少しの考察で解けると思います。
- 条件を考える
- シミュレートする
私（うにだよ）の結果
Dが一番苦労しました。個人的にはD>E>>F>C>>B>Aという感想でした。
A問題『Very Very Primitive Game』
問題ページ：A - Very Very Primitive Game
灰コーダー正解率：94.8 %
茶コーダー正解率：98.9 %
緑コーダー正解率：99.3 %
考察
一旦先手・後手を忘れて、『高橋くんと青木くんが同時に飴を食べるルール』に変更して考えてみます。
飴の数が違う場合、飴の数が多い人が勝ちます。先手・後手のルールを追加しても勝敗は変わりません。
飴の数が同じ場合は引き分けになります。先手・後手のルールを追加すると、先手のほうが先に飴がなくなるので、後手の勝ち（先手の負け）です。
実装
めんどくさいので、シミュレートしたほうが楽かもしれません。
コード
条件式を書くコードです。
A, B, C = map(int, input().split())
if C == 0:
# 高橋くんが先手の場合
if A > B:
print("Takahashi")
else:
print("Aoki")
else:
if A >= B:
# 青木くんが先手の場合
print("Takahashi")
else:
print("Aoki")
シミュレートするコードです。
def solve():
A, B, C = map(int, input().split())
if C == 0:
# 高橋くんが先手の場合
while True:
if A == 0:
return False
A -= 1
if B == 0:
return True
B -= 1
else:
# 青木くんが先手の場合
while True:
if B == 0:
return True
B -= 1
if A == 0:
return False
A -= 1
print("Takahashi" if solve() else "Aoki")
B問題『Magic 3』
問題ページ：B - Magic 3
灰コーダー正解率：91.2 %
茶コーダー正解率：98.7 %
緑コーダー正解率：99.2 %
考察
『詠唱が $S$ 秒より短い』かつ『ダメージが $D$ より大きい』ならダメージが通ります。
これをそのままコードにすればいいです。
コード
def solve():
for _ in range(N):
s, d = map(int, input().split())
if s < S and d > D:
# 条件は『詠唱がS秒より短い』かつ『ダメージがDより大きい』です
return True
# ダメージが通る呪文がなかったです
return False
N, S, D = map(int, input().split())
print("Yes" if solve() else "No")
C問題『Bowls and Dishes』
問題ページ：C - Bowls and Dishes
灰コーダー正解率：20.6 %
茶コーダー正解率：72.2 %
緑コーダー正解率：94.4 %
考察
制約の人の数は $K\le{16}$ です。それぞれの人が $A_i$ か $B_i$ のどちらか片方にボールを置きます。よって、ボールの置き方は最大で $2^{16}=65536$ 通りしかありません。よって、全部の置き方を 『bit全探索』 で試すことができます。
それぞれの置き方についてどの皿にいくつボールが置かれるか数えて、いくつ条件を満たすか判定します。最大値を出力すればいいです。
実装
itertoolsモジュールのproductを使うと、簡単にbit全探索を書けます。今回は下のように書けばいいです。
for bit in product((0, 1), repeat=K):
コード
def solve():
from itertools import product
ans = 0
# 2^K通りの置き方をbit全探索します
# productで0か1をK個並べてできる数列を全列挙します
# ループで (0,0,0), (0,0,1), (0,1,0),(0,1,1)...
# の要素を1つずつ取りして使います
for bit in product((0, 1), repeat=K):
cnt = [0] * (N + 1) # 各皿のボールの数をカウントします
for i in range(K):
# i番目の人がA_i, B_iのどちらか片方にボールを置きます
# bit[i] == 0ならA_i、bit[i]==1ならばB_iを選びます
ball = people[i][bit[i]]
cnt[ball] += 1
score = 0
for i in range(M):
c, d = conditions[i]
if cnt[c] > 0 and cnt[d] > 0:
# 条件は皿C, 皿Dの両方にボールが1個以上置かれていることです
score += 1
ans = max(ans, score) # 最大値を更新します
return ans
N, M = map(int, input().split())
conditions = []
for _ in range(M):
a, b = map(int, input().split())
conditions.append((a, b))
people = []
K = int(input())
for _ in range(K):
c, d = map(int, input().split())
people.append((c, d))
print(solve())