AtCoder Beginner Contest 164のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
よかったらLGTMしていただけると、私のやる気がでます！
更新履歴
2021/03/02: 全部書き直しました
目次
ABC164 まとめ
A問題『Sheep and Wolves』
B問題『Battle』
C問題『gacha』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC164 まとめ
全提出人数: 11297人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | ABC--- | 600 | 70分 | 8727(8554)位 |
| 400 | ABC--- | 600 | 29分 | 7198(7026)位 |
| 600 | ABC--- | 600 | 18分 | 5852(5682)位 |
| 800 | ABC--- | 600 | 12分 | 4422(4252)位 |
| 1000 | ABC--- | 600 | 8分 | 3103(2934)位 |
| 1200 | ABC--- | 600 | 5分 | 2081(1912)位 |
| 1400 | ABCD-- | 1000 | 53分 | 1350(1189)位 |
| 1600 | ABCD-- | 1000 | 25分 | 852(704)位 |
| 1800 | ABCD-- | 1000 | 11分 | 533(392)位 |
| 2000 | ABCDE- | 1500 | 73分 | 324(203)位 |
| 2200 | ABCDE- | 1500 | 54分 | 195(98)位 |
| 2400 | ABCDE- | 1500 | 40分 | 116(46)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 4938 | 99.0 % | 90.7 % | 79.7 % | 2.4 % | 0.1 % | 0.0 % |
| 茶 | 1828 | 99.6 % | 98.7 % | 98.4 % | 13.2 % | 0.5 % | 0.0 % |
| 緑 | 1357 | 99.6 % | 99.3 % | 99.6 % | 34.5 % | 2.1 % | 0.0 % |
| 水 | 733 | 99.9 % | 99.5 % | 99.7 % | 73.7 % | 12.7 % | 0.6 % |
| 青 | 345 | 99.7 % | 99.7 % | 99.7 % | 92.8 % | 58.0 % | 2.9 % |
| 黄 | 151 | 90.7 % | 90.7 % | 91.4 % | 89.4 % | 70.9 % | 8.0 % |
| 橙 | 33 | 93.9 % | 87.9 % | 90.9 % | 93.9 % | 84.8 % | 39.4 % |
| 赤 | 3 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 66.7 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (11148人AC)『Sheep and Wolves』
- 書いてあるとおりに判定しましょう。
- B問題 (10415人AC)『Battle』
- シミュレートすれば解けます。算数をしてもいいです。
- C問題 (9553人AC)『gacha』
-
set型を使えば一発です。 - D問題 (1926人AC)『Multiple of 2019』[この記事では解説しません]
- DPです。
- E問題 (497人AC)『Two Currencies』[この記事では解説しません]
- 『今持っている銀貨の数』という状態を頂点にもたせて、ダイクストラ法をすればいいです。
- F問題 (41人AC)『I hate Matrix Construction』[この記事では解説しません]
- よくわからなかったので、公式解説でも見てください。
'unsafe'と'safe'を逆にする- ちょうど $W = S$ の場合の判定を間違える
- 出力をタイプミスする
A問題『Sheep and Wolves』
問題ページ：A - Sheep and Wolves
灰コーダー正解率：99.0 %
茶コーダー正解率：99.6 %
緑コーダー正解率：99.6 %
考察
問題文に書いてあるとおりに判定しましょう。次のようなミスをしないように気をつけてください。
コード
S, W = map(int, input().split())
if W >= S:
print("unsafe")
else:
print("safe")
B問題『Battle』
問題ページ：B - Battle
灰コーダー正解率：90.7 %
茶コーダー正解率：98.7 %
緑コーダー正解率：99.3 %
実装
解法1: シミュレート
制約が小さいので、whileループで実際に戦闘をシミュレートすれば解けます。
変数名を問題文のまま $A, B, C, D$ にすると、どれが何を表しているかわかりづらいです。適当に、先攻の体力、攻撃力を f_hp, f_atk、後攻の体力、攻撃力をs_hp, s_atk とでもしておきます。
解法2: 算数
算数で両者が生き残るターン数を求めて、長く生き残るほうが勝ちとしてもいいです。同じターンなら、先に攻撃して相手を倒せる、先攻の勝ちです。
生き残るターン数は、$\frac{(自分の体力)}{(相手の攻撃力)}$ の小数点以下を切り上げた数です。
コード
シミュレートするコードです。
def judge():
f_hp, f_atk, s_hp, s_atk = map(int, input().split())
while True:
s_hp -= f_atk
if s_hp <= 0:
return True
f_hp -= s_atk
if f_hp <= 0:
return False
if judge():
print("Yes")
else:
print("No")
算数で求めるコードです。
f_hp, f_atk, s_hp, s_atk = map(int, input().split())
ft = (f_hp + s_atk - 1) // s_atk # 先攻の生き残るターン（詳細は省きますが、この式でf_hpをs_atkで割って切り上げた値を求められます）
st = (s_hp + f_atk - 1) // f_atk # 後攻の生き残るターン
if ft >= st:
# 同じターンなら先攻の勝ちです
print("Yes")
else:
print("No")
C問題『gacha』
問題ページ：C - gacha
灰コーダー正解率：79.7 %
茶コーダー正解率：98.4 %
緑コーダー正解率：99.6 %
実装
種類数を求めたいときは、set型を使うといいです。set型は、重複する要素を含まないように管理してくれるコレクション（複数の要素を持つデータ型）です。
set型に入力を全部追加して、要素数をlen()で求めれば、簡単に種類数を求めることができます。
コード
N = int(input())
S_set = set()
for _ in range(N):
S = input()
S_set.add(S) # setに要素を追加するときはaddです
print(len(S_set))