AtCoder ABC197 個人的メモ

所感

abc3完

A - Rotate

S = input()

print(S[1:] + S[0])

B - Visibility

マス(X, Y)から4方向に向けて連続する障害物でないマスを数えていく
制約より，(X, Y)は障害物で無いと分かるので初期値は1
縦座標がXで，横がY

H, W, X, Y = map(int, input().split())
grid = [input() for _ in range(H)]

X -= 1  # 縦
Y -= 1  # 横
ans = 1
# ↓
for i in range(1, H - X):
    if grid[X + i][Y] == "#":
        break
    ans += 1

for i in range(1, X + 1):
    if grid[X - i][Y] == "#":
        break
    ans += 1

for i in range(1, W - Y):
    if grid[X][Y + i] == "#":
        break
    ans += 1

for i in range(1, Y + 1):
    if grid[X][Y - i] == "#":
        break
    ans += 1

print(ans)

C - ORXOR

区間の分け方は，数列の各要素間において分けるか分けないかで$2^{N-1}\sim 10^6$通りある
よって，全探索できそうなのでそうする

from functools import reduce
from operator import or_, xor

N = int(input())
A = list(map(int, input().split()))

if N == 1:
    print(*A)
    exit()

ans = 10 ** 18
for bit in range(1, 1 << (N - 1)):
    is_cut = []
    for i in range(N - 1):
        is_cut.append(int(bool(bit & (1 << i))))
    # is_cutが1のとこで別れる
    last = 0
    res = []
    for i in range(N - 1):
        if is_cut[i] == 0:
            continue
        res.append(reduce(or_, A[last:i + 1]))
        last = i + 1
    res.append(reduce(or_, A[last:]))
    ans = min(ans, reduce(xor, res))

print(ans)

D - Opposite

解説ac
この辺りを参考にした
https://atcoder.jp/contests/abc197/submissions/21297967
https://atcoder.jp/contests/abc197/editorial/996
https://qiita.com/FumioNonaka/items/c246aca8f1b1b03a66be
https://ja.wikipedia.org/wiki/逆三角関数

1つ目のコードは，直交座標系で考えた．
任意の点$(x, y)$を原点を中心として$\theta[rad]$回転させた時の座標$(x',y')$は

$$x'=xcos(\theta)-ysin(\theta)\\ y'=xsin(\theta)+ycos(\theta)$$

で表される．
なので，以下の様に実装する．

1. 正$N$角形の中心を求め，原点に移動させる
2. 頂点$p_0$を$\theta =2\pi /N$回転させる
3. 1.で移動させた分を元に戻す

2つ目のコードは極座標系で考えた．
公式解説同じ

from math import pi, sin, cos

N = int(input())
a, b = map(int, input().split())
c, d = map(int, input().split())

x, y = (a + c) / 2, (b + d) / 2
ox, oy = a - x, b - y
theta = 2 * pi / N

ansx = ox * cos(theta) - oy * sin(theta) + x
ansy = ox * sin(theta) + oy * cos(theta) + y

print(f"{ansx:.11f} {ansy:.11f}")

from math import pi, sin, cos, atan2

N = int(input())
a, b = map(int, input().split())
c, d = map(int, input().split())

x, y = (a + c) / 2, (b + d) / 2  # 正N角形の中心(x,y)
ox, oy = a - x, b - y            # 正N角形の中心を原点に移動
theta = 2 * pi / N               # p0→p1の回転角度θ

omega = atan2(oy, ox)            # p0の角度
omega += theta

radius = (oy ** 2 + ox ** 2) ** 0.5

# (x',y')=(rcos(θ + ω),rsin(θ + ω))と移動させた分を元に戻す
print(f"{radius * cos(omega) + x:.11f} {radius * sin(omega) + y:.11f}")