メインコンテンツへスキップ

[Python] ABC473 A~Fざっくり解説

    (今回は解法が思いつきやすい方だった気がします。方針はすぐ立てられるものが殆どでしたが、何故か酒を煽っていたのでA~E完で頭が回らなくなって断念♡(後半になるほどWAで引っかかりまくって笑ってました) そんな人による解説です。参考になれば幸いです。)

    A - Second Half Sum (問題)

    配列長が偶数の整数列AAが与えられるので、後半部分の総和を求めるだけです。

    N = int(input())
    A = list(map(int, input().split()))
    print(sum(A[N//2::]))


    B - Old Maid (問題)

    高橋君が持っている任意の整数が書かれているカードNN枚のうち、
    [1]書かれている数字の被っているカードがない
    [2]書かれている数字の被っているカードが奇数枚ある

    の2通りの場合で、書かれている整数の値を足し合わせるだけです。

    バケットの問題として解く、もしくは検索がO(1)O(1)のsetを用意して、被りがあればsetから消す、なければ入れるを繰り返してsumを取れば解けます。

    //setを使った解法
    N = int(input())
    A = list(map(int, input().split()))
    pool = set()
    for i in A:
      if not i in pool:
        pool.add(i)
      else:
        pool.discard(i)
    print(sum(pool))
    //バケットとして解く
    N = int(input())
    A = list(map(int, input().split()))
    bucket = [0 for _ in range(100)]
    for i in A:
      bucket[i-1] += 1
    ans = 0
    for i in range(100):
      if bucket[i] % 2 != 0:
        ans += i+1
    print(ans)


    C - Change Schools (問題)

    これもバケット問題として解いて間に合います。
    (問題の性質がB問と似ているので苦戦することなく解けた人が多いのではと思います)

    N, K = map(int, input().split())
    bucket = [0 for _ in range(K)]
    max_c = 0
    
    for i in map(int, input().split()):
      bucket[i-1] += 1
      max_c = max(max_c, bucket[i-1])
    
    ans = 0
    for i in bucket:
      if max_c <= i+1:
        ans += 1
    print(ans)


    D - Coefficient Stair (問題)

    非負整数からなる長さN(1≦N≦10)N(1≦N≦10)の列AAがある。この数列の各インデックスと各要素を掛け合わせた総和がKKとなり得る数列AAの要素を辞書順で小さい方から出力する問題です。
    辞書順で小さい方からという指定がされているので、数列AAのインデックスの小さいものから取り得る要素の最小値AiA_iを0から決めつけて再帰を回していけば良いです。
    ※print(*A)と書くとTLEするので注意

    def findA(i, k, A):
      if i == N-1:
        if(K-k) % N == 0:
          A[i] = (K-k)//N
          print(' '.join(str(a) for a in A))
        return
      for x in range(0, (K-k)//(i+1)+1):
        A[i] = x
        findA(i+1, k+x*(i+1), A)
    
    N, K = map(int, input().split())
    A = [0 for _ in range(N)]
    findA(0, 0, A)


    E - K-Divisible Subarrays (問題)

    個人的にこのような問題はパッと見何をすればいいか分からないことが多いのですが、なんとなくDPのような気がしました。
    区切った配列の和がmodK=0modK=0となるように沢山区切ってその最大値を求める問題ですが、どのように丁度Kで割り切れる配列を作るのかで時間がかかりました。
    まず配列AAの頭から累積和を取り、そのmodKmodKの値を記録します。そして同じmodKmodKの値を取るなら、その両端で区切った配列の総和は確かにKで割り切れます。

    N=6,S=4N=6, S=4
    3,5,2,2,4,73, 5, 2, 2, 4, 7
    累積和のmodK配列は3,0,2,0,0,33, 0, 2, 0, 0, 3となる
    modK配列に含まれる要素のうち一番多い値(今回は0)で、区切る左の値が0、かつ0を1つ含むように配列を区切るときスコアが最大値になる。
    つまり、(3,5),(2,2),(4),(7)(3, 5), (2, 2), (4), (7)のスコア3が最大値。
    ただ配列の左側にmodK=amodK=a、配列の右側にmodK=bmodK=bが多く存在する場合、途中で乗り換えて分割した方がスコアが高くなるのは自明。

    これをコードに落とし込めばいいので、
    [1] 累積和を取りながらmodK配列を作る
    [2]配列AiA_iにおけるスコア最大値をdp[i]dp[i]として、i<ji<jとなるAjA_jにおいて、modKがAjA_jと等しくなる点を数えて仮スコアを出し、dp[i]+仮スコアdp[i] + 仮スコアが最大値であればdp[j+1]dp[j+1]に更新する。

    dpを行なっているときに毎回dp[j]dp[j]の最大値を求め直すのは無駄なので、キーをmodKの値としたmax_vで管理しています。

    N, K = map(int, input().split())
    k = []
    sum = 0
    for i in map(int, input().split()):
      sum += i
      k.append(sum % K)
    
    dp = [0 for _ in range(N+1)]
    max_v = {}
    count = {}
    count[0] = 1
    max_v[0] = 0
    
    for i in range(N):
      b_j1 = count.get(k[i], 0)
      if k[i] in max_v:
        opt = max_v[k[i]] + b_j1
        dp[i+1] = max(dp[i], opt)
      else:
        dp[i+1] = dp[i]
      max_v[k[i]] = max(max_v.get(k[i], float('-inf')), dp[i+1] - b_j1)
      count[k[i]] = b_j1 + 1
    print(dp[N])


    Fも軽く解きたかったですが、無理そうです。
    ではまたABC474で。

    F - A/AB Insertion

    遅延セグ木なんてまだ知らない人間が通りますよ。
    調べてみるとなんと知っていればそこまで難しくない問題のようです。というか典型的な遅延セグ木の区間和の問題みたいですね。

    遅延セグ木とは…
    根に配列SSを持ち、末端の葉には配列SSの要素単体が格納されています。これを二分木の要領で葉から根の前までを順に足し合わせていくと根の配列になります。(ここまではセグ木)
    末端の葉の要素に変更が生じた場合、本来であればすぐに上に伝えて更新し直す所を、更新する必要が出てくるまでこのような変更があったことだけを記録して後回しにする方法です。
    セグ木が区間和、区間最大・最小値を求めるのに強いデータ構造で、更新があるため遅延セグ木という方法が最適になるようです。

    そして遅延セグ木の実装にはかなり長いコードを書く必要があるわけですが、atCorder ライブラリの中に使っても大丈夫なチートコードがあるみたいです。
    Pythonの遅延セグメントツリーのチートシート【AtCoder】 #Python3 - Qiita

    ということで軽く考察。
    まずA,ABで組み合わせて特定の文字列を作れるか否かを判定しなければならないですが、これはAを+1、Bを-1とした時にその総和が0以上である必要があります。これは文字を組み立てる途中にも適用されることなので、セグ木で組み立てていくときに出来上がるすべての文字列に対して0以上が成り立てばよいです。また文字列の左端がBの場合は省きます。
    つまりセグ木でA,Bをそれぞれ1,-1として入れてその総和を管理、またその最小値も記録します。そして末端の葉が変更されたら一旦先延ばしにする遅延セグ木にすることで効率的に求めることが出来るという事です。
    それで実装してみたのがこちら。

    from atcoder.lazysegtree import LazySegTree
    import sys
    
    INF = 1 << 30
    ID = None 
    
    def op(ele1, ele2):
        sum1, min1 = ele1
        sum2, min2 = ele2
        return (sum1 + sum2, min(min1, sum1 + min2))
    
    e = (0, INF)
    
    def mapping(func, ele):
        if func == ID:
            return ele
        if func == 1:
            return (1, 1)
        else:
            return (-1, -1)
    
    def composition(func_upper, func_lower):
        if func_upper == ID:
            return func_lower
        else:
            return func_upper
    id_ = ID
    
    input = sys.stdin.readline
    N = int(input())
    S = input()
    
    s = []
    for i in S:
        if i == "A":
            s.append((1, 1))
        else:
            s.append((-1, -1))
    seg = LazySegTree(op, e, mapping, composition, id_, s)
    
    Q = int(input())
    
    for _ in range(Q):
        q = input().split()
        if int(q[0]) == 1:
            idx = int(q[1]) - 1
            char = q[2]
            val = 1 if char == "A" else -1
    
            seg.apply(idx, idx + 1, val)
            
        elif int(q[0]) == 2:
            l = int(q[1]) - 1
            r = int(q[2])
            total_sum, min_pref = seg.prod(l, r)
            
            print("Yes" if total_sum >= 0 and min_pref >= 0 else "No")

    ただPythonでは、タプルで処理するのが時間がかかる?らしく(定数倍がそもそも大きい)これに工夫しないとTLEになってしまいます。正直どうしたらいいのか分からないですね…また解決したら書きます。

    解決しました。普通に勘違いして謎の遅延セグ木を実装していました。
    区間加算かつ区間最小値を取ってこれる遅延セグ木で解けばいいので、別にタプルを使わずに書けますね。
    以下実装コードです。(pypyで出すとTLEしません、てか前のコードもpypyだったらTLEしないやんけ~~~泣 無駄に2通り作った人になりました。)

    from atcoder.lazysegtree import LazySegTree
    
    INF = 1 << 63
    
    def op(ele1, ele2):
        return min(ele1, ele2)
    
    def mapping(func, ele):
        return func + ele
    
    def composition(func_upper, func_lower):
        return func_upper + func_lower
    
    e = INF
    id_ = 0
    
    # TODO (初期リストlst)
    seg = LazySegTree(op, e, mapping, composition, id_, lst)
    N = int(input())
    S = input()
    
    s = []
    for i in S:
        if i == "A":
            s.append(1)
        else:
            s.append(-1)
    
    Q = int(input())
    for _ in range(Q):
        q = list(input().split())
    
        if q[0] == "1":
            i = int(q[1]) - 1
            if S[i] == q[2] : continue
            if q[2] == "A":
                seg.apply(i, N, 2)
            else:
                seg.apply(i, N, -2)
            S[i] = q[2]
        else:
            l = int(q[1]) - 1
            r = int(q[2])
    
            m = 0
            if l > 0 : m = ls.get(l-1)
            print("No" if seg.prod(l, r) < m else "Yes)
    
    

    一応いろんな人の回答を見漁って書いたのがこのコードなので、自分が書いたとは言いにくいのですが、こちらの方がシンプルにまとまっていて良いですね。最小値を区間で求めて、A,Bの置き換えを2の加算減算で実装するのは思いつかなかったので良い学びになりました。

    ではまたABC474で。



    あなたへのおすすめ