Xenous の精進記録

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

ABC207 参加記録

  • 3完0ペナ 22分でした
  • また3完だ... と思ったら DEFが最高に難しい回だったので仕方がない感じでした。

A - Repression

探索させても良いですし、ソートして大きいもの2つを取る、でも良いと思います。下記の実装は後者です。

X = list(map(int, input().split()))
X.sort()
ans = X[-1] + X[-2]
print(ans)

B - Hydrate

式に落とすと以下になります。

  •  A + kB \leq kC \times D を満たす最小の0以上の整数  k を見つける。

式変形すると  A \leq k(C\times D -B) になります。  A は制約上  10^{5} までしかとらないため、 k の最大も  A 程度になります。

したがって この式を直接  k でループさせて調べることができて、越えればその  k の値ですし、超えないなら -1 です。

A, B, C, D = map(int, input().split())
for i in range(10**7):
    if A + i*B <= D*i*C:
        print(i)
        return
print(-1)

C - Many Segments

区間を左から順に舐めとっていこうとすると混乱します。今回の問題は単純に全ての区間から2つを選ぶ全探索が  O(N^{2}) で回るので、こちらの方針で実装します。

区間の重なりについては以下のように判定します。

区間  i区間  j を取ります。それぞれを比較したとき、左端  l の値が小さい方を  i と改めておきます。 そうしたとき、区間  i の右端  r_i区間  j の左端  l_j で以下のような場合があります。

f:id:Xenous:20210626230401p:plain
区間の場合分けイメージ

区間の持ち方でパターン (i)、(ii)、(iii) に分かれ、右端と左端の関係を図のように確認し、満たすのであれば重なりがあるとしてカウントします。 以上で各区間の重なりを見ることができました。

N = int(input())
sector = []
for _ in range(N):
    t, l, r = map(int, input().split())
    sector.append((t, l, r))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        ti, li, ri = sector[i]
        tj, lj, rj = sector[j]
        if li > lj:
            ti, tj = tj ,ti
            li, lj = lj, li
            ri, rj = rj, ri
        
        if ti == 2 or ti == 4:
            if lj < ri: ans += 1
        elif (ti == 1 or ti == 3) and (tj == 1 or tj == 2):
            if lj <= ri: ans += 1
        else:
            if lj < ri: ans += 1
print(ans)

D - Congruence Points

本番では重心で考える方法を思いつきはしましたが、小数の扱いになるとミスしやすいのでその方法は諦め、原点に戻す点( S T を一致させるための基準点)を全探索する方針にしました。しかし、公式解説にもありますが、重心は各点を  N 倍しておけば整数のまま扱えます。

また、整数点を回転させて整数点になるのは 90 度回転だけでは?ということを本番中否定できなかったのも反省です。これは 例えば以下のようなパターンで否定できます。三平方の定理で斜めの線分の長さが整数になるパターンです。

f:id:Xenous:20210628202134p:plain
90度回転以外の場合

ということで、角度は確定でなく探索する必要があります。しかし実数なので全探索はできません。

全体の方針としては、以下の流れで回転を調べます。

  1.  S T の重心をそれぞれ求める(各入力の点を  N 倍しておき、重心を整数で扱えるようにする)
  2.  S T の重心をそれぞれ原点へ移動させる。
  3.  S から 1 点、 T から 1 点選び、それらを重ねるように、  S の点に対する原点を中心とした回転角を求める。
  4. 求めた回転角で実際に  S を回転させて、 T と一致するか確かめる。
  5. どこかで一致したら Yes 。全部調べて一致しなかったら No とする

以下、この方針に沿って実装したコードを見ていきます。

1  S T の重心をそれぞれ求める(各入力の点を  N 倍しておき、重心を整数で扱えるようにする)

書いてあるとおり、入力時点で  N 倍します。その座標を使って重心を求めれば必ず整数になります。(なので小数点切り捨てでの割り算をしています)

N = int(input())
S = []; T = []
Sgx, Sgy = 0, 0
for _ in range(N):
    a, b = map(int, input().split())
    S.append((a*N, b*N))
    Sgx += a*N; Sgy += b*N
