緑による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](https://github.com/hidehic0/library) やっとciを直せてほっとしてます、modintを追加しました
使うのであれば、starを押して頂けるとものすごくうれしいです。~~qiitaのいいねの数倍ぐらい~~

### 二分探索ライブラリ
```py
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問題](https://atcoder.jp/contests/abc390/tasks/abc390_a)
普通に全探索した
問題分を誤読して、1ペナ食らった

ACコード(ライブラリ抜粋)
```py
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問題](https://atcoder.jp/contests/abc390/tasks/abc390_b)
少数誤差が大変だった

ACコード(ライブラリ抜粋)
注意: 現在はacできません
```py
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問題](https://atcoder.jp/contests/abc390/tasks/abc390_c)
すぐ解法が思いついたので良かった(当然だろ)
黒いマスのxの最大値、最小値、yの最大値、最小値をgetして

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


ACコード(ライブラリ抜粋)
```py
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問題](https://atcoder.jp/contests/abc390/tasks/abc390_d)
再帰関数だと思ったけど、よく分からなっかた
青diffでびっくりした

# [E問題](https://atcoder.jp/contests/abc390/tasks/abc390_e)
dpだと思ったけど、偽考察が走り、ACできなかった
残り10分で、ナップサック+二分探索で、ACできる事に気づき、コードを書くもACできなかった

ACコード(ライブラリ抜粋)
```py
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!