初めに
二次予選お疲れ様でした。
僕は、落ちました(感情の変化おかしいだろ)
点数は、219点、ボーダー高いですね280点(B問題をまともにdpだと思っていた、やつが言うな)
最初290点ぐらいかなーって思ってたけど、AI使用で落とされた人が結構いるみたいですね
ツッコミ: 二次予選の記事はいつ書くんだ???
僕: 本戦が終わってから
ツッコミ: 落ちたくせになんで
僕: いつ記事上げていいか、わからない(ツッコミ辛辣すぎだろ)
ツッコミ: そういうことか(clarでも送ればよかったのに)
ということで本戦が終わってから書きまーす。
やったー初の5完、初の水perf、入緑(やっぱテンションおかしい)
今度色変記事、書きます。
コンテスト中の流れは、AとBは瞬殺、Cはbit全探索で解き、Dは累積和としゃくとり法をつかい、Eはダイクストラ法みたいな感じで解きました。
なんかあったかくなりそうですね、明日は最低1度(ついに感覚おかしくなったか)
さて本題
使っているライブラリ
前回から結構変えました。
セグ木をac-libraryに変えたり色々しました
あとlinuxのtuxくんのアスキーアートを入れました(cowsayで生成した)
ツッコミ: 無駄の極みだ
A問題
普通に、実装しました。
なんか同じような問題を見たことがあるような...
acコード(ライブラリ抜粋)
n, a, b = sl()
S = s()
ans = ""
for s in S:
if a == s:
ans += s
else:
ans += b
print(ans)
B問題
あARC div2のトラウマが蘇る
400点問題のくせに水diff、普通予選とかじゃないと出ない、レベルエグいって
まあ現在のレートが更新範囲内だったら、レートの変動を受け入れる、方式でやればOK
入力例2のレートが実際のchokudaiのレートで笑った
acコード(ライブラリ抜粋)
N, R = il()
for _ in [0] * N:
D, A = il()
if D == 1:
if 1600 <= R <= 2799:
R += A
else:
if 1200 <= R <= 2399:
R += A
print(R)
C問題
bit全探索で実装した
インデックスに対応する文字列を持っておけばすぐできました
ねえDから先に解いてた人いたけど絶対、Cのほうが簡単でしょ
acコード(ライブラリ抜粋)
T = il()
L = []
for bit in range(1 << 5):
n = ""
p = 0
for i in range(5):
if bit & (1 << i):
n += upperlist[i]
p += T[i]
if n == "":
continue
L.append((n, p))
L.sort(key=lambda l: l[0])
L.sort(key=lambda l: l[1], reverse=True)
for n, p in L:
print(n)
D問題
とりあえず周期に含まれる部分は、除算で可能だから、累積和取って、$a_N-a_i$をdとすると、$S-d$がaに存在すれば、Yesにして
$S-d$がaに存在する部分は、愚直にやるとTLEするので累積和を、setに持ち替えると、一クエリごとの計算量が$O(1)$になるため、全体の計算量が$O(N)$になる。
で与えられる、Aの中に、Sが入っていると、先程の計算ではカバーしきれないため、尺取法でyesになるか判定すればOKでした
公式解説では、入力で与えられるAを二倍にしてあーだこーだやるみたいです
親に説明しろと言われて、説明したら言語化全然できませんでした。(親はruby勢で3完)
あと用意しておいたsetを使い忘れ、一TLE喰らいました(やっぱこいつアホミスの名人だな)
acコード(ライブラリ抜粋)
N, S = il()
A = il()
B = [0] + list(accumulate(A))
C = set(B)
for i in range(N):
cur = B[-1] - B[i]
if cur > S:
continue
ts = S - cur
tmp = ts // B[-1]
ts -= B[-1] * tmp
if ts in C:
print("Yes")
exit()
r = 0
su = 0
for l in range(N):
while r < N and su < S:
su += A[r]
r += 1
if su == S:
print("Yes")
exit()
if r == l:
r = l + 1
else:
su -= A[l]
print("No")
E問題
優先度付きキューを使って解きました。
JOIの過去問でダイクストラ法などを勉強したのと、二次予選のB問題で出てきたので覚えてました
ちなみに、二次予選のBはダイクストラのほうが簡単にできるのに、dpでバグらせ結局のとこ、70点しか取れませんでした
具体的には、キューから取り出した値が、更新されたら、そこから隣接する未訪問の場所を、キューに入れれば、できます
なお更新するときは、現在の強さに、吸収されたスライムの強さを足します
自分は、キューに入っている内容を、setに入れたのですがオーバーキルでした。
acコード(ライブラリ抜粋)
H, W, X = il()
X = 1 / X
MOVES = [(1, 0), (-1, 0), (0, 1), (0, -1)]
P, Q = il(-1)
S = li(H, il)
ans = S[P][Q]
used = create_array2(H, W, False)
used[P][Q] = True
PQ = []
T = set()
for i in range(4):
nx, ny = P + MOVES[i][0], Q + MOVES[i][1]
if not (0 <= nx < H and 0 <= ny < W):
continue
heapq.heappush(PQ, (S[nx][ny], nx, ny))
T.add((nx, ny))
while PQ:
p, x, y = heapq.heappop(PQ)
if used[x][y]:
continue
if p >= ans * X:
continue
used[x][y] = True
T.remove((x, y))
ans += p
for i in range(4):
nx, ny = x + MOVES[i][0], y + MOVES[i][1]
if not (0 <= nx < H and 0 <= ny < W):
continue
if used[nx][ny] or (nx, ny) in T:
continue
heapq.heappush(PQ, (S[nx][ny], nx, ny))
T.add((nx, ny))
print(ans)
最後に
5完した瞬間は、アドレナリンがエグかったです。
やっぱatcoderは神ゲーですね
まあ当面の間は入水目指して頑張ります。