はじめに
ユーザ名 hidehico
コンテスト名 HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)
順位 2438th / 11601 (top 2.04%)
パフォーマンス 1114
レーティング 840 → 872 (+32) Highest更新！
段級位 6 級
よっしゃー、5完 6ペナ???
えーはいE問題でやらかして6ペナ食ったアホです
ランダムチェッカー使ってやっとEを通しました
コンテストの流れ
開始3秒
acc newを実行し、テストケースを取得する
開始60秒
vimでgolfできそうと思ったけど、普通にAをpythonで通す
開始3分
問題文を読むのに時間がかかったけどBを通す
開始8分
二分探索でCを通す ライブラリ作っといてよかった
開始20分
imos法でDを通す
開始50分
Eのロジックが完成
ここから6ペナが始まる
開始75分
すでに6ペナを食っている
パフォもあまり変らないだろうと思いつつも、ランダムチェッカーを作成した
開始80分
パラメータをイジってやっとEを通す
こんなかんじでした
そんじゃ1問ずつ感想書きますか
使っているライブラリ
github
ファイル分割したんでよかったら、見てください
二分探索ライブラリ
今回の記事で使っているので紹介します
def binary_search(fn: Callable[[int], bool], right: int = 0, left: int = -1) -> int:
"""
二分探索の抽象的なライブラリ
評価関数の結果に応じて、二分探索する
最終的にはleftを出力します
関数のテンプレート
def check(mid:int):
if A[mid] > x:
return True
else:
return False
midは必須です。それ以外はご自由にどうぞ
"""
while right - left > 1:
mid = (left + right) // 2
if fn(mid):
left = mid
else:
right = mid
return left
筆者のdotfiles(宣伝)
github
neovimの設定を書きなおしたら、結構プラグインの数が減らせました
A問題
普通に実装した
ACコード(あとで書いた)
escapeが消えてますがご了承
a DaUPCZZ
B問題
全探索しました
ACコード(ライブラリ抜粋)
N, D = il()
L = li(N, il)
for k in range(1, D + 1):
ans = 0
for t, l in L:
ans = max(ans, (l + k) * t)
print(ans)
C問題
パッと見 にぶたんだと思って実装しました
ライブラリ作っといたので、実装の手間が大幅に軽減しました(オススメです)
ACコード(ライブラリ抜粋)
N = ii()
A = il()
ans = 0
for a in A:
def c(mi):
if A[mi] <= a // 2:
return True
else:
return False
ans += binary_search(c, N, -1)
print(ans)
D問題
imos法を使って実装しました
親に説明しろと言われて、どうしようか迷ってます
まずimos法から解説しないとなので大変
ACコード(ライブラリ抜粋)
N = ii()
A = il()
dp = [0] * (N + 1)
ans = [0] * N
cur = 0
for i in range(N):
cur += dp[i]
A[i] += cur
if i + A[i] + 1 >= N:
ans[i] = A[i] - (N - i - 1)
dp[i + 1] += 1
continue
if A[i] == 0:
continue
dp[i + 1] += 1
dp[i + A[i] + 1] -= 1
print(*ans)
E問題
二分探索を使って実装しました
上に置くモチは、一番小さいとこからK番目まで、下に置くモチは、$N-K$番目から$N$番目までを、使えばOK
それができるか、できないかを判定関数にして二分探索すればよかった
だけどKの上限と下限の設定をミスって案の定6ペナ食らいました
ランダムチェッカー使ったら一瞬でした
ACコード(ライブラリ抜粋)
N = ii()
A = il()
def c(mid):
a = A[:mid]
b = A[N - mid :]
for i in range(mid):
if a[i] <= b[i] // 2:
continue
else:
return False
return True
ans = binary_search(c, N // 2 + 1, -1)
print(ans)
最後に
やはりペナの効果は大きいですね
来週はAHCなので楽しみです。(ていうかABCの結果が心配)
最後まで見ていただいて、ありがとうございます。