緑コーダーによるABC385振り返り

# 初めに

https://qiita.com/hidehic0/items/0af9925dfc64575e8554

~~ねえいいねください 色変記事なのに全然伸びない~~(自分の責任だろ)

取り乱してすいません

あと少し投稿が遅れてしまってすいません
スノーボード行って、記事を書く気力がなく、このような結果になりました
そして虚無埋めをする気力もなくstreakを切らしました

<details><summary>初スノボの記録</summary>
母と二人で行きました。
母はスキーをやってます。
鹿島槍が一番レッスン代が安いのでそちらに行った記録です。
鹿島槍ガーデン(釣り堀です　-6度近くあるのにおっさんがたくさんいた)の天気予報だと、雪はふらない予報だったのですが早速オリンピック道路で、雪が降ってきて、それも道路ガッチガチに凍っていました。
波乱の予感がします

スキー場に行く山道は結構雪が降っていて、こりゃコンディション悪いと確信しました

スキー場に到着し、スリップした2躯の軽が帰るのを見届けると、シーズン券(15000円の共通券)を受け取り、スキー学校の受付を済ませてレッスンが始まりました。

プライベートレッスンの四時間コースで、新雪がすごかったけど、ある程度滑れるようになりました。

駐車場へ言ったら、雪が20センチぐらい積もっていて、かき出すのが大変でした
駐車場は-7度ぐらいで寒かったです。

意外と順調に駐車場からは帰れて無事帰宅しました。(車は4~5回ぐらいエンストしてました マニュアル車なので)

すみませんスノボ全然関係ありませんでしたね、ごめんなさい
</details>

コンテスト結果は、4完　水perf 落茶回避でした
AJLのランキング上昇が楽しみです。

コンテスト前 手がかじかんで動かなかったので、寿司打やりました

コンテスト中の流れとしては
ABは瞬殺、Cは一見$O(N^3)$に見えましたが、実装してみたら計算量が$O(N^2)$っぽく簡単にACできました。
ここまで1ペナ 10分　たしかこれだけでperf 1000は出るみたいです
Dは二分探索+imos法でACしました。

そんじゃ、1問ずつ感想書きますか


**使っているライブラリ**

レポジトリを変えました
unittestとか実装しようと思ったけど、とりあえず今度やります。

[github](https://github.com/hidehic0/library/tree/main)

# [A問題](https://atcoder.jp/contests/abc385/tasks/abc385_a)
普通に、条件分岐して、解きました

やっぱりYesNo関数必要かな

ACコード(ライブラリ抜粋)
```py
A, B, C = il()

if A + B == C or B + C == A or A + C == B or (A == B and B == C):
    print("Yes")
else:
    print("No")
```

# [B問題](https://atcoder.jp/contests/abc385/tasks/abc385_b)
動けるのであれば、フラグを立てて、動く
動けなかったら、そのまま

その後、フラグが立っている、かつ、家がある場合の数の、総和を出力すればいい
でxとyも変数に取っておけばいいから、簡単

ACコード(ライブラリ抜粋)
```py
H, W, X, Y = il()
X -= 1
Y -= 1
S = li(H, s)

T = s()
used = create_array2(H, W)

for t in T:
    nx, ny = X, Y
    match t:
        case "U":
            nx -= 1

        case "D":
            nx += 1
        case "L":
            ny -= 1
        case "R":
            ny += 1

    if S[nx][ny] != "#":
        X, Y = nx, ny
        used[X][Y] = True

ans = 0
for i in range(H):
    for k in range(W):
        if S[i][k] == "@" and used[i][k]:
            ans += 1

print(X + 1, Y + 1, ans)
```

# [C問題](https://atcoder.jp/contests/abc385/tasks/abc385_c)
間隔と始点を全探索して、始点からループを回して、ループを回した回数の最大値を求めればいいです

計算量が$O(N^2)$になる理由の考察は、大体ループが回っている量が$O(N^2)$ぐらいだからだと思います

一度競技プログラミング最高の瞬間を、出してしまったものの、すぐバグに気づいてACしました

![スクリーンショット 2024-12-23 115826.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3889080/fb0b9ac7-83dc-8b70-a9b6-fd55a1f0b33e.png)

```py
N = ii()
H = il()
ans = 1

for i in range(1, N):
    for start in range(N - i):
        count = 0
        t = H[start]

        for k in range(start, N, i):
            if t == H[k]:
                count += 1
            else:
                break

        ans = max(count, ans)

print(ans)
```

# [D問題](https://atcoder.jp/contests/abc385/tasks/abc385_d)
そのx座標とy座標それぞれにdefaltdictを作って、それをソートの中身をすべてソートします。
そしてimos法用の配列を、x座標とy座標それぞれに作成します。
そして各クエリごとに、二分探索すればOK

最後にimos法のために用意しておいた配列に累積和を取って、それが1以上だったら、setに入れます。
あとは、現在地とsetの長さを入れればOKでした。

公式解説は僕のコードより全然エレガントでした(そりゃそーだ)

まあいつものクソコードよりは綺麗にできた気がします

ACコード(ライブラリ抜粋)
```py
N, M, x, y = il()
H = defaultdict(list)
W = defaultdict(list)
l = set()
ts = set()

for _ in [0] * N:
    X, Y = il()
    ts.add((X, Y))
    H[X].append(Y)
    W[Y].append(X)

UH = defaultdict(list)
UW = defaultdict(list)

for tx in H.keys():
    H[tx].sort()
    UH[tx] = [0] * (len(H[tx]) + 1)

for ty in W.keys():
    W[ty].sort()
    UW[ty] = [0] * (len(W[ty]) + 1)


def bis_y(a, b, tx):
    a, b = min(a, b), max(a, b)
    if len(H[tx]) == 0:
        return
    if H[tx][0] > b or H[tx][-1] < a:
        return

    l = bisect.bisect_left(H[tx], a)
    r = bisect.bisect_left(H[tx], b)
    UH[tx][l] += 1
    UH[tx][r] -= 1


def bis_x(a, b, ty):
    a, b = min(a, b), max(a, b)
    if len(W[ty]) == 0:
        return
    if W[ty][0] > b or W[ty][-1] < a:
        return

    l = bisect.bisect_left(W[ty], a)
    r = bisect.bisect_left(W[ty], b)
    UW[ty][l] += 1
    UW[ty][r] -= 1


for _ in [0] * M:
    D, C = sl()
    C = int(C)

    match D:
        case "U":
            bis_y(y, y + C, x)
            y += C

        case "D":
            bis_y(y, y - C, x)
            y -= C

        case "L":
            bis_x(x, x - C, y)
            x -= C

        case "R":
            bis_x(x, x + C, y)
            x += C

    if (x, y) in ts:
        l.add((x, y))

for tx in H.keys():
    t = list(accumulate(UH[tx]))
    for i in range(len(H[tx])):
        if t[i] >= 1:
            l.add((tx, H[tx][i]))

for ty in W.keys():
    t = list(accumulate(UW[ty]))
    for i in range(len(W[ty])):
        if t[i] >= 1:
            l.add((W[ty][i], ty))

print(x, y, len(l))
```

# 最後に
やっぱりD問題の二分探索使う系の緑diffはめんどくさいですね

レートは50ぐらい上がりました
半年後ぐらいには入水したいです。

最後まで見ていただきありがとうございました。