今回はPythonでABC418をA~Eまで解くことができたので、その備忘録を纏めます。
３コンペ振りにD問題を解けただけでなく、初めてE問題をコンテスト中に解くことができ、無事入緑することができました。
コンテスト概要
AtCoder Beginner Contest 418
開催日:2025年8月9日 21:00-22:40
A - I'm a teapot
方針
文字列Sの最後の文字がteaで終わっているかどうかを判定するだけ
N = int(input())
S = input().strip()
if S.endswith("tea"):
print("Yes")
else:
print("No")
B - You're a teapot
充填率の定義
-
tの先頭と末尾の文字が共にtであり、かつ長さが3以上である場合、tの個数をxとした場合のtの充填率は$\frac{x-2}{|t|-2}$ - そうでない場合は、充填率は0
方針
文字列Sの中から、tとt で挟まれる＆その中でtの数が3以上になる組み合わせから充填率が一番高くなる値を求めらば良い。
S = input().strip()
n = len(S)
ans = 0.0
# 先頭となるtを探索
for i in range(n):
if S[i] != 't':
continue
# 後尾となるtを探索
for j in range(i + 2, n):
if S[j] != 't':
continue
# 部分文字列の作成
sub = S[i:j+1]
# tの数をカウント
x = sub.count('t')
if x >= 3:
# 充填率の計算
rate = (x - 2) / (len(sub) - 2)
# 最大値の更新
ans = max(ans, rate)
print(ans)
C - Flush
問題の本質
- 勝つには 同じフレーバー b 個 が必要
- ディーラーは 1種類 b-1 個まで 渡して阻止する
方針
-
Aをソート - b-1 以下の要素を二分探索で探す
S = 小さい方の合計 + 残り種数*(b-1)- 答え = S+1（総数超えたら -1）
計算量
- ソート＋累積和：O(N log N)
- 各クエリ：O(log N)
import sys
N, Q = map(int,input().split())
A = list(map(int,input().split()))
queries = [int(input()) for _ in range(Q)]
A.sort()
prefix_sum = [0] * (N + 1)
#累積和
for i in range(N):
prefix_sum[i+1] = prefix_sum[i] + A[i]
total_tea_bags = prefix_sum[N]
for b in queries:
k = b-1
# 二分探索
left = 0
right = N - 1
idx = -1
while left <= right:
mid = (left+right) // 2
if A[mid] <= k:
idx = mid
left = mid + 1
else:
right = mid - 1
S = 0
if idx != -1:
S = prefix_sum[idx+1]
count_k = N - (idx + 1)
S += count_k * k
else:
S = N * k
x = S + 1
if x > total_tea_bags:
print(-1)
else:
print(x)
D - XNOR Operation
問題の本質
- 操作ルールはペア
(S[i], S[i+1])に対して以下の変換を行う：
| S[i] | S[i+1] | x |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- 最後の1文字が
1になるような部分文字列を 美しい文字列 と呼ぶ - 求めるのは T の全ての部分文字列のうち、美しい文字列の個数
重要な観察
- 上表の規則は、実は「ペアの和の偶奇を反転させる」動きに相当する
- 操作を繰り返すと、最終結果は
(1 の個数 + 部分文字列の長さ の偶奇) の組み合わせに依存する。 - 美しい文字列 ⇔ (長さの偶奇) XOR (1 の個数の偶奇) = 1
方針
- 1 の個数の累積和を計算
- 各位置
iに対して
- 部分文字列の長さの偶奇 =
(i+1) % 2 -
1 の個数の偶奇 =
prefix_sum[i+1] % 2 - これらの XOR を計算 →
current_xor_sum
- 同じ
current_xor_sumを持つ始点との組み合わせが美しい文字列になる - 出現回数をハッシュマップ
countで管理しながら総和を取る
N = int(input())
T = input()
prefix_sum = [0] * (N+1)
for i in range(N):
prefix_sum[i+1] = prefix_sum[i] + (1 if T[i] == '1' else 0)
ans = 0
count = {0:1}
for i in range(N):
idx_parity = (i+1) % 2
ps_parity = prefix_sum[i+1] % 2
current_xor_sum = idx_parity ^ ps_parity
if current_xor_sum in count:
ans += count[current_xor_sum]
count[current_xor_sum] += 1
else:
count[current_xor_sum] = 1
print(ans)
E - Trapezium
台形の数を数え上げる問題
問題の本質
- 台形は「一組だけ平行な辺をもつ四角形」
- 二次元平面で点の座標が与えられ、
4点の組み合わせのうち台形になるものを数える - 条件：
- 任意の2点は異なる位置
- 任意の3点は同一直線上にない
方針
-
平行な辺を数える
- 任意の点ペアごとに傾きを計算（既約分数形式で正規化）
- 同じ傾きの線分がペアで選ばれると「平行な辺」ができる
- 平行な辺の組み合わせ数 = total_parallels
-
平行四辺形を除外
- 平行四辺形は「二組の辺が平行」→台形ではない
- 特徴：対角線の中点が一致
- 中点ごとに点ペアをグループ化し、組み合わせ数を数える
- 平行四辺形の数 = total_parallelograms
-
台形の数
実装のポイント
-
傾きの正規化
(dx, dy)を最大公約数で割り、符号を揃えることで一意化 -
中点の計算
(x1 + x2, y1 + y2)と整数で持つ（浮動小数回避） - それぞれ組み合わせ数
nC2 = n*(n-1)/2を計算
from collections import defaultdict
from math import gcd
N = int(input())
points = [tuple(map(int, input().split())) for _ in range(N)]
slope_counts = defaultdict(int)
for i in range(N):
for j in range(i+1,N):
x1, y1 = points[i]
x2, y2 = points[j]
dx = x2 - x1
dy = y2 - y1
if dx == 0:
slope = (1, 0)
elif dy == 0:
slope = (0, 1)
else:
divisor = gcd(abs(dx), abs(dy))
dx //= divisor
dy //= divisor
if dx < 0:
dx, dy = -dx, -dy
slope = (dx, dy)
slope_counts[slope] += 1
total_parallels = 0
for k in slope_counts.values():
total_parallels += k * (k-1) // 2
midpoint_counts = defaultdict(int)
for i in range(N):
for j in range(i+1, N):
x1, y1 = points[i]
x2, y2 = points[j]
midpoint = (x1 + x2, y1 + y2)
midpoint_counts[midpoint] += 1
total_parallelograms = 0
for k in midpoint_counts.values():
total_parallelograms += k * (k-1) // 2
ans = total_parallels - total_parallelograms
print(ans)
結果
ABCDE 5完
順位 484th / 12888
パフォーマンス 1831
レーティング 671 → 919 (+248)
感想
今回のD,E問題はTLEとなりそうな問題ではなく、たまたま上手く行った結果だと思います。とはいえ年内に入緑することができて自信がつきました。とりあえず引き続きD問題までを安定して解けるように頑張っていこうと思います。（解説がちょいちょい雑だとおもうので、時間がある時に修正するかもしれません。）