Codeforces Round #661 (Div. 3)

f:id:ntk_ta01:20200814212941p:plain バチャをした．ABCD4完（３ペナ）．AとDは正解の考察に行くまでに時間がかかった．問題を上手に整理しつつ，もっと早く正確に解法にたどり着きたい．

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

A問題

数列が与えられて，値の差の絶対値が1以下のペアのうち，小さい値を取り除く操作が可能．可能な限り操作して，数列の要素を1つにできるか判定する問題．

誤読していたのもあり，最初は一つでもほかの要素との差が全て2以上になる要素があったらダメでそれ以外はOKかな～みたいな全探索を書いて1WA．これは"1 1 3 3"で"YES"になってしまう（正解は"NO"）．

正しくは，ソートして隣り合う値の差の絶対値が全て1以下になっていれば"YES"で，そうでなければ"NO"．

コード

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = [int(i) for i in input().split()]
        A.sort()
        if N == 1 or all(A[i+1] - A[i] <= 1 for i in range(N-1)):
            print("YES")
        else:
            print("NO")


if __name__ == '__main__':
    main()

B問題

数列が2個与えられて，条件を満たすために必要な操作の最小回数を求める問題．条件は， $a_i = a_j (^\forall i,j)$ と $b_i = b_j (^\forall i,j)$ ．同じ $i$ 番目については， $a_i \neq b_i$ でも $a_i = b_i$ でもよい．操作は $a_i$ を1つ減らすか， $b_i$ を1つ減らすか， $a_i$ と $b_i$ を1つずつ減らすかの三つ． $a_i$ も $b_i$ も0より少なくはできない．

これは方針がパッと立って，減らすことしかできないのですべての値をそれぞれの数列の最小値にすればいい． $a_i$ と $b_i$ を同時に減らす操作があるので， $i$ 番目の要素に必要な操作回数は $A_i - (Aの最小値)$ と $b_i - (Bの最小値)$ の大きい方．

最近似たような操作をしたなあ（これより難しかったし，コンテスト中に解けなかったけど）．

コード

def main():
    Tquery = int(input())
    for _ in range(Tquery):
        N = int(input())
        A = [int(i) for i in input().split()]
        B = [int(i) for i in input().split()]
        ans = 0
        minA = min(A)
        minB = min(B)
        for i in range(N):
            need = max(A[i] - minA, B[i] - minB)
            ans += need
        print(ans)


if __name__ == '__main__':
    main()

C問題

n個の値があって，できるだけ多くペアを作りたい．すべてのペアの値の和は，一定の値 $s$ にしなければならない．このときのペア数の最大値を求める問題．

制約を見ると方針が立つ．それぞれの値 $w$ は $1 \le w \le 50$ であり，ペアの値の和 $s$ は[2,100]の範囲の値しか取らない．それぞれの値 $w$ が何個あるか数えておいて，和 $s$ を全探索．

1WAは答えの最小値を1にしていた…（ $n = 1$ のときはペアが作れないので答えが0になる）．

コード

def main():
    Tquery = int(input())
    for _ in range(Tquery):
        _ = int(input())
        W = [int(i) for i in input().split()]
        cnt = [0]*(101)
        for w in W:
            cnt[w] += 1
        ans = 0
        for s in range(2, 101):
            cur = 0
            for i in range(1, s//2 + 1):
                if i != s-i:
                    cur += min(cnt[i], cnt[s-i])
                else:
                    cur += cnt[i]//2
            ans = max(ans, cur)
        print(ans)


if __name__ == '__main__':
    main()

D問題

考察の方針があっちに行ったりこっちに行ったりと迷子になった．よくない．

nケタのbinaryの文字列が与えられる．これをいくつかの部分列に分解して，どの部分列でも0と1が交互に来るようにしたい．例えば，"0101"だったら，このまま条件を満たすし，"0100"だと条件を満たさないので"010"と"0"の2個の部分列に分解する．わかりやすさのために連続する部分列を分解したが，連続しない要素を抜き出して部分列にしてもよい．"0011"だったら，真ん中の"01"と両端の"01"の部分列に分解する．つまり"0"や"1"が連続して現れないように部分列を作ることが条件．そしてすべての部分列が条件を満たすような最小の分解の個数を求めるのが問題．

初めは個数だけで決まる？と考えたけど，"0101"は部分列が1，"0011"は部分列が2で違うなと気づき，すぐに方針を切り替える．ここから部分列の個数が何個になるだろう？を考えていたが，最終的に要素ごとにどの部分列に割り当てるか構築しなければいけないことは考えていなかった．反省．

サンプルだけは合うコードが書けるも，"10001011110"で5個必要と出力されるようなコードを書いて1WA（正しくは4個で十分）．

最終的な解法は，キューを二つ用意しておき，文字列を前から見ていった．"0"が来たら"1"が末尾の列に追加したいので，そのような列がキューに入っていれば追加，入っていなければ"0"を先頭にするような新しい部分列を増やすことにした．実際にキューに部分列を入れる必要はなく，何個目の部分列であるか，だけ入れて管理すればいい．

コード

def main():
    from collections import deque
    Tquery = int(input())
    for _ in range(Tquery):
        N = int(input())
        S = input()
        ans = [-1]*N
        idx = [deque(), deque()]
        teamnum = 0
        for i, s in enumerate(S):
            if idx[int(s) ^ 1]:
                team = idx[int(s) ^ 1].popleft()
                ans[i] = team
                idx[int(s)].append(team)
            else:
                newteam = teamnum + 1
                ans[i] = newteam
                teamnum += 1
                idx[int(s)].append(newteam)
        print(teamnum)
        print(*ans)


if __name__ == '__main__':
    main()

なんかググってたらすごいたくさん解説が書いてありそうなサイト見つけた．なんだこれすごい．

ntk log ntk

競プロや非競技プロのやったことを書いています.

Codeforces Round #661 (Div. 3)

A問題

B問題

C問題

D問題