Codeforces Round #662 (Div. 2)A~C [Python]

A

ジャンル

マンハッタン距離　ギャグ

概要

n*n gird の色分け
外側の境界から違い違いになるように順番に埋めていく。前回のターンで置かれた場所に隣接している箇所にしかおけないとき、最小のターン数を求めよ。

制約

1 <= n <= 10**9

考察

　n*n grid で最も内側がどこに位置するかを考える。
　右上を0,0とすると、(n//2,n//2)が最も内側のマス（の１つ）になる上下左右対象なのでこれを何回目にアクセスできるかを考える。

　１ターンで隣接している箇所にしか進めないので最も近傍のgridの辺上のマスからのマンハッタン距離を求めれば良い。

実装

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    n = int(input())
    print(n // 2 + 1)

ポイント

隣接しか進めないという条件をマンハッタン距離に帰着する。

B

ジャンル

クエリ　更新があるクエリでの最大、最小　

概要

あらかじめn 本の数列がある。qこのクエリが与えられ、(- k or + k の形式）、値k が削除、挿入される。

　各クエリ終了時に長方形、正方形が作れるか判定せよ。

制約

1<=n<=10**5
1<=ai<=10**5
1<=q<=10**5

考察

　挿入、削除時の最適な操作（どの値を挿入して削除するのがベストか？）を考えたい。

　ナイーブに考えると、各操作ごとにそれぞれの長さがいくつあるかを保持して、上からソートしたときに(4,2,2) (6,2) 以上あればOKだが、O(NQ log N )が通らない

全体で個数が6,4,2以上になる値がいくつあるかを変数としてもち、クエリでの操作によって6,4,2 を跨いだらを更新する。
　
　O(Q) でできる。

実装

import sys
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

n = ii()
a = il()
q = ii()
cnt = [0] * (10 ** 5 + 1)
cnt_246 = [0, 0, 0, 0]
lis = [2, 4, 6, 8]
for i in range(n):
    cnt[a[i]] += 1
    if cnt[a[i]] in lis:
        cnt_246[lis.index(cnt[a[i]])] += 1
        # print(i, cnt_246)

for qu in range(q):
    s = iss().split()
    # print(len(s), s)
    if s[0] == "+":
        cnt[int(s[-1])] += 1
        if cnt[int(s[-1])] in lis:
            cnt_246[lis.index(cnt[int(s[-1])])] += 1
    else:
        cnt[int(s[-1])] -= 1
        if cnt[int(s[-1])] + 1 in lis:
            cnt_246[lis.index(cnt[int(s[-1])] + 1)] -= 1
    # print(cnt_246, cnt[:3])
    if (
        cnt_246[3] >= 1
        or cnt_246[2] >= 2
        or (cnt_246[2] >= 1 and sum(cnt_246[:3]) >= 4)
        or (cnt_246[1] >= 2)
        or (cnt_246[1] == 1 and cnt_246[0] >= 3)
    ):
        print("YES")
    else:
        print("NO")

学び

　跨いだ箇所だけ変更しているので、累積の形現在の値以下のポイントにbitが立っている実装になっている(少しわかりにくい）

クエリ問題の入力の受け取りはTLEすることがあるのでsys.stdin.buffer.readline() であらかじめ一括で受け取る

　sys.stdin.buffer.readline()で文字列を受け取る時は8bitのバイト列として受け取られるので、decode() で文字列に直す処理が必要になる。

Unicode 文字列はコードポイントの列であり、コードポイントとは 0 から 0x10FFFF (10 進表記で 1,114,111) までの数値です。このコードポイント列はメモリ上では コードユニット 列として表され、その コードユニット 列は 8-bit のバイト列にマップされます。Unicode 文字列をバイト列として翻訳する規則を 文字エンコーディング または単に エンコーディング と呼びます。

docs.python.org

C

ジャンル

ギャグ　整数配列

概要

　整数列が与えられ、同じ数ができるだけ遠くなるように並び替えるとき、最も近くになるペアの距離を答えよ。
　

制約

2 <= n<= 10**5
1 <= ai <= n

考察

　同じ整数の個数がmax の数のみを考えれば良い。
　max の個数 K を持つ整数が m 個あるとき、(n-m) // (K-1) -1 が答え

実装

import sys
import math

read = sys.stdin.buffer.read
# input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
t = int(input())
for case in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0] * (10 ** 5 + 1)
    for i in range(n):
        cnt[a[i]] += 1
    k = max(cnt)
    m = cnt.count(k)
    print((n - m) // (k - 1) - 1)

学び

文字列や整数配列で出現頻度を持つのは頻出