개인 노트

감상


abc3 완료
abc197

A - Rotate


S = input()

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

B - Visibility


송어(X, Y)에서 네 방향으로 장애물이 아닌 송어를 연속으로 세다
제약에 의하면 (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}\sim10^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


해설
이 일대를 참고했습니다.
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/역삼각함수
첫 번째 코드는 정교 좌표계에서 고려한 것이다.
임의의 점(x, y)을 원점 중심\theta[rad]으로 회전할 때의 좌표(x', y')는
x'=xcos(\theta)-ysin(\theta)\\
y'=xsin(\theta)+ycos(\theta)
나타내다
따라서 다음과 같이 설치합니다.
  • 정N 삼각형의 중심을 구하고 원점으로 이동
  • 정점p0 회전\theta = 2\pi/N
  • 1.변경합니다.
    두 번째 코드는 극좌표계다.
    공식 해설 동일
    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}")
    
    
  • 좋은 웹페이지 즐겨찾기