茶色コーダーによるABC384振り返り


# 初めに

二次予選お疲れ様でした。

僕は、落ちました(感情の変化おかしいだろ)
点数は、219点、ボーダー高いですね280点(B問題をまともにdpだと思っていた、やつが言うな)
~~最初290点ぐらいかなーって思ってたけど、AI使用で落とされた人が結構いるみたいですね~~

ツッコミ: 二次予選の記事はいつ書くんだ???
僕: 本戦が終わってから
ツッコミ: 落ちたくせになんで
僕: いつ記事上げていいか、わからない(ツッコミ辛辣すぎだろ)
ツッコミ: そういうことか(clarでも送ればよかったのに)

ということで本戦が終わってから書きまーす。

やったー初の5完、初の水perf、入緑(やっぱテンションおかしい)
今度色変記事、書きます。

コンテスト中の流れは、AとBは瞬殺、Cはbit全探索で解き、Dは累積和としゃくとり法をつかい、Eはダイクストラ法みたいな感じで解きました。

なんかあったかくなりそうですね、明日は最低1度(ついに感覚おかしくなったか)

さて本題

使っているライブラリ
前回から結構変えました。
セグ木をac-libraryに変えたり色々しました
あとlinuxのtuxくんのアスキーアートを入れました(cowsayで生成した)
ツッコミ: 無駄の極みだ

[github](https://github.com/hidehic0/my-kyopro-code/blob/main/Performance/.template/code/main.py)

# [A問題](https://atcoder.jp/contests/abc384/tasks/abc384_a)

普通に、実装しました。
なんか同じような問題を見たことがあるような...

acコード(ライブラリ抜粋)

```py
n, a, b = sl()
S = s()

ans = ""

for s in S:
    if a == s:
        ans += s
    else:
        ans += b

print(ans)
```

# [B問題](https://atcoder.jp/contests/abc384/tasks/abc384_b)

あARC div2のトラウマが蘇る
400点問題のくせに水diff、普通予選とかじゃないと出ない、レベルエグいって

まあ現在のレートが更新範囲内だったら、レートの変動を受け入れる、方式でやればOK
入力例2のレートが実際のchokudaiのレートで笑った

acコード(ライブラリ抜粋)

```py
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問題](https://atcoder.jp/contests/abc384/tasks/abc384_c)

bit全探索で実装した
インデックスに対応する文字列を持っておけばすぐできました

ねえDから先に解いてた人いたけど絶対、Cのほうが簡単でしょ

acコード(ライブラリ抜粋)

```py
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問題](https://atcoder.jp/contests/abc384/tasks/abc384_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コード(ライブラリ抜粋)

```py
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問題](https://atcoder.jp/contests/abc384/tasks/abc384_e)

優先度付きキューを使って解きました。
JOIの過去問でダイクストラ法などを勉強したのと、二次予選のB問題で出てきたので覚えてました
ちなみに、二次予選のBはダイクストラのほうが簡単にできるのに、dpでバグらせ結局のとこ、70点しか取れませんでした

具体的には、キューから取り出した値が、更新されたら、そこから隣接する未訪問の場所を、キューに入れれば、できます
なお更新するときは、現在の強さに、吸収されたスライムの強さを足します

自分は、キューに入っている内容を、setに入れたのですがオーバーキルでした。

acコード(ライブラリ抜粋)

```py
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は神ゲーですね

まあ当面の間は入水目指して頑張ります。