緑によるABC393振り返り

はじめに

ユーザ名 hidehico
コンテスト名 AtCoder Beginner Contest 393
順位 4033rd / 12397 (top 32.53%)
パフォーマンス 840
レーティング 943 → 933 (-10)

すげー微妙だなー(最大公約数にやられたやつ(僕)に言われたくないなー)
えーはい、Dで躓き、Eにまともに当りにいったためです、Fに行けばよかったなー(タラレバ)
ABCD4完、3ペナでした

コンテスト中どうだったか

開始3秒

acc newを実行する

開始2分

なんか時間かかったけど、Aを通す

開始4分

こっちも時間かけたけど、Bを通す

開始7分

diff逆転かと思いきや、全然簡単で、Cを通す

開始44分

3ペナ食って、Dを通す

開始45分

Eが最大公約数、Fは、セグ木か、dp、それともセグ木dp、どうしよう
Fは難しそうだったので、Eを解きにいく

開始1時間40分

そのまま時間が過ぎ去り、コンテスト終了
泣きそうになりました

使っているライブラリ

最近は、余り追加してません

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

A問題

簡単だったけど、時間がかかった

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

a, b = sl()

if "fine" == a and "sick" == b:
    print(3)
elif "sick" == a and "fine" == b:
    print(2)
elif "sick" == a and "sick" == b:
    print(1)
else:
    print(4)

B問題

三重ループのB問題って出るんだ

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

S = s()
ans = 0

for a in range(len(S) - 2):
    for b in range(a + 1, len(S) - 1):
        for c in range(b + 1, len(S)):
            if b - a == c - b and S[a] == "A" and S[b] == "B" and S[c] == "C":
                ans += 1

print(ans)

C問題

一見難しそうだけど、グラフ用語を覚えとけば、問題なかった
あとset使わないとACできない(コーナケースがいくつも考えられる)

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

N, M = il()
L = [set() for _ in [0] * N]

ans = 0

for u, v in li(M, il, -1):
    if u == v:
        ans += 1
        continue

    if v in L[u] or u in L[v]:
        ans += 1
        continue

    L[u].add(v)
    L[v].add(u)

print(ans)

D問題

累積和と和の公式使って、解いた
言語化するのが難しいけど、マスを固定して、各マスの答えの最小値を、高速に求めればいいと思い累積和を使った

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

N = ii()
S = s()

AC = [0]
BC = [0]
L = []

for i in range(N):
    if S[i] == "1":
        AC.append(AC[-1] + i)
        BC.append(BC[-1] + 1)
        L.append(i)
    else:
        AC.append(AC[-1])
        BC.append(BC[-1])

ans = INF

for i in L:
    acos = ((i * BC[i]) - AC[i]) - simple_sigma(BC[i])
    bcos = ((AC[N] - AC[i + 1]) - (i * (BC[N] - BC[i + 1]))) - simple_sigma(
        BC[N] - BC[i + 1]
    )

    ans = min(ans, acos + bcos)

print(ans)

E問題

そもそも、どうやるかが分からなかった
検索して、いろいろ考えたけど無理だった

F問題

DPかセグ木だと思ったけど、残り2分で、TLEするDP解を思いついたが高速化するまで至らなかった

最後に

もっと精進しなきゃなーと実感しました(逃げずに、数学系問題考察するとか)

以上です