緑によるABC391振り返り

はじめに

えーとE問題、本当に緑diffですか?
あのー僕、E問題水diffだと思って、離脱したんですけど....(こいつ、スノーシュー行って疲れてたくせに、rated参加+4完したくせに満足してねーのかよ)

結局、結果はこんな感じでした

ユーザ名 hidehico
コンテスト名 AtCoder Beginner Contest 391
順位 2358th / 11611 (top 1.96%)
パフォーマンス 1119
レーティング 874 → 901 (+27)

ていうか、2000位で、緑パフォって相当、レベル高いな

コンテスト中は、こんな感じでした

コンテスト中の流れ

開始4時間前

スノーシューに行ってくたびれて、帰宅

開始30分前

ratedで参加登録する

開始3秒

atcoder-cliで、テストケースを取得する

開始2分

Aを通す
時間がかかった理由は、強行手段でACしたから

開始9分

Bを通す
インデックス調整をミスって、時間をかけてしまった
幸い、サンプルケースが強かったので、0ペナ

開始12分

Cを通す
明らかに、得意な、クエリ系だったので、難無くACできた
3分で通して、Bでのロスをリカバリーした

開始40分

Dを通す

多分、Eは解けそうにないし、離脱した
翌日diffを確認すると、緑diffビックリ仰天、レートもそこまで上ってない、萎えた

こんな感じでした

使っているライブラリ

github
前回からの、変更点は、バグの修正だけです

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

A問題

簡潔な案を思いついたけど、バグらせたら嫌だなーと、思い、普通に書いた
無限ifよりは、簡潔に書けた

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

D = {
    "N": "S",
    "S": "N",
    "E": "W",
    "W": "E",
    "NE": "SW",
    "SW": "NE",
    "NW": "SE",
    "SE": "NW",
}
print(D[s()])

B問題

全探索した、だけど1-indexedから、0-indexedへの変換に時間がかかり、タイムロスした
すべての問題が、0-indexedだったらいいのに

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

N, M = il()
S = li(N, s)
T = li(M, s)

for a in range(1, N - M + 2):
    for b in range(1, N - M + 2):
        flag = True
        for i in range(M):
            for k in range(M):
                if S[i + a - 1][b + k - 1] != T[i][k]:
                    flag = False

        if flag:
            print(a, b)
            exit()

C問題

鳩の現在の場所と、各巣の鳩の匹数を、とっておいて
移動先の、鳩の匹数、が1だったら、ansを増やす
移動元の、鳩の匹数、が2だったら、ansを減らす

で鳩の移動の処理をやれば、ACできる

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

N, Q = il()
D = [i for i in range(N)]
L = [1] * N
ans = 0

for _ in [0] * Q:
    l = il(-1)

    if l[0] == 0:
        a = D[l[1]]

        if L[l[2]] == 1:
            ans += 1

        if L[a] == 2:
            ans -= 1

        L[l[2]] += 1
        L[a] -= 1

        D[l[1]] = l[2]
    else:
        print(ans)

D問題

diffの崖がすごい

各列の一番下にある、ブロックの高さ-現在時刻、の最大値+現在時刻が、各ブロックの答えになる
それであーだこーだやればできる

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

N, W = il()
D = defaultdict(list)
L = li(N, il)
ans = [INF] * N

for i in range(N):
    D[L[i][0]].append((L[i][1] - 1, i))

for i in range(1, W + 1):
    D[i].sort(reverse=True)


cur = 0
while True:
    flag = True
    m = 0
    l = []

    for i in range(1, W + 1):
        if len(D[i]) == 0:
            flag = False
            break

        y, ind = D[i].pop()
        m = max(m, y - cur)
        l.append(ind)

    if not flag:
        break

    for ind in l:
        ans[ind] = m + cur

    cur += m

Q = ii()

for _ in [0] * Q:
    T, A = il()

    YN(ans[A - 1] >= T)

E問題

眠すぎぎた
問題文の理解ができなかった

解説見たらDP使うみたい

最後に

順位表を見たら、消えてる人が数人いた(AI使ってたのかな?)
まあ関係ないけど

まあ眠かったし、ABCD 4完でも満足でした

:qa!