AtCoder Beginner Contest 197の感想

過去問埋め。

AtCoder Beginner Contest 197（Sponsored by Panasonic） - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Rotate

文字列はリストのようにインデックスを使ってn文字目にアクセス出来ることを利用。

s = input()
ans = s[1:] + s[0]
print(ans)

B – Visibility

スタート地点から全探索。

上下左右に全探索していくとスタート地点が４回カウントされてしまうので、最後に−３する。

二次元配列のインデックスと、range関数の引数に注意する。

h, w, x, y = map(int, input().split())
masu = [list(input()) for _ in range(h)]

x -= 1
y -= 1

ans = 0
for i in range(x, h):
    curr = masu[i][y]
    if curr == ".":
        ans += 1
    else:
        break

for i in range(x, -1, -1):
    curr = masu[i][y]
    if curr == ".":
        ans += 1
    else:
        break

for i in range(y, w):
    curr = masu[x][i]
    if curr == ".":
        ans += 1
    else:
        break

for i in range(y, -1, -1):
    curr = masu[x][i]
    if curr == ".":
        ans += 1
    else:
        break

ans -= 3
print(ans)

C – ORXOR

n=1の時、答えは与えられた数字。

n=2の時、答えは2つの数字のXOR。

n>=3の時を考える。

n個の値を1つ以上の空でない連続した区間に分けるので、数学の組み合わせ問題のようにn-1個の仕切りを入れたいと考える。

仕切りを入れる、入れないの2択をn-1箇所に行うので、bit全探索が使える。

n<=20なので、計算量O(2^N)は十分間に合う。

仕切りが入っていなければ同じグループなのでorの値(orval)を更新する。

仕切りがあれば別グループに変わるので、xorの値(xorval)を更新してorvalをリセットする。

ループの最後 j=n-2の時にxorvalが更新されない場合があるので書き忘れないよう注意。

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(a[0])
    exit()

if n == 2:
    ans = a[0] ^ a[1]
    print(ans)
    exit()

ans = 1e9
for i in range(1, 2 ** (n - 1) - 1):
    pattern = [0] * (n - 1)
    for j in range(n - 1):
        if i >> j & 1:
            pattern[j] = 1

    orval = a[0]
    xorval = 0
    for j in range(n - 1):
        if pattern[j] == 0:
            orval |= a[j + 1]
        else:
            xorval ^= orval
            orval = a[j + 1]

        if j == n - 2:
            orval |= a[j + 1]
            xorval ^= orval

    ans = min(ans, xorval)

print(ans)

D – Opposite

以下のように数学の図形問題として考える。

１．正N角形の中心を原点に移動。

２．(x0, y0)を 360/n 度回転させると(x1,y1)と一致。

３．１で原点に移動させた分を戻して終わり。

import numpy as np

n = int(input())
x0, y0 = map(int, input().split())
xn2, yn2 = map(int, input().split())

# 正N角形の中心は与えられた2点の中点
xo = (x0 + xn2) / 2
yo = (y0 + yn2) / 2

# 中心を原点に移動
x0 -= xo
y0 -= yo

# 回転
angle = 360 / n
radian = np.deg2rad(angle)
cos = np.cos(radian)
sin = np.sin(radian)

x = x0 * cos - y0 * sin
y = x0 * sin + y0 * cos

# 移動した座標を戻す
x += xo
y += yo

print(x, y)