Xenous の精進記録

AtCoder関連他、学習したことの記録です。

ABC203 参加記録

  • 3完0ペナ 97分でした
  • E問題解けたと思いましたが、、TLE で3完になりました。しばらく一度に提出するのを控えようと思います。

A - Chinchirorin

if 文を使って条件を列挙し、問題文の通りに判定します。

a, b, c = map(int, input().split())
if a == b: print(c)
elif a == c: print(b)
elif b == c: print(a)
else: print(0)

B - AtCoder Condominium

部屋番号の整数を実際に構成して、足し合わせて答えとします。  1 \leq N, K \leq 9 なため、計算量は余裕です。

N, K = map(int, input().split())
ans = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        ans += i*100 + j
print(ans)

C - Friends and Travel costs

 10^{100} が大きいのでここまで行き着くかまずは考えてみます。 最初に  10^{9} 円を持ち、 2 \times 10^{5} 人から  10^{9} 円をもらう場合でも  2 \times 10^{14} くらいで終わります。よって最後に到達することは考えなくて良さそうです。

友達からもらうお金は、辿り着ける村の順番にあらかじめソートします。 順に見ていく中で、辿り着いたときに負の値になると、途中でお金が足りなくなったと判断します。

N, K = map(int, input().split())
l = [(0, 0)]
for _ in range(N):
    A, B = map(int, input().split())
    l.append((A, B))
l.sort(key=lambda x: x[0])
i = 0; 
for a, b in l:
    if K < a - i:
        print(i + K)
        return
    K -= a - i
    i += a - i
    K += b
print(i + K)

D - Pond

本番では方針さえ全然思いつきませんでした。二分探索で答えを決め打ち、0 1 に変換する方針の問題は前にも出てきていたのでちゃんと覚えておきたい典型です。

マスの行列の大きさの最大が  800 なため、各マスを探索する分には  O(N^{2}) で十分間に合います。そこから中央値の探索をすることを考えます。

中央値は値そのものよりも順位を見る統計量です。  K\times K の区画を動かすことを考えたとき、元々の中央値の値より小さい値(もしくは大きい値)がいくつ抜けていくつ入ってきたかを考えようとしました。この場合、行または列で少なくとも  O(K) の確認を行う必要があり、最終的に  O(N^{2}K) になります。 大体  6\times 10^{7} くらいになるのでそこそこ厳しいです。また、同じ値が出入りしたときの更新の方法も簡単ではなさそうです。

答えを二分探索で決め打ちしたとき、全てのマスについて、その決め打ちした値以上か?それとも未満か?を 0 1 で表現できます 。  K \times K の区画で、1 の数が  \lfloor\frac{K^{2}}{2}\rfloor +1 個以上あれば、その値は中央値になる可能性があります。

この確認を全ての区画( (N-K)^{2} 個の区画)で行って、少なくとも一つ中央値になる可能性があるとなれば、二分探索の上限を小さくでき、そうでないなら下限を大きくします。

 K \times K の区画で 0 1 の個数の集計をそのままやると、区画ごとに  O(K^{2}) かかり TLE ですが、二次元累積和を使えば前処理に  O(N^{2}) 、区画の 0 1 の個数集計は  O(1) で答えられます。

二分探索は  O(\log{a_{\max}}) で済むので、全体で  O(N^{2}\log{a_{\max}}) で解けます。

D問題 提出コード

def accumulate_2d(field:list, H:int, W:int) -> list:
    """
    二次元累積和を計算する
    """
    res = [[0]*(W+1)]
    for i in range(H):
        tmp = field[i].copy()
        res.append([0] + tmp)
    for i in range(1, H+1):
        for j in range(1, W+1):
            res[i][j] += res[i-1][j] + res[i][j-1] - res[i-1][j-1]
    return res


def f(n):
    global A, N, K
    # 0 1 判定
    B = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            B[i][j] = A[i][j] >= n
    # 累積和テーブル
    field = accumulate_2d(B, N, N)
    # 各区画で個数計算
    l = K; r = K
    for k in range(N-l+1):
        for j in range(N-r+1):
            tmp = field[l+k][r+j] - field[k][r+j] - field[l+k][j] + field[k][j]
            if tmp < K**2//2+1: 
                # ある区画でより小さい値が中央値になる
                return False
    return True


def main():
    global A, N, K
    N, K = map(int, input().split())
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        A.append(tmp)
    
    R = 10**9+1 # right side
    L = 0 # left side
    while True:
        if L+1 >= R:
            break
        mid = (L+R)//2
        t = f(n=mid) # boolean function
        if t: L = mid # True
        else: R = mid # False
    ans = L
    print(ans)


if __name__ == "__main__":
    main()

E - White Pawn

本番で、解き方は割とすぐ思いつきましたが、TLE を解消できませんでした。

黒ポーンの配置の制約から、境界については考える必要はなさそうです。 サンプルにあるようなケース以外にも、特に下記の場合の動きを正しく管理するにはどうするか?を考えます。

f:id:Xenous:20210606132216p:plain
確認した自作テストケース

黒のポーンが置かれている位置についてソートし、左端から順に見ていきます。各黒ポーンの時点で、到達できる  y 軸の値を集合 (この集合を  S とおきます) で管理します。

まず、新しく移動可能になる  y 座標について考えます。このポーンの  y 座標を  q とおくと、 q S に含まれておらず、 q+1 または  q-1 S に含まれているなら、 S q を追加することができます。

次に、移動可能だった場所が移動できなくなるパターンを考えます。これは 「 q+1 q-1 S に含まれていない」かつ「 qS に含まれている」が成り立つときです。このとき  q S から削除します。

以上で要素の管理のルールは表現できました。あとはこれを間に合うように更新させていきます。

黒ポーンをソートして順に見ていくので、ここまでで  O(M\log{M}) かかります。要素の追加と削除ですが、set 型の union()difference() を使用すると、結合させる集合どうしの大きさに比例して計算量が大きくなり、 O(MN\log{M}) となって間に合いません。

追加と削除の要素は高々ポーンの数しか出てこないことを考えると、直接要素を addremove したほうが高速でした(具体的な計算量はわかりませんでした)。

E 問題 提出コード

def main():
    N, M = map(int, input().split())
    dots = dict()
    for _ in range(M):
        X, Y = map(int, input().split())
        if X not in dots: dots[X] = set([])
        dots[X].add(Y)

    X = list(dots.keys())
    X.sort()
    status = set([N])
    for x in X:
        yset = dots[x]
        able = set([])
        stop = set([])
        for y in yset:
            if y-1 in status or y+1 in status and y not in status: able.add(y)
            if y in status and y-1 not in status and y+1 not in status: stop.add(y)
        for a in able:
            status.add(a)
        for s in stop:
            status.remove(s)
    ans = len(status)
    print(ans)


if __name__ == "__main__":
    main()