はじめに
ユーザ名 hidehico
コンテスト名 トヨタ自動車プログラミングコンテスト2025（AtCoder Beginner Contest 389
順位 2095th / 12393 (top 1.75%)
パフォーマンス 1204
レーティング 872 → 911 (+39) Highest更新！
段級位 6 級
やったー久しぶりの、水パフォ(コンテスト前、松本駅で親を待つ間、寒くて駅の階段を爆速で登り、すぐ降りた奇行をしたやつが言うな)
解いた問題数は、ABCD4完でした
コンテスト中の流れ
開始3秒
atcoder cliで、コンテストデータを取得する
A問題を見る
開始48秒
A問題を提出
開始60秒
B問題を見る
難しそうに見えたが、案外簡単ですぐACできた
開始3分
C問題を見る
このタイプのクエリは見たことがあったので、その方針でやると決めた
開始26分
C問題をバグり散らかしつつも、AC(0ペナ)
開始27分
D問題を見る
方針がすぐ定まり、実装を始める
開始41分
D問題を提出し、AC
順位表を見てどちらを、解きに行くか、見る
Eは挑戦している人は多いが、ACしている人が少ない
Fはその反対
Fはセグ木っぽかったので、Fのセグ木は解いた試しがないので、Eを解きに行く
そのまま時間は、すぎてゆきコンテストは終了した
使っているライブラリ
github(コミットする時、毎度のようにコンフリクトするため、萎える(pull忘れたりするのが多い))
二分探索ライブラリ
def binary_search(fn: Callable[[int], bool], right: int = 0, left: int = -1) -> int:
while right - left > 1:
mid = (left + right) // 2
if fn(mid):
left = mid
else:
right = mid
return left
そんじゃ一問ずつ感想書きますか
A問題
普通に実装した
first acが13秒でびっくりした(自分は、48秒)
ACコード(ライブラリ抜粋 以下略)
S = s()
print(int(S[0]) * int(S[2]))
B問題
最初戸惑ったけど、案外簡単だった
$10^18 < 20!$なので20までを、全探索した
ACコード
X = ii()
for i in range(1, 21):
if X == factorial(i):
print(i)
exit()
C問題
抜けたヘビの長さの総和を位置から引いて出力すればいい
だけど、方針ミスったりで、時間がかかった
ACコード
Q = ii()
L = defaultdict(lambda: (0, 0))
cur = -1
t = 0
m = 0
for _ in [0] * Q:
l = il()
if l[0] == 1:
L[cur + 1] = (L[cur][-1], L[cur][-1] + l[1])
cur += 1
elif l[0] == 2:
m = L[t][-1]
t += 1
else:
print(L[t - 1 + l[1]][0] - m)
D問題
最初にいい方針、引けたので、20分ぐらいでACできた
x = 0の線とy = 0の線を使って四等分して、そのどこかの、区間の答えを4掛ければacできた
その答えを求める計算は、x軸を全探索して、そのxを使って二分探索すればいい
距離はユークリッド距離で求めなければいい(マンハッタン距離使って5分ぐらいロスした)
僕は二分探索で実装したけど、公式解説は尺取り法みたい、まあどっちでもいっか
ACコード
R = ii()
ans = 0
for i in range(R + 1):
if i + 1 > R:
continue
def c(mid):
return ((i + 0.5) ** 2) + ((mid + 0.5) ** 2) <= R * R
ans += binary_search(c, R * 2, 0)
print(ans * 4 + 1)
E問題
いろいろ試したけど、ACできなかった
解法は二分探索みたい
さいごに
やっぱ水パフォ出すと、脳汁がヤバいですね(水パフォぎりぎりだろ)
Cで方針ミスったけど、Dで挽回できたので、結果オーライでした
AHCが楽しみです
:qa!