ABC206のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
よかったらLGTMしていただけると、私のやる気がでます！
目次
ABC206 まとめ
A問題『Maxi-Buying』
B問題『Savings』
C問題『Swappable』
D問題『KAIBUNsyo』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC206 まとめ
全提出人数: 9102人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 9分 | 6613(6380)位 |
| 400 | ABC--- | 600 | 61分 | 5363(5132)位 |
| 600 | ABC--- | 600 | 33分 | 4365(4135)位 |
| 800 | ABC--- | 600 | 17分 | 3363(3135)位 |
| 1000 | ABCD-- | 1000 | 82分 | 2455(2234)位 |
| 1200 | ABCD-- | 1000 | 44分 | 1724(1508)位 |
| 1400 | ABCD-- | 1000 | 26分 | 1183(972)位 |
| 1600 | ABCD-- | 1000 | 15分 | 795(593)位 |
| 1800 | ABCDE- | 1500 | 83分 | 512(337)位 |
| 2000 | ABCDE- | 1500 | 52分 | 333(177)位 |
| 2200 | ABCDE- | 1500 | 31分 | 227(87)位 |
| 2400 | ABCDEF | 2100 | 103分 | 151(40)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 4197 | 98.4 % | 93.8 % | 47.8 % | 5.1 % | 0.3 % | 0.1 % |
| 茶 | 1635 | 99.7 % | 99.4 % | 93.9 % | 27.7 % | 1.4 % | 0.0 % |
| 緑 | 1181 | 99.5 % | 99.5 % | 98.9 % | 69.6 % | 5.7 % | 0.1 % |
| 水 | 733 | 99.6 % | 99.7 % | 99.7 % | 91.7 % | 20.9 % | 1.2 % |
| 青 | 344 | 99.7 % | 99.7 % | 100.0 % | 98.3 % | 57.9 % | 14.8 % |
| 黄 | 179 | 93.3 % | 93.8 % | 93.3 % | 93.8 % | 69.3 % | 49.2 % |
| 橙 | 43 | 97.7 % | 97.7 % | 100.0 % | 100.0 % | 88.4 % | 93.0 % |
| 赤 | 14 | 92.9 % | 92.9 % | 92.9 % | 92.9 % | 85.7 % | 100.0 % |
※表示レート、灰に初参加者は含めず
私（うにだよ）の結果
Eが解けないとレートが増えませんね。
A問題『Maxi-Buying』
問題ページ：A - Maxi-Buying
灰コーダー正解率：98.4 %
茶コーダー正解率：99.7 %
緑コーダー正解率：99.5 %
考察
$\lfloor 1.08 \times N \rfloor$ はそのまま計算せずに、$108\times{N}$ を $100$ で割って切り捨てたほうが良いです。
浮動小数点数を使った計算は、値が大きくなると誤差が無視できなくなり、WAになる恐れがあるからです。（この問題では、値が小さいために使っても問題ありません）
コード
def main():
N = int(input())
x = N * 108 // 100
if x < 206:
print('Yay!')
elif x == 206:
print("so-so")
else:
print(":(")
if __name__ == '__main__':
main()
B問題『Savings』
問題ページ：B - Savings
灰コーダー正解率：93.8 %
茶コーダー正解率：99.4 %
緑コーダー正解率：99.5 %
考察
制約が $N\le10^9$ と小さいので、whileループでシミュレーションすれば解くことができます。
$1+2+\dots+k = \frac{k(k+1)}{2}$ です。つまり、$k$ 日目の貯金額は、 $k$ の二乗の半分くらいになります。したがって、$N=10^9$ であっても、$10^5$ 日目よりは答えが小さくなると予想できます。なぜなら、$\frac{(10^5)^2}{2} = \frac{10^{10}}{2}\gt{10^9}$ だからです。
コード
def main():
def solve():
money = 0
day = 1
while True:
money += day
if money >= N:
return day
day += 1
N = int(input())
print(solve())
if __name__ == '__main__':
main()
おまけ : N が非常に大きい場合
$N$ がより大きく、例えば$N\le{10^{18}}$ といった場合、シミュレーションで解くことはできません。
この場合、C問題レベルになりますが、二分探索というアルゴリズムを使うと解くことができます。
C問題『Swappable』
問題ページ：C - Swappable
灰コーダー正解率：47.8 %
茶コーダー正解率：93.9 %
緑コーダー正解率：98.9 %
考察
すべての $i, j$ の組を試すと計算量が $O(N^2)$ になるので、TLEになります。
$i<j$ という条件があるので、左から順番に見ていくことにします。
今、左から $j$ 番目の $A_j$ を見ているとします。$i<j$ となる $i$ は $1,2,\dots,j-1$ の $j-1$ 個あります。（$A_j$ より左側にある要素は $j-1$ 個ありますね）これら $j-1$ 個の整数 $A_1, A_2,\dots,A_{j-1}$のうち、$A_i\ne{A_j}$ であるものがいくつあるか知りたいです。
そのために、今までどの整数が何回出てきたかを数えておきます。ある $j$ に対する答えは、 $j-1$ 個から、$A_j$ と同じ値が何回出てきたかを引けば求められます。
実装
数を数えるときは、collectionsモジュールのCounterを使いましょう。
コード
def main():
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter() # C[x]: 今までxが何回出現したか
ans = 0
for j in range(N):
ans += j - C[A[j]] # j=0 から数えているので、今まで見た整数はj個です
C[A[j]] += 1 # A[j]の出現回数を1増やします
print(ans)
if __name__ == '__main__':
main()
D問題『KAIBUNsyo』
問題ページ：D - KAIBUNsyo
灰コーダー正解率：5.1 %
茶コーダー正解率：27.7 %
緑コーダー正解率：69.6 %
疲れたので軽い説明にさせてください、ごめんね！
考察
無向グラフを考えます。頂点は数字で、同じ数字でなければならない頂点同士を辺で結びます。（回文ですから、前から $i$ 番目と後ろから $i$ 番目の要素が同じ必要があります）
この無効グラフで、連結な頂点同士はすべて同じ数字にしなければなりません。ある連結成分をすべて同じ数字にするには、『連結成分の個数 - 1』個の数字を書き換える必要があります。
したがって、すべての連結成分について、『連結成分の個数 - 1』を足し合わせたものが答えになります。
ある要素と要素が連結かどうかを管理するには、UnionFindというデータ構造を使うのが楽です。
コード
class UnionFind:
"""
0-indexed
"""
from typing import List
def __init__(self, n):
self.n = n
self.parent = [-1] * n
def unite(self, x, y) -> int:
"""
xとyを併合
"""
x = self.root(x)
y = self.root(y)
if x == y:
return 0
if self.parent[x] > self.parent[y]:
x, y = y, x
self.parent[x] += self.parent[y]
self.parent[y] = x
return self.parent[x]
def is_same(self, x, y) -> bool:
"""
xとyが同じ連結成分か判定
"""
return self.root(x) == self.root(y)
def root(self, x) -> int:
"""
xの根を取得
"""
if self.parent[x] < 0:
return x
else:
self.parent[x] = self.root(self.parent[x])
return self.parent[x]
def size(self, x) -> int:
"""
xが属する連結成分のサイズを取得
"""
return -self.parent[self.root(x)]
def all_sizes(self) -> List[int]:
"""
全連結成分のサイズのリストを取得
計算量: O(N)
"""
sizes = []
for i in range(self.n):
size = self.parent[i]
if size < 0:
sizes.append(-size)
return sizes
def groups(self) -> List[List[int]]:
"""
全連結成分のサイズの内容のリストを取得
計算量: O(N・α(N))
なんでACLはO(N)でできるんでしょうね
"""
groups = dict()
for i in range(self.n):
p = self.root(i)
if not groups.get(p):
groups[p] = []
groups[p].append(i)
return list(groups.values())
def main():
N = int(input())
A = list(map(int, input().split()))
def solve():
Const = 2 * 10 ** 5 + 5
uf = UnionFind(Const)
if N % 2 == 0:
first = A[:N // 2]
second = A[N // 2:][::-1]
else:
# 数列の長さが奇数の場合、中央の要素はなんでも良いので省きます
first = A[:N // 2]
second = A[N // 2 + 1:][::-1]
for x, y in zip(first, second):
uf.unite(x, y)
ans = 0
for x in uf.all_sizes():
ans += x - 1
return ans
print(solve())
if __name__ == '__main__':
main()