【AtCoder解説】PythonでABC189のA,B,C問題を制する！

AtCoder Beginner Contest 189のA,B,C問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

• シンプル：余計なことを考えずに済む
• 実装が楽：ミスやバグが減ってうれしい
• 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo

目次

ABC189 まとめ
A問題『Slot』
B問題『Alcoholic』
C問題『Mandarin Orange』

ABC189 まとめ

全提出人数: 8938人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	A-----	100	3分	6862(6663)位
400	AB----	300	86分	5705(5506)位
600	AB----	300	7分	4709(4512)位
800	ABC---	600	69分	3652(3458)位
1000	ABCD--	1000	119分	2665(2477)位
1200	ABCD--	1000	65分	1866(1684)位
1400	ABCD--	1000	36分	1276(1096)位
1600	ABCDE-	1500	101分	845(676)位
1800	ABCDE-	1500	72分	547(389)位
2000	ABCDE-	1500	53分	349(206)位
2200	ABCD-F	1600	64分	213(100)位
2400	ABCDEF	2100	82分	129(46)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3675	97.1 %	40.6 %	24.5 %	8.9 %	0.5 %	0.1 %
茶	1512	99.6 %	78.7 %	59.3 %	39.8 %	2.3 %	0.0 %
緑	1227	99.9 %	92.6 %	78.1 %	78.8 %	12.1 %	0.7 %
水	720	99.9 %	97.6 %	85.8 %	95.7 %	44.0 %	4.2 %
青	385	100.0 %	99.0 %	95.3 %	99.0 %	76.9 %	20.3 %
黄	154	94.2 %	92.2 %	90.9 %	92.2 %	83.8 %	52.0 %
橙	33	100.0 %	100.0 %	93.9 %	97.0 %	87.9 %	75.8 %
赤	15	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %

※表示レート、灰に初参加者は含めず

簡易解説

A問題 (8747人AC)『Slot』

$3$ 文字とも同じか判定します。

B問題 (5436人AC)『Alcoholic』

お酒を順番に飲んでいって、酔っ払ったとき何杯目を飲んでいたか求めればいいです。
ただし、小数のある数を使うと、誤差でWAになります。式変形をして整数だけで求められるようにしましょう。

C問題 (4158人AC)『Mandarin Orange』

すべての区間について、二重ループで食べられるみかんの数を全探索します。
ただし、制約が厳しいので低速なPythonでは全探索のコードがTLEになります。PyPyを使ってください。
Pythonでも通る $O(N)$ 解法もありますが、難しいです。

D問題 (3270人AC)『Logical Expression』[この記事では解説しません]

前から順番に見ていきます。
$OR$ なら $1$ 個前で $True$ か、前はなんでもよくて今 $True$ のとき $True$ です。
$AND$ なら $1$ 個前で $True$ かつ 今も $True$ です。

E問題 (1008人AC)『Rotate and Flip』[この記事では解説しません]

行列を使って座標を変換をします。
アフィン変換というものらしいです。
わざわざ行列を使わなくてもできます。

F問題 (244人AC)『Sugoroku2』[この記事では解説しません]

確率DPです。振り出しに戻るマスに止まったときの期待値は、$0$ マス目の期待値と等しいですが、求めたいものと循環してしまいうまくいきません。
スタート地点の期待値を $x$ とおきます。$1$ 次式 $Ax + B$ の $2$ 配列を使ったDPをして、最後に $x$ について式を解けば求められます。

私（うにだよ）の結果

Eの解き方はすぐわかりましたが、行列を掛ける向きや符号を間違え続けてハマりました。

A問題『Slot』

問題ページ：A - Slot
灰コーダー正解率：97.1 %
茶コーダー正解率：99.6 %
緑コーダー正解率：99.9 %

実装

C = input()と書き、文字列（str型）として受け取ります。そして、if C[0] == C[1] == C[2] と書き、$3$ 文字とも同じであるか判定すればいいです。

出力が'Won'と'Lostであることに注意してください。いつもと違う出力が求められている場合は、見間違いやタイプミスを防ぐために、問題文からコピペすると確実です。

コード

C = input()

if C[0] == C[1] == C[2]:
    print('Won')
else:
    print('Lost')

この問題で使う必要はありませんが、種類数を求めたいときはlen(set(C))と書くとできます。よく使うので、覚えておくと役に立ちます。

C = input()

if len(set(C)) == 1:
    print('Won')
else:
    print('Lost')

B問題『Alcoholic』

問題ページ：B - Alcoholic
灰コーダー正解率：40.6 %
茶コーダー正解率：78.7 %
緑コーダー正解率：92.6 %

考察

問題文と必要な知識を整理します。

- 高橋君が酔っ払うのは、アルコールの摂取量が $X$ mlを『超えた』とき
- $V$ ml のアルコール度数 $P$ % のお酒に含まれるアルコールは $\frac{VP}{100}$ ml