Sg = (Sgx//N, Sgy//N)

Tgx, Tgy = 0, 0
for _ in range(N):
    c, d = map(int, input().split())
    T.append((c*N, d*N))
    Tgx += c*N; Tgy += d*N
Tg = (Tgx//N, Tgy//N)

2  S T の重心をそれぞれ原点へ移動させる。

平行移動させるだけなので、それぞれの重心の座標を  S  T の集合から引いていくだけで良いです。

# 重心で重ねる
nS = []; Sgx, Sgy = Sg
for x, y in S:
    nS.append((x-Sgx, y-Sgy))

nT = set([]); Tgx, Tgy = Tg
for x, y in T:
    nT.add((x-Tgx, y-Tgy))

3  S から 1 点、 T から 1 点選び、それらを重ねるように、  S の点に対する原点を中心とした回転角を求める。

原点に移動させた  S の点と  T の点でループさせて、回転角を求めます。 回転角は  S の点の角度と、 T の点の角度をそれぞれ出して差を求めています。

# 一致させる点を探索する
for a, b in nS:
    for c, d in nT:
        # 回転角を求める
        stheta = theta(a, b, positive=True)
        ttheta = theta(c, d, positive=True)
        psi = ttheta - stheta
# x 軸からの回転角を求める関数
def theta(x:float, y:float, positive = False) -> float:
    if x == 0 and y == 0: return 0
    value = sqrt(x**2 / (x**2 + y**2)) * (1*(x >= 0) - 1*(x < 0))
    sign = 1 * (y >= 0) - 1 * (y < 0)
    res = acos(value) * sign
    if positive:
        res += 2*pi*(sign < 0)
    return res

求めた回転角で実際に  S を回転させて、 T と一致するか確かめる。

上の for 文の中で書きます。 回転行列の式を使って各点を原点を中心とした回転をさせます。このとき誤差が生じますが、整数点との差分がとても小さいなら、格子点上にあるとみなします。

# 点を丸める
err = 0.0000001

nnS = []
for x, y in nS:
    x, y = route(x, y, psi)
    rx, ry = round(x), round(y)
    if abs(x-rx) <= err and abs(y-ry) <= err:
        nnS.append((rx, ry))

# 整数点であることを確かめる
if len(nnS) != len(nT): continue

# 一致するか確かめる
if check(nnS, nT):
    print('Yes')
    return
# T に一致するか確かめるための関数
def check(s:list, t:set) -> bool:
    for x,y in s:
        if (x, y) not in t:
            return False
    return True

# 原点中心の回転を行う関数
def route(x:int, y:int, theta:float) -> tuple:
    return (x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta))

どこかで一致したら Yes 。全部調べて一致しなかったら No とする

回し切って、Yes にならなかったら No です。

以上です。計算量は  O(N^{3}) です。偏角ソートなどを使えば  O(N^{2}\log{N}) くらいになります。

提出コード

import sys
from math import cos, sin, sqrt, acos, pi

input = sys.stdin.readline
err = 0.0000001

def check(s:list, t:set) -> bool:
    for x,y in s:
        if (x, y) not in t:
            return False
    return True


def route(x:int, y:int, theta:float) -> tuple:
    return (x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta))


def theta(x:float, y:float, positive = False) -> float:
    """
    点(x, y) と x 軸との角度 theta を求める.

        Peremeters:
        -----------
        x, y: float
            点(x, y) の座標.
        positive: bool
            返却値を 0 <= theta < 2*pi の範囲にする
        
        Returns:
        --------
        theta: float
            点(x, y)とx軸との角度 theta
            positive が False であれば -pi/2 < theta <= pi/2 の範囲で返す
            positive が True であれば 0 <= theta < 2*pi の範囲で返す
            点(0, 0) の場合は 0 を返す
    """
    if x == 0 and y == 0: return 0
    value = sqrt(x**2 / (x**2 + y**2)) * (1*(x >= 0) - 1*(x < 0))
    sign = 1 * (y >= 0) - 1 * (y < 0)
    res = acos(value) * sign
    if positive:
        res += 2*pi*(sign < 0)
    return res


def main():
    N = int(input())
    S = []; T = []
    Sgx, Sgy = 0, 0
    for _ in range(N):
        a, b = map(int, input().split())
        S.append((a*N, b*N))
        Sgx += a*N; Sgy += b*N
    Sg = (Sgx//N, Sgy//N)

    Tgx, Tgy = 0, 0
    for _ in range(N):
        c, d = map(int, input().split())
        T.append((c*N, d*N))
        Tgx += c*N; Tgy += d*N
    Tg = (Tgx//N, Tgy//N)

    # 重心で重ねる
    nS = []; Sgx, Sgy = Sg
    for x, y in S:
        nS.append((x-Sgx, y-Sgy))

    nT = set([]); Tgx, Tgy = Tg
    for x, y in T:
        nT.add((x-Tgx, y-Tgy))

    # 一致させる点を探索する
    for a, b in nS:
        for c, d in nT:
            # 回転角を求める
            stheta = theta(a, b, positive=True)
            ttheta = theta(c, d, positive=True)
            psi = ttheta - stheta

            # 点を丸める
            nnS = []
            for x, y in nS:
                x, y = route(x, y, psi)
                rx, ry = round(x), round(y)
                if abs(x-rx) <= err and abs(y-ry) <= err:
                    nnS.append((rx, ry))
            
            # 整数点であることを確かめる
            if len(nnS) != len(nT): continue

            # 一致するか確かめる
            if check(nnS, nT):
                print('Yes')
                return
    print('No')    

if __name__ == "__main__":
    main()

E - Mod i

後ほど書きます。

F - Tree Patrolling

後ほど書きます。