ABC207のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo
よかったらLGTMしていただけると、私のやる気がでます！
目次
ABC207 まとめ
A問題『Repression』
B問題『Hydrate』
C問題『Many Segments』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC207 まとめ
全提出人数: 8401人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 64分 | 6115(5893)位 |
| 400 | AB---- | 300 | 20分 | 4970(4748)位 |
| 600 | ABC--- | 600 | 94分 | 4052(3833)位 |
| 800 | ABC--- | 600 | 60分 | 3133(2917)位 |
| 1000 | ABC--- | 600 | 41分 | 2305(2091)位 |
| 1200 | ABC--- | 600 | 30分 | 1631(1425)位 |
| 1400 | ABC--- | 600 | 21分 | 1126(925)位 |
| 1600 | ABC--- | 600 | 13分 | 752(570)位 |
| 1800 | ABC-E- | 1100 | 103分 | 479(328)位 |
| 2000 | ABC-E- | 1100 | 63分 | 311(176)位 |
| 2200 | ABC-E- | 1100 | 35分 | 211(89)位 |
| 2400 | ABCDE- | 1500 | 68分 | 122(43)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3832 | 98.1 % | 65.0 % | 27.6 % | 0.1 % | 0.4 % | 0.1 % |
| 茶 | 1538 | 99.9 % | 94.4 % | 73.4 % | 0.7 % | 1.0 % | 0.2 % |
| 緑 | 1090 | 99.5 % | 97.9 % | 90.5 % | 2.8 % | 3.5 % | 0.4 % |
| 水 | 712 | 99.4 % | 98.0 % | 95.7 % | 11.2 % | 18.1 % | 1.4 % |
| 青 | 308 | 99.7 % | 98.7 % | 98.4 % | 17.5 % | 52.9 % | 6.8 % |
| 黄 | 171 | 94.7 % | 94.2 % | 93.0 % | 39.2 % | 59.1 % | 24.0 % |
| 橙 | 41 | 97.6 % | 97.6 % | 97.6 % | 73.2 % | 85.4 % | 68.3 % |
| 赤 | 14 | 100.0 % | 100.0 % | 100.0 % | 78.6 % | 92.9 % | 85.7 % |
※表示レート、灰に初参加者は含めず
私（うにだよ）の結果
B問題に時間をかけすぎました。
A問題『Repression』
問題ページ：A - Repression
灰コーダー正解率：98.1 %
茶コーダー正解率：99.9 %
緑コーダー正解率：99.5 %
実装
3通りの選び方の最大値を出力するコード
2枚のカードの選び方は、$A+B$, $B+C$, $C+A$ の 3通りあります。これらの最大値を出力すればいいです。
3枚の合計から最小値を引くコード
3枚のうちいらないカードは、一番小さい数字が書いてあるカードです。
つまり、$A + B + C$ から、$A,\,B,\,C$ の最小値を引けば答えになります。
リストで受け取ってソートするコード
入力をリストLとして受け取ってソートします。それから L[1] + L[2]を出力すればいいです。
コード
3通りの選び方の最大値を出力するコード
def main():
A, B, C = map(int, input().split())
print(max(A + B, B + C, C + A))
if __name__ == '__main__':
main()
3枚の合計から最小値を引くコード
def main():
A, B, C = map(int, input().split())
S = A + B + C
print(S - min(A, B, C))
if __name__ == '__main__':
main()
リストで受け取ってソートするコード
def main():
L = map(int, input().split())
L.sort() # 小さい順にソートされるので、L[1] と L[2] が必要なカードです
print(L[1] + L[2])
if __name__ == '__main__':
main()
B問題『Hydrate』
問題ページ：B - Hydrate
灰コーダー正解率：65.0 %
茶コーダー正解率：94.4 %
緑コーダー正解率：97.9 %
問題の意味
考察
forループで全探索する場合
「ABCのB問題で、制約も$A,B,C,D\le{10^5}$ とそれほど大きくないので、もしも目標が達成可能であるとすれば、それほど操作回数は大きくならないだろう」と予想をして、forループでTLEにならない程度にできる限り多くの回数シミュレーションします。条件を満たした瞬間ループを打ち切って答えを出力ます。forループを抜けるまで見つからなければ達成不可能と考えて-1を出力します。
実際、この方法でACを取ることができます。
※ 公式解説に、目標が達成可能な場合必要な操作回数の最小値は $A$ 以下になることが示されています。
不等式を立てて解く場合
$x$ 回 操作を行ったとき、各色のボールの数は以下の式で表されます。
水色のボールの数：$A + Bx$ 個
赤色のボールの数：$Cx$ 個
「『水色のボールの個数』が『赤色のボールの個数』の $D$ 倍以下になる」を不等式で表すと、以下の式になります。
$A + Bx\le{D}\times{Cx}$
この式を式変形します。
$A\le{D\times{Cx}} - Bx$
$A\le{(D\times{C} - B)x}$
ここで制約より、$A\ge{1}$ 、操作回数 $x\ge{0}$ であることを考えると、$D\times{C} - B\le{0}$ の場合、この不等式は解を持ちません。つまり、目標を達成することは不可能ですから、-1 を出力して終了します。
そうでない場合、すなわち $D\times{C} - B\gt{0}$ で解がある場合を考えます。両辺を $D\times{C} - B$ で割ります。（負や $0$ にはなりませんから、不等式を負の値で割るときに不等号を反転させたり、$0$ 除算のことを考える必要はありません）
$\frac{A}{D\times{C}-B}\le{x}$
この不等式を満たす、最小の非負整数 $x$ は、$A$ を $D\times{C} - B$ で割って、小数点以下を切り上げた値になります。天井関数を使って書くと、$\lceil{\frac{A}{D\times{C}-B}}\rceil$です。
コード
forループで解く場合
ループ回数を1000万回に設定すると、Python 3.8.2で1440ms、PyPy3 (7.3.0)で85msでACできます。
def main():
def solve():
Const = 10 ** 7 + 5 # TLEにならない程度に、できる限り大きな値にします
for x in range(Const):
cyan = A + B * x
red = C * x
if cyan <= D * red:
return x
return -1 # 解が見つかりませんでした
A, B, C, D = map(int, input().split())
print(solve())
if __name__ == '__main__':
main()
不等式を立てて解く場合
def main():
def solve():
t = C * D - B
if t <= 0:
# 不可能な場合です
return -1
return - (-A // t) # Pythonでは、こう書くと切り上げができます
A, B, C, D = map(int, input().split())
print(solve())
if __name__ == '__main__':
main()
C問題『Many Segments』
問題ページ：C - Many Segments
灰コーダー正解率：27.6 %
茶コーダー正解率：73.4 %
緑コーダー正解率：90.5 %
考察
全探索する
制約が$N\le{2000}$ と小さいので、二重ループで $i\lt{j}$ である $(i,j)$ の組を全探索し、共通部分を持つ組の数を数えあげることを考えます。（$N=2000$ のとき、$(i,j)$ の組は $\frac{2000\times{(2000 - 1)}}{2} = 1,999,000$ 組しかありません。）
閉区間・開区間の扱い
閉区間・開区間の説明は、親切にも問題文の折りたたみ部分に書いてあります。 それを読むとわかりやすいです。
さて、入力がすべて整数であることに着目すると、開区間をすべて閉区間に置き換えることができます。
具体的には、以下のように置き換えれば良いです。
$[l, r]$ を $[l,r]$
$[l,r)$ を $[l,r-0.5]$
$(l,r]$ を $[l+0.5, r]$
$(l,r)$ を $[l + 0.5, r-0.5]$
共通部分を持つかの判定：反対を考えよう
『共通部分を持つか？』を直接判定するのは面倒です。しかし、反対の『共通部分を持たないか？』を判定するのは比較的容易です。
閉区間 $[A,B]$ と、閉区間 $[C,D]$ が共通部分を持たないのは以下の2パターンあります。（画像参照、$[A,B]$ を固定して考えてみましょう）
- 閉区間$[A,B]$ の右端 $B$ よりも、閉区間 $[C,D]$ の左端 $C$ が右側にある
- 閉区間$[A,B]$ の左端 $A$ よりも、閉区間 $[C,D]$ の右端 $D$ が左側にある
条件式で表すと
$B<C$ または $D<A$
となります。この条件式をnotで反転すれば、『共通部分を持つか？』を判定できます。
実装
コードを読んだほうが詳細な実装を理解しやすいと思うので、簡単な流れだけを説明します。
- 入力を受けとる際に、開区間を閉区間に変換する**
- 二重ループで、すべての$(i,j)$の組を全探索する
- 関数
judge(a, b, c, d)で、共通区間を持つか判定する
コード
def main():
def func(t, l, r):
"""
開区間を閉区間に変換します
"""
if t == 1:
# [l, r]
return l, r
if t == 2:
# [l, r)
return l, r - 0.5
if t == 3:
# (l, r]
return l + 0.5, r
if t == 4:
# (l, r)
return l + 0.5, r - 0.5
def judge(a, b, c, d):
b1 = b < c
b2 = d < a
if not (b1 or b2):
# 共通区間がある
return 1
else:
# 共通区間がない
return 0
N = int(input())
L = [-1] * N
R = [-1] * N
for i in range(N):
t, l, r = map(int, input().split())
l, r = func(t, l, r) # tに応じて、与えられた区間を閉区間に変換します
L[i], R[i] = l, r
ans = 0
for i in range(N):
a, b = L[i], R[i]
for j in range(i + 1, N):
c, d = L[j], R[j]
ans += judge(a, b, c, d)
print(ans)
if __name__ == '__main__':
main()