あるお酒を飲み終えた時点のアルコール摂取量の合計を $S$ とします。$X\lt{S}$ であれば酔っぱらいです。$X\le{S}$ ではないことに注意してください。

素直にアルコールの量を計算すると、S += V * P / 100と書くことになりますが、これはWAになります。コンピュータが小数点のある数を扱うとき、通常は浮動小数点数という形式を使います。この形式は完全に正確には数を表すことができず、誤差が出てしまいます。

そこで、誤差が出ない整数型（int型）だけで計算をできるように式を変形します。

$S = \frac{V_1{P_1}}{100} + ... + \frac{V_i{P_i}}{100} > X$ という判定式から、左辺の $100$ で割っているところをなくせばいいです。そのために、両辺に $100$ を掛けます。すると、$V_1{P_1} + ... + V_i{P_i} > 100X$ になります。これをコードにすればACできます。

コード

def solve():
    S = 0
    for i in range(1, N + 1):
        V, P = map(int, input().split())
        S += V * P  # 100で割りたくないので、そのままにします
        if S > 100 * X:  # ここでXを100倍します
            return i
    return -1


N, X = map(int, input().split())

print(solve())

C問題『Mandarin Orange』

問題ページ：C - Mandarin Orange
灰コーダー正解率：24.5 %
茶コーダー正解率：59.3 %
緑コーダー正解率：78.1 %

考察

実行時間と言語について

この問題はすべての$l, r$の組を全探索する $O(N^2)$ のコードでACできますが、制限時間（$1.5$ 秒）と制約（$N = 10^4$）が厳しいです。

$l,r$ の組は $\frac{N\times{(N + 1)}}{2}$ 組あるので、$N = 10^4$ だと 約 $5000$ 万組になります。低速な言語でない限り、簡単な処理であれば、$5000$ 万回の処理をしても余裕を持ってACできます。残念ながら、Pythonは低速な言語なので通りません。PyPyを使うと通ります。

Pythonでも通る $O(N)$ の解法も存在しますが、難しいのでここでは扱いません。（蟻本298ページのスタックを使う解法や、UnionFindで大きい順に見て、隣が自分以上ならUnionする解法があります。コメントでいただいた@c-yan さんのこちらの記事が参考になると思います）

問題の考察

問題文が少しむずかしいですが、このようなことを言っています。

• 連続する区間 $[l, r]$ を好きに選ぶ（ $1 ～ 3, 2 ～ 2$ など ）
• 選んだ区間のすべての皿から、$x$ 個ちょうどずつみかんを食べる（必ず$x$ 個ちょうどで、足りなくなるような $x$ は選べない）
• 食べられるみかんの最大値を求めよ

さきほど書いた通り、すべての $l, r$ の組について食べられるみかんの数を二重ループで全探索して最大値を求めることを考えます。

$l,r$ を決めたとき、食べるみかんの数 $x$ は『選んだ区間内でみかんが最小の皿と同じ』にすると最大まで食べられます。これ以上はみかんが足りなくなるのでできません。

このとき、食べられるみかんの数は $(区間の長さ)\times{(区間内の最小値)}$ です。区間の長さは $r - l + 1$ です。最小値の求め方は次の実装の項で考えます。

実装

区間の最小値を求めるために min(A[l : r + 1]) を使った次のようなコードが思いつきますが、これではTLEになります。

for l in range(N):
    for r in range(l, N):
        d = r - l + 1  # 区間の幅
        m = min(A[l : r + 1])  # 区間の最小
        score = m * d  # 食べたみかんの数
        ans = max(ans, score)

min関数は与えたリストの要素すべてを線形探索（全部確認する）します。これには長さに比例した計算量がかかりますから、全体で $O(N^3)$ になってしまいます。

ここで『 $l$ から $r$ の最小値』は『 $l$ から $r - 1$ の最小値と $r$ の小さい方』ということを利用します。 $l$ を固定して $r$ を $1$ ずつ増やしていけば、直前に求めた『 $l$ から $r - 1$ の最小値』を使い回すことができます。

これで最小値の更新が $O(1)$ になり、全体で $O(N^2)$ となってACできます。

コード

このコードをPyPyで提出すると $250$ msで通ります。C++の $50$ msと比べると遅いですが、制限時間は $1500$ msなので問題ありません。

N = int(input())
A = [*map(int, input().split())]

ans = 0
for l in range(N):
    m = 10 ** 6  # 適当な10 ** 5より大きい数で初期化します
    for r in range(l, N):
        d = r - l + 1  # 区間の幅
        m = min(m, A[r])  # 区間の最小を更新
        score = m * d  # 食べたみかん
        ans = max(ans, score)

print(ans)