AtCoder Beginner Contest 158のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
更新履歴
2021/3/1: 全体的に書き直しました
目次
ABC158 まとめ
A問題『Station and Bus』
B問題『Count Balls』
C問題『Tax Increase』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC158 まとめ
全提出人数: 7106人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 8分 | 5530(5363)位 |
| 400 | ABC--- | 600 | 64分 | 4583(4420)位 |
| 600 | ABC--- | 600 | 23分 | 3769(3609)位 |
| 800 | ABCD-- | 1000 | 91分 | 2912(2756)位 |
| 1000 | ABCD-- | 1000 | 59分 | 2123(1969)位 |
| 1200 | ABCD-- | 1000 | 40分 | 1480(1328)位 |
| 1400 | ABCD-- | 1000 | 28分 | 1006(855)位 |
| 1600 | ABCD-- | 1000 | 19分 | 664(522)位 |
| 1800 | ABCDE- | 1500 | 109分 | 422(296)位 |
| 2000 | ABCDE- | 1500 | 55分 | 273(155)位 |
| 2200 | ABCDEF | 2100 | 121分 | 171(75)位 |
| 2400 | ABCDEF | 2100 | 90分 | 101(34)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3130 | 97.5 % | 70.8 % | 62.1 % | 22.1 % | 0.2 % | 0.0 % |
| 茶 | 1215 | 99.2 % | 96.4 % | 93.7 % | 62.5 % | 0.5 % | 0.0 % |
| 緑 | 1073 | 99.7 % | 99.0 % | 98.7 % | 89.7 % | 2.6 % | 0.8 % |
| 水 | 532 | 99.8 % | 99.8 % | 99.4 % | 96.2 % | 19.2 % | 5.3 % |
| 青 | 308 | 99.7 % | 99.7 % | 99.7 % | 99.3 % | 43.5 % | 28.6 % |
| 黄 | 131 | 91.6 % | 90.8 % | 92.4 % | 93.1 % | 65.7 % | 61.8 % |
| 橙 | 35 | 97.1 % | 97.1 % | 97.1 % | 91.4 % | 91.4 % | 94.3 % |
| 赤 | 3 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 66.7 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (6954人AC)『Station and Bus』
- 文字列が全部同じ文字か判定します。
- B問題 (5837人AC)『Count Balls』
- 算数です。
- C問題 (5456人AC)『Tax Increase』
- 全探索です。
- D問題 (3533人AC)『String Formation』[この記事では解説しません]
- 実際に文字列を反転させる操作をすると、TLEになります。
dequeかリストを2つ使って、文字列の先頭と末尾に追加された文字を管理するといいです。
なお、PyPyは文字列の連結に+=演算子を使うと非常に遅いため、TLEになります。
dequeを使うか、リストを使って最後に"".join(A)で文字列にするといいです。 - E問題 (408人AC)『Divisible Substring』[この記事では解説しません]
- DPですが、$2$ と $5$ の場合だけ特別なので注意が必要です。
- F問題 (245人AC)『Removing Robots』[この記事では解説しません]
- セグメントツリーを使ってDPをすると解けます。
A問題『Station and Bus』
問題ページ：A - Station and Bus
灰コーダー正解率：97.5 %
茶コーダー正解率：99.2 %
緑コーダー正解率：99.7 %
問題の意味
"A" か "B"だけの3文字の文字列 $S$ があります。これはAtCoder市にある3つの駅の運営会社を表す文字列です。例えば"ABA"なら駅1・駅3をA社が、駅2をB社が運営しています。
違う運営会社の駅は路線が違うので、交通の便が悪いです。そこで、A社とB社の駅の間にバスを運行させることにしました。ただし、実際にバスが運行する駅の組み合わせがあるとは限りません。具体的には、市内の3つの駅がすべて同じ会社の駅の場合、バスが運行する駅の組はないことになります。バスが実際に運行するかどうかを判定してください。
考察
コンテスト中に上のレベルまで想像力を働かせる必要はないですが、具体的な状況を想像したり書いたりすると理解の助けになることがあります。
"ABA" "ABB"のように $S$ に"A"と"B"の2種類が存在するなら"Yes"です。$S$ が1種類の文字だけのとき、つまり"AAA"か"BBB"なら"No"です。
コード
S = input()
if S == "AAA" or S == "BBB":
# 全部同じならNoです 逆にしないよう注意
print("No")
else:
print("Yes")
len(set(S))を使って、文字の種類数を判定してもいいです。
S = input()
if len(set(S)) == 1:
# Sに含まれる文字の種類が1種類か判定してもいいです
print("No")
else:
print("Yes")
B問題『Count Balls』
問題ページ：B - Count Balls
灰コーダー正解率：70.8 %
茶コーダー正解率：96.4 %
緑コーダー正解率：99.0 %
問題の意味
※$A$ 個、$B$ 個はわかりづらいので、 $Blue$ 個と $Red$ 個に変更します。
青いボール $Blue$ 個と赤いボール $Red$ 個 を交互に並べる作業を無限に行って、無限に長いボールの列を作ります。（元の問題文では $10^{100}$ 回ですが、無限とみなしていいです）
$1$ 以上 $10^{18}$ 以下の範囲で $N$ を指定します。ボールの列の先頭から $N$ 個のうち、青いボールはいくつでしょうか。
考察
whileループで操作をシミュレートすれば、$N$ が小さい場合の答えは求まられます。しかし、この問題は $N$ が最大で $10^{18}$ にもなります。コンピュータでも計算に数年～数十年かかるので、別の方法で求める必要があります。
『整数の割り算』（小学校でやった余りの出る割り算）を使って、数式を使って一発で求めることを考えてみます。
わかりやすくするために、問題文と操作を少し言い換えてみます。
新しい問題文
『青いボール $Blue$ 個と赤いボール $Red$ 個が入った筒』を $1$ 本ずつ列に加える操作を考えます。ただし、筒のまま加えると列のボールが $N$個 を超えてしまう場合は、筒からボールを1個ずつ取り出して列に加えることにします。このとき、青いボールが先に筒から出てきます。
ボールの色を忘れてみる
一旦ボールの色のことは忘れて、『ボール $(Blue + Red)$ 個入りの筒の本数 $Q$ 本』と『バラのボールの個数 $R$ 個』を求めてみます。これがわかれば、青いボールの個数は簡単に計算できます。
『筒の本数 $Q$ 本』と『バラのボールの数 $R$ 個』は、『ボールの総数 $N$ 個』を「筒1本あたりのボールの数 $(Blue + Red)$ 個」 で割ると求められます。
{N} \div {(Blue + Red)} = Q\.あまり\.R
求めたい『青いボールの総数』は『筒の中にある青いボールの総数』と『バラの青いボールの数』を足した数です。
1. 筒の中の青いボールの総数
筒1本の中には青いボールが $Blue$ 個入っています。よって、 $Q$ 本の筒に入った青いボールは $Blue \times Q$ 個です。
2. バラの青いボールの数
筒は $1$ 本だけ開けるので、 $R$ 個のバラのボールのうち青いボールは最大でも $Blue$個 です。赤いボールよりも青いボールを先に取り出すので、基本的には $R$個 ですが、下の画像のように $R$ が $Blue$ 個 を超えるなら $Blue$ 個です。
言い換えると、 $R$ 個と $Blue$ 個の小さい方、$min(Blue, R)$ 個です。
答え
1.と2. を足して、求める『青いボールの総数』は
$Blue\times{Q} + min(Blue, R)$ 個
になります。
コード
N, blue, red = map(int, input().split())
T = blue + red
# n / (blue + red) = q ... r
q, r = N // T, N % T
ans = blue * q + min(blue, r)
print(ans)
商と余りを求める部分は、以下のようにdivmod(N, T)と書くとより簡潔です。
python
q, r = divmod(N, T)
C問題『Tax Increase』
問題ページ：C - Tax Increase
灰コーダー正解率：62.1 %
茶コーダー正解率：93.7 %
緑コーダー正解率：98.7 %
考察
消費税の上限が $100$ 円と小さいです。税抜き価格を $1$ 円から順に、消費税率 $8\%$ と $10\%$ でそれぞれ税込み価格がいくらになるか実際に計算して、$A$ 円 $B$ 円と一致するものを探します。
税抜き価格をいくらまで探せばよいか考えます。消費税率 $10\%$ で 消費税が $101$ 円になるのは税抜き $1010$ 円ですから、$1009$ 円まで調べればいいです。
実際には余計に調べても不正解にはなりませんから、上限の $1009$ 円をぴったり求める必要はないです。正確に求めるのは面倒なうえミスの原因になるので、適当に $1$ 万円くらいまで調べると楽で安全です。
実装
消費税を求めるとき、次のように小数をかけて切り捨てをしても、この問題は正解できます。
tax_a = int(price * 0.08)
tax_b = int(price * 0.1)
ただし浮動小数点数の計算は、扱う数字が大きい場合などに誤差が生じて正しい答えが出ない場合があります。ですので、使う必要がない場合はできるだけ整数だけで計算することを心がけるといいです。
この問題では、次のようにすればいいです。
tax_a = price * 8 // 100
tax_b = price * 10 // 100
コード
a, b = list(map(int, input().split()))
ans = -1 # 答えが見つからなかった場合の-1を初期値にしておく
# 0円から9999円まで1円ずつ増やして調べる
for price in range(10000):
# 消費税を8%と10%それぞれ計算します。0.08倍, 0.1倍して切り捨ててもACできますが
# 浮動小数点数は誤差の問題があるので、できるだけ使わないほうがいいです
tax_a = price * 8 // 100
tax_b = price * 10 // 100
# 条件を満たしたら答えに代入してループから抜ける
if tax_a == a and tax_b == b:
ans = price
break
# 答えが見つかったらそのときの値、見つからなかったら初期値の-1が表示される
print(ans)