Codeforces Round #398 (Div. 2)

参加しました、結果は１完でした
とにかくBがとても難しかったというか複雑だったというか。
どっかで見切りをつけて次の問題を見てみるべきだったかも、とも思いました。
Aもいつものレベルに比べて難しく、２回もWAしてしまった。問題を正しく理解できてなかったのが要因ですが。

A.xxo
B.xxx

公式解説
Codeforces Round #398 (Div. 2) Editorial - Codeforces

A. Snacktower

Problem - A - Codeforces

停滞気味なのでさくっとコードだけ。

import heapq

def solve():
    n = int(input())
    A = [int(i) for i in input().split()]
    heap = []
    nxt = n

    for i in range(n):
        tmp = []
        heapq.heappush(heap, -A[i])
        while heap and -heap[0] == nxt:
            tmp.append(-heapq.heappop(heap))
            nxt -= 1
        print(*tmp)

if __name__ == '__main__':
    solve()

２回WA出した後で焦っていたのか無駄にheapqとか使っちゃってるのでO(Nlog(N))くらい？
こんなことをしなくても、どの数字が何番目に出てきたか、という配列を別に作ればO(N)で出来ました。

def solve():
    n = int(input())
    A = [int(i) for i in input().split()]

    app_n = [0] * (n + 1)
    for i, a in enumerate(A):
        app_n[a] = i
    
    nxt = n
    for i in range(n):
        tmp = []
        while nxt > 0 and app_n[nxt] <= i:
            tmp.append(nxt)
            nxt -= 1
        print(*tmp)

if __name__ == '__main__':
    solve()

B. The Queue

Problem - B - Codeforces

やや複雑ですがこんな感じでしょうか。計算量はO(n)かな？

def solve():
    ts, tf, t = map(int, input().split())
    n = int(input())

    if n == 0:
        print(ts)
        return None

    AT = [int(i) for i in input().split()]
    BT = [0]*n

    for i, at in enumerate(AT):
        if i == 0:
            if at > ts:
                print(ts)
                return None
            else:
                BT[i] = ts
        else:
            if at > BT[i - 1] + t and BT[i - 1] + t <= tf:
                print(BT[i - 1] + t)
                return None
            else:
                BT[i] = BT[i - 1] + t

    if BT[n - 1] + 2*t <= tf:
        print(BT[n - 1] + t)
        return None

    min_wait = float('inf')
    ans = None

    for i in range(n):
        if i > 0 and AT[i] == AT[i - 1]:
            continue
        else:
            if BT[i] - (AT[i] - 1) < min_wait and BT[i] + t <= tf:
                min_wait = BT[i] - (AT[i] - 1)
                ans = AT[i] - 1

    print(ans)

if __name__ == '__main__':
    solve()

とにかく魔の問題だった。コンテスト中もBよりCを解いた人のほうが多いくらいだった、早めに察するべきだったかも。
今見てもBよりCの方が少ない。
こういう問題をちゃんと解けるようになりたい。

Cはそもそも見てません。