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

はじめに

投稿遅れてすんません
点数見た時点で荒れると思っていたけどBの問題文がすごい複雑で結局C問題を先に解いてあとでBを解いた
Bの実装が結構重かった(茶色の感想)
初めて自分用ライブラリを導入してみたけど使い心地は良かった
今後も使おうと思う(今言わなくていい)

使っているライブラリ

def pow(x: int, n: int, t: int = 1):
    if t == 1:
        ans = 1
        while n:
            if n % 2:
                ans = ans * x
            x = x * x
            n >>= 1
        return ans
    ans = 1
    while n:
        if n % 2:
            ans = (ans * x) % t
        x = (x * x) % t
        n >>= 1
    return ans


def is_prime(n: int) -> bool:
    if n == 1:
        return False

    i = 2
    s = n**0.5

    while i < s:
        if n % i == 0:
            return False

        i += 1

    return True


INF = 10**18
lowerlist = list("abcdefghijklmnopqrstuvwxyz")
upperlist = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

それじゃ一問ずつ感想書きますか

A問題

まあ150点ってだけでいつものAと同じ感じだった
最後に押されたときの時間を変数においておいて
あとは問題文の通り実装した
PythonでのACコード

(
    N,
    C,
) = list(map(int, input().split()))
A = list(map(int, input().split()))
r = 1
t = A[0]

for i in A[1:]:
    if i - t >= C:
        r += 1
        t = i

print(r)

解説URL

B問題

最初にも話したように実装がきつかった
そして問題文をところどころ見落とし実装ミスした
制約をすごい見落としよくわからなくなりCへスキップCをACしてからBをACした

PythonでのACコード↓↓(ライブラリ抜粋)
コード全文(2000byteもあります)

N, Q = list(map(int, input().split()))
ans = 0
l = 1
r = 2

for _ in [0] * Q:
    H, T = input().split()
    T = int(T)

    if H == "L":
        tl = l
        c = 0
        mode = False
        while tl != T:
            if mode:
                tl -= 1
                c += 1
            else:
                if tl + 1 == r or (tl == N and r == 1):
                    c = 0
                    tl = l
                    mode = True
                else:
                    tl += 1
                    c += 1

            if c > 0:
                if mode:
                    if tl == 0:
                        tl = N
                else:
                    if tl == N + 1:
                        tl = 1

        l = T
        ans += c
    elif H == "R":

        tr = r
        c = 0
        mode = False
        while tr != T:
            if mode:
                tr -= 1
                c += 1
            else:
                if tr + 1 == l or (tr == N and l == 1):
                    c = 0
                    tr = r
                    mode = True
                else:
                    tr += 1
                    c += 1
            if c > 0:
                if mode:
                    if tr == 0:
                        tr = N
                else:
                    if tr == N + 1:
                        tr = 1

        r = T
        ans += c

print(ans)

解説URL

C問題

AとBどちらもソートして二分探索した
計算量は難解を極める
僕はどちらかというとオブジェクト指向、関数型も書けるが競プロ始めてから意識しないと手続き型になってしまい　判定関数も作っていないゴミコードですがよろしければ見てください

PythonによるACコード(ライブラリ抜粋)
全文

import bisect

N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))

r = 0

for i in range(N - 1):
    if A[i] <= B[i]:
        continue
    else:
        r += 1

if r >= 1:
    print(-1)
    exit()

ng, ok = (0, A[-1])

while ok - ng > 1:
    mid = (ng + ok) // 2
    TB = B.copy()
    bisect.insort(TB, mid)
    r = 0
    for a, b in zip(A, TB):
        if a <= b:
            continue
        else:
            r += 1
            break

    if r:
        ng = mid
    else:
        ok = mid

print(ng + 1)

解説URL

D問題

閉路なにそれ状態で結局ACできなかった
BFSの線までは言っていたがそれを1..Nすべて試す方法を思いついたが計算量が$O(N(N+M))$になってしまうため諦めた
最後までACできなかった

解説見たらBFSで頂点1に戻って来るだけで良かったらしい

解説URL

最後に

灰色に戻らなくてよかった
レートは30ぐらい上がりました