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

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

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

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

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

よかったらLGTMしていただけると、私のやる気がでます！

目次

ABC194 まとめ
A問題『I Scream』
B問題『Job Assignment』
C問題『Squared Error』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC194 まとめ

全提出人数: 7892人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	68分	5952(5739)位
400	AB----	300	22分	4899(4686)位
600	ABC---	600	80分	4038(3825)位
800	ABC---	600	40分	3160(2947)位
1000	ABCD--	1000	84分	2347(2139)位
1200	ABC-E-	1100	78分	1679(1477)位
1400	ABCDE-	1500	93分	1171(974)位
1600	ABCDE-	1500	64分	798(609)位
1800	ABCDE-	1500	45分	524(354)位
2000	ABCDE-	1500	34分	338(189)位
2200	ABCDE-	1500	16分	214(93)位
2400	ABCDEF	2100	85分	135(43)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3401	95.1 %	64.8 %	27.6 %	3.9 %	2.9 %	0.1 %
茶	1435	98.9 %	96.0 %	75.8 %	17.8 %	15.1 %	0.3 %
緑	1174	99.1 %	99.1 %	94.0 %	42.6 %	43.4 %	0.7 %
水	680	99.7 %	99.6 %	98.7 %	77.5 %	81.8 %	2.9 %
青	388	99.7 %	99.5 %	99.7 %	93.8 %	96.1 %	13.7 %
黄	168	97.0 %	97.0 %	97.6 %	94.6 %	93.5 %	47.0 %
橙	36	100.0 %	100.0 %	100.0 %	100.0 %	100.0 %	94.4 %
赤	11	100.0 %	100.0 %	100.0 %	100.0 %	90.9 %	81.8 %

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

簡易解説

A問題 (7636人AC)『I Scream』

問題文がややこしいです。要するに $A+B$ と $B$ の条件を判定する問題です。

B問題 (6319人AC)『Job Assignment』

同じ従業員 $i$ を仕事A, Bの両方に割り当てる場合の時間は $A_i + B_i$ です。
異なる従業員 $i$, $j$ を割り当てる場合は $max(A_i, B_j)$ です。
$N\le{1000}$ なので、二重ループですべての従業員の組を試す $O(N^2)$ のコードを書けばいいです。

C問題 (4535人AC)『Squared Error』

$|A_i| <= 200$ という制約を利用します。
$A_i$ として現れる数は、$-200 ~ 200$ の $401$ 種類しかありません。
$A$ にどの数が何回出現するか、Counterを使って数えます。
すべての $i\le{j}$ の組について、$$cnt_i\times{cnt_j}\times{(i-j)^2}$ を計算して足し合わせれば答えです。

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

はじめから $1$ 個持っているコンプガチャの期待値です。
答えは $\frac{N}{N - 1} + \frac{N}{N - 2} + \frac{N}{N - 3} + \dots + \frac{N}{1}$ です。

E問題 (1992人AC)『Mex Min』[この記事では解説しません]

各数の出現回数を数えておいて、左端の数の出現回数を $-1$, 右端の出現回数を $+1$ していきます。
操作中にある数の出現回数が $0$ になったときに、現在のmexを更新します。

F問題 (215人AC)『Digits Paradise in Hexadecimal』[この記事では解説しません]

桁DPです。十六進表記でややこしいですが、基本的には十進表記の場合と同様に解けばいいです。

私（うにだよ）の結果

CはTLEです。Dに手間取りました。

A問題『I Scream』

問題ページ：A - I Scream
灰コーダー正解率：95.1 %
茶コーダー正解率：98.9 %
緑コーダー正解率：99.1 %

考察

判定条件は 『乳固形分』 と 『乳脂肪分』 の二つあります。

入力で与えられるのは 『無脂乳固形分』 $A$ パーセント、『乳脂肪分』 $B$ パーセントです。

『乳固形分』が直接与えられていないので、計算して求める必要があります。『乳固形分』は 『無脂乳固形分』と 『乳脂肪分』の合計で $A+B$ パーセントです。

実装

if、elifを使って上から順に条件の判定をします。満たしたら $1$ つだけ数字を出力するように気をつけてください。

if 文を $4$ つ並べただけだと、一番上の条件を満たすときに、$1,2,3,4$ と出力されてしまいます。

コード

A, B = map(int, input().split())
X = A + B  # 乳固形分
Y = B  # 乳脂肪分

if X >= 15 and Y >= 8:
    print(1)
elif X >= 10 and Y >= 3:
    print(2)
elif X >= 3:
    print(3)
else:
    print(4)

B問題『Job Assignment』

問題ページ：B - Job Assignment
灰コーダー正解率：64.8 %
茶コーダー正解率：96.0 %
緑コーダー正解率：99.1 %

考察

仕事A,仕事Bへの従業員の割り当て方は $N^2$ 通りあります。この問題の制約は $N\le{1000}$ なので、最大でも $100$ 万組です。すべての組についてかかる時間を全探索して、一番小さいものを出力すればいいです。

実装

二重ループで全探索します。

同じ従業員の場合（$i = j$）の場合と、異なる従業員の場合（$i \ne j$）でかかる時間の計算式が違うので、if文で場合分けします。同じ従業員なら $A_i + B_i$ 分で、異なる従業員なら $max(A_i, B_j)$ 分です。

コード

N = int(input())
A = []
B = []

for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

ans = float('INF')  # 正の無限大を初期値にします

for i in range(N):
    for j in range(N):
        if i == j:
            score = A[i] + B[i]
        else:
            score = max(A[i], B[j])
        ans = min(ans, score)

print(ans)

C問題『Squared Error』

問題ページ：C - Squared Error
灰コーダー正解率：27.6 %
茶コーダー正解率：75.8 %
緑コーダー正解率：94.0 %

考察

求める答えには『数列の順番を入れ替えても結果が変わらない』という重要な性質があります。$(A_i - A_j)^2$ の $A_i$ と $A_j$ を入れかえても同じ結果になるからです。

つまり、各数字が何回出現するかだけが答えに影響して、どこに出てくるかは関係ありません。

また、制約を見てみると $|A_i|\le{200}$ とあります。数列に出てくる値の種類は最大でも $-200\ ～\ 200$ の $401$ 種類しかありません。

以上の二つの性質を利用して、それぞれの数字が何回出てくるかを数えたあと、同じ値の要素をまとめて処理します。

$x$ が $cx$ 個、$y$ が $cy$ 個あるとします。このとき、$x$ と $y$ の組は $cx\times{cy}$ 組あります。$1$ 組につき $(x - y)^2$ だけ答えが増えるので、$cx\times{cy}\times{(x - y)^2}$ を足せばいいです。

$x < y$ である数字の組だけ調べるようにしないと、同じ組を重複して数えてしまうので注意してください。

実装

数を数えるときは、Counterを使うと楽です。

1. Counterで各数字が数列に出現する回数を数える
2. 二重ループで $-200\le{x}\le{200}$ 、 $x\lt{y}\le{200}$ の組 $(x,\ y)$ の答えをすべて計算して足し合わせる

コード

from collections import Counter

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

ans = 0

for x in range(-200, 201):
    for y in range(x + 1, 201):
        cx = cnt[x]
        cy = cnt[y]
        ans += cx * cy * (x - y) ** 2

print(ans)