Codeforces Round #636 (Div. 3)

コンテストへのリンク

バチャをした！べるさんとしふとさんとはてぃーぽったーさんとnok0さんとmedoさんとkumakumaaaaaさんとサマリ6さんと並走！

ABC3完．Aでめちゃくちゃ苦戦した．悔しい！！！！！！！！

以下問題ごとの感想とACコード．

A問題

解説見たらなんで解けなかったんだろう…という気持ちになった．

全然左辺をくくろうという気持ちにならなかったんだよな…nの約数を求めるなどしていた．本当に悔しいな． たぶんコンテストでは，20分くらいかけて2WA出してて方針に自信がないときは一回飛ばした方がよさそう．いや，飛ばすべき（ABCのBとかでこういうの来たら怖いな）．

コード

def main():
    T = int(input())
    A = [2**i-1 for i in range(2, 32)]
    for _ in range(T):
        N = int(input())
        for a in A:
            if N % a == 0:
                print(N//a)
                break


if __name__ == '__main__':
    main()

B問題

Aを飛ばして，比較的サクッと解法が浮かんだ（しかし2WA）．うーん，一つ前が解けてなくても平常心を保ちたい．

Nを2で割ったものを，さらに2で割った余りが1ならば"NO"．つまり4の倍数でないときは"NO"．これは後半の奇数のみの和を前半の和と等しくするために，後半の要素が偶数個でなければならないから． 2の倍数でn//2個適当に前半を構築し，aの要素から1引いたものでn//2-1個とaの和とbの和の差で1個の合計n//2個で後半を構築する．

コード

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        if (N//2) % 2 == 1:
            print("NO")
        else:
            print("YES")
            A = [2*i for i in range(1, N//2+1)]
            B = [a-1 for a in A[:-1]]
            B.append(sum(A) - sum(B))
            print(*A, *B)


if __name__ == '__main__':
    main()

C問題

一番わかりやすい． 正が連続するところと負が連続するところでそれぞれ数列を見て，それぞれのmaxを取ってきて和を求めればよい． alternating subsequence ってなんだ…？って読んでるとき一瞬思ったけど，交代行列とか交代級数のalternatingか～って途中で気づいた．

コード

def main():
    T = int(input())
    for _ in range(T):
        _ = int(input())
        A = [int(i) for i in input().split()]
        ans = 0
        cur_max = A[0]
        posi = True if A[0] > 0 else False
        for a in A[1:]:
            if posi:
                if a > 0:
                    cur_max = max(cur_max, a)
                else:
                    ans += cur_max
                    posi = False
                    cur_max = a
            else:
                if a < 0:
                    cur_max = max(cur_max, a)
                else:
                    ans += cur_max
                    posi = True
                    cur_max = a
        print(ans + cur_max)


if __name__ == '__main__':
    main()

D問題

バチャ後に解説AC．これ難しくないか？？？？？

問題概要

長さnの数列aと整数kが与えられる．前からi番目と後ろからi番目をペアにして，それぞれ和を計算する（）．ただし，和はある値xにしたい．xはすべてのペアで共通の値である．数列aの各要素を変更してよいとき，変更しなければいけない要素の個数は最小で何個か求めよ．ただし，数列aの要素はの範囲の整数値を取るとする（変更後も！）．

思考過程

とりあえず各ペアの和は取りたくなるので，Counter()でペアの和それぞれが何個あるか数える．どれかにできるのかな～って思ったけど，上手く計算できそうにない．困ったので解説を見た．

解法

各ペアの和xは，区間]のいずれかの値を取る．xの値を決め打ったとき，変更しなければいけない要素の個数が高速にわかると問題が解ける．

xの値を固定したときに，各ペアについて考える操作は3パターンある． 1. 変更する要素はない．すでにペアの和がxになっている． 2. 1つ要素を変更する． 3. 2つ要素を変更する．

1.は思考過程に書いたように，実際のペアの和を計算し，それぞれの和が何個あるか数えるとわかる（和xになるペアを数える）．

2.は，各ペアが取りうる和の範囲を考える．ペアの和が一番小さくなるのはのとき（値の大きい方を1に置き換えた）．一番大きくなるのは，のとき（値の大きい方をkに置き換えた）．この2つの間の和は全部作れて，あるペアが1つ要素を変更したときの取りうる和の範囲がわかった．ただしこれは要素を変更しなかったとき（0個要素を変更したとき）の和も含んでいることに注意する．そして，これを各ペアについて和を足し合わせると，和をxにしたときの要素を1個以下変更するペアの数がわかる．

1.を保存しているリストをcnt，2.を保存しているリストをSとする．それぞれについて，和をxにしたときに要素を前者なら0個，後者なら1個以下変更するペアの個数を，と書く．

すると，3.は和をxにしたときに(N//2 -)個が変更しなければいけないペアの数とわかる．

ここまで頑張ると，各xについて変更しなければいけない要素の個数はであるから，各xについてこれを計算して最小値が答え．

反省

各ペアの和の範囲は考えるべきだった．その和にできるか？みたいなのをO(1)で判定できたら和の範囲でループを回せばよい…までは思考できるようにしたかった．ここまで考察が進んだら，和xを固定したときに取りうる状態を考えたり，範囲を考えたくなる気持ちはあったので，うまくまとめあげて解法のように考えを進めていきたい．次は解きたいなあ．

コード

def main():
    from collections import Counter
    from itertools import accumulate
    T = int(input())
    for _ in range(T):
        N, K = (int(i) for i in input().split())
        A = [int(i) for i in input().split()]

        # ペアの和について，その和になるペアがいくつあるか数える
        c = Counter()
        for i in range(N//2):
            c[A[i] + A[-(i+1)]] += 1
        # ペアの要素を1つ以下変えたときに，各ペアが取りうる区間を計算
        # いもす法を使って，ペアの要素を1つ以下変更するだけで各和xにできるペアの数を計算
        S = [0]*(2*K+5)
        for i in range(N//2):
            mi = min(A[i], A[-(i+1)]) + 1
            ma = max(A[i], A[-(i+1)]) + K
            S[mi] += 1
            S[ma + 1] -= 1
        S = list(accumulate(S))

        # 各xについて変更しなければいけない数を計算．最小が答え
        ans = 3*10**5
        for x in range(2, 2*K+1):
            cur = (S[x] - c[x]) + (N//2 - S[x])*2
            ans = min(ans, cur)
        print(ans)


if __name__ == '__main__':
    main()