緑によるABC390振り返り

はじめに

前回の記事を誤投稿してしまってすみません(アホか)
github actionsのミスにより投稿されてしまいました(罪を機械になすりつけるな あとpaizaのキャンペーンでいいね稼ぎするな)

ユーザ名 hidehico
コンテスト名 AtCoder Beginner Contest 390
順位 6496th / 12572 (top 5.43%)
パフォーマンス 484
レーティング 911 → 874 (-37)

3完10ペナ、aw ＜ESC＞1000.(ドットリピートすな)、vimで入力するとおもしろいことになりますよ(wが大量に出るだけだろ)
はい、Bで少数誤差で9ペナ食らいました、そして、苦心のすえACしたコードもafter contestに見事撃墜されました
そして、終了10分前に、EをACするアイデアを思いついたものの、結局ACできませんでした、コンテスト終了後コードを書いてACすると落胆しました

コンテスト中の流れ

開始3分

1ペナ食らいつつもAをAC?

開始5分

Bで3ペナ食らう
時間の無駄だと気づき、スキップ

開始20分

CをAC

開始25分

Bで2ペナ

開始50分

Dを覗いてみるも、なかなかアイデアが、うかばす、Bに戻る
そしてEを覗くもよくわからず

開始80分

やっとBを通す

開始90分

Eを通す アイデアを思いつく

コンテスト終了

結局、EはACできず、通してたら水パフォでてたことき気づきショック

使っているライブラリ

github やっとciを直せてほっとしてます、modintを追加しました
使うのであれば、starを押して頂けるとものすごくうれしいです。qiitaのいいねの数倍ぐらい

二分探索ライブラリ

def binary_search(fn: Callable[[int], bool], right: int = 0, left: int = -1) -> int:
    while right - left > 1:
        mid = (left + right) // 2

        if fn(mid):
            left = mid
        else:
            right = mid

    return left

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

A問題

普通に全探索した
問題分を誤読して、1ペナ食らった

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

A = il()
B = list(sorted(A))

NE(A == B)


for i in range(4):
    k = i + 1
    n = A[:]
    n[i], n[k] = n[k], n[i]

    YE(B == n)

print("No")

B問題

少数誤差が大変だった

ACコード(ライブラリ抜粋)
注意: 現在はacできません

N = ii()
YE(N == 2)
A = il()

for i in range(N - 1):
    B = [A[-1]]
    a = A[i + 1] / A[i]

    for _ in [0] * (N - 1):
        B.append(B[-1] / a)

    YE(A == list(reversed(B)))

print("No")

C問題

すぐ解法が思いついたので良かった(当然だろ)
黒いマスのxの最大値、最小値、yの最大値、最小値をgetして

先程のxの最小値 - xの最大値とyの最小値 - yの最大値、で二重ループ回して、そのどれか一つでも、白ならNo、そうでないなら、Yesを出力すればいい

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

H, W = il()
S = li(H, s)

ax, bx = 0, H
ay, by = 0, W

for i in range(H):
    for k in range(W):
        if S[i][k] != "#":
            continue

        ax = max(ax, i)
        bx = min(bx, i)
        ay = max(ay, k)
        by = min(by, k)

for i in range(bx, ax + 1):
    for k in range(by, ay + 1):
        NE(S[i][k] == ".")

print("Yes")

D問題

再帰関数だと思ったけど、よく分からなっかた
青diffでびっくりした

E問題

dpだと思ったけど、偽考察が走り、ACできなかった
残り10分で、ナップサック+二分探索で、ACできる事に気づき、コードを書くもACできなかった

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

N, X = il()

D = defaultdict(list)

for _ in [0] * N:
    V, A, C = il()
    V -= 1
    D[V].append((A, C))

DP = []

for V in range(3):
    dp = create_array2(len(D[V]) + 1, X + 1, -INF)
    dp[0][0] = 0

    for i in range(len(D[V])):
        A, C = D[V][i]
        for x in range(X + 1):
            dp[i + 1][x] = max(dp[i + 1][x], dp[i][x])

            if x + C > X:
                continue

            dp[i + 1][x + C] = max(dp[i + 1][x + C], dp[i][x] + A)

    DP.append(dp[-1])


def check(mid):
    cos = 0

    for V in range(3):
        for i in range(X + 1):
            if DP[V][i] >= mid:
                cos += i
                break
        else:
            break
    else:
        return False if cos > X else True

    return False


print(binary_search(check, INF, 0))

最後に

書いてるとき泣きそうになりました
ナップサックdpのライブラリを用意しとけばよかったと痛感しました
まあ言い訳ですけど、だけどこの教訓を次に生かしたいです
ちなみにABCE 4完最遅でも水perfでるらしいです

:qa!