AtCoder Beginner Contest 197（Sponsored by Panasonic）

A-E は Python，F は Java．

A - Rotate

Python が楽．

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

B - Visibility

$(X, Y)$ を中心にして，4 方向それぞれに対して壁にぶつかるまで進む． $(X,Y)$ を重複してカウントしないように注意．

あんまりきれいに実装できなかった．

H, W, X, Y = map(int, input().split())
X -= 1
Y -= 1
S = []
for _ in range(H):
    S.append(input())
ans = 1
for j in range(Y + 1, W):
    if S[X][j] == '#':
        break
    ans += 1
for j in reversed(range(Y)):
    if S[X][j] == '#':
        break
    ans += 1
for i in range(X + 1, H):
    if S[i][Y] == '#':
        break
    ans += 1
for i in reversed(range(X)):
    if S[i][Y] == '#':
        break
    ans += 1
print(ans)

C - ORXOR

数列の各項の隙間 $N-1$ 個に対して，それぞれ切る or 切らないの $2 ^ {N-1}$ 全探索．区間列挙の際は両端に番兵を入れておくとよい．

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

ans = 1 << 32
for i in range(1 << N - 1):
    sep = [0] + [j + 1 for j in range(N - 1) if i >> j & 1] + [N]
    K = len(sep) - 1
    x = 0
    for l, r in zip(sep, sep[1:]):
        v = 0
        for t in A[l:r]:
            v |= t
        x ^= v
    ans = min(ans, x)

print(ans)

D - Opposite

点の回転がしたいので複素数を使う．

$K=N/2,\ z _ 0 = x _ 0 + i\cdot y _ 0,\ z _ K = x _ K + i\cdot y _ K$ とおく．正 $N$ 角形の中心を $z _ M$ とすると， $z _ M = (z _ 0 + z _ K) / 2$ である．そして， $z _ M$ を用いて目標の点 $z _ 1$ は次のように表せる．

$\displaystyle z_1=z_M+(z_0-z_M)\left(\cos \frac{\pi}{K}+i\cdot\sin\frac{\pi}{K}\right)$

実装においては，Python では標準で complex 型がサポートされているのでこれを使うとよい．

import math

N = int(input())
K = N // 2
x0, y0 = map(int, input().split())
xK, yK = map(int, input().split())

z0 = complex(x0, y0)
zM = complex((x0 + xK) / 2, (y0 + yK) / 2)

rot = complex(math.cos(math.pi / K), math.sin(math.pi / K))

z1 = (z0 - zM) * rot + zM
print(z1.real, z1.imag)

E - Traveler

DP をやるだけなんだけど，何を思ったか貪欲方針があると思って時間を溶かした．なんで...？

ボールが一つ以上存在するような全ての色に対して，その昇順に番号を $1,\ldots,M$ と振りなおす．そして，各色の玉の左端の位置 $L _ i$ と右端の位置 $R _ i$ を計算しておく．

ここで，以降の実装の簡単のため，色 $0$ をスタート地点に対応させ，色 $M+1$ をゴール地点に対応させる．このとき， $L _ 0 = R _ 0 = L _ {M + 1} = R _ {M + 1} = 0$ である．

2 つの DP テーブル $\mathrm{dpL}$ および $\mathrm{dpR}$ を，それぞれ以下のように定義する．

$\displaystyle \mathrm{dpL[i]}=\text{色 $i$ の玉を回収し終えて $L _ i$ にいるような場合における，それまでの移動距離の最小値}$

$\displaystyle \mathrm{dpR[i]}=\text{色 $i$ の玉を回収し終えて $R _ i$ にいるような場合における，それまでの移動距離の最小値}$

まず， $i=0$ の場合は明らかに $\mathrm{dpL}[0]=\mathrm{dpR}[0]=0$ である．

$i\gt 0$ の場合は，次のように遷移を書くことが出来る．

$\displaystyle \mathrm{dpL[i]}=\min( \mathrm{dpL[i-1]}+|L_{i-1}-R_i|, \mathrm{dpR[i-1]}+|R_{i-1}-R_i|)+R_i-L_i$

$\displaystyle \mathrm{dpR[i]}=\min( \mathrm{dpL[i-1]}+|L_{i-1}-L_i|, \mathrm{dpR[i-1]}+|R_{i-1}-L_i|)+R_i-L_i$

求める答えは $\mathrm{dpL}[M+1]$ または $\mathrm{dpR}[M+1]$ である．

F - Construct a Palindrome

難しい，みんな解くのが速い...

回文の中心から外に向かってパスを伸ばしていくイメージで，次のテーブルを埋めていく．

$\displaystyle \mathrm{dist}[u][v]=\text{回文となる $u$, $v$ パスの最短長}$

初め，すべての $0\leq u,v\lt N$ に対して $\mathrm{dist}[u][v]=\infty$ と初期化しておく．

自明なケースとして $\mathrm{dist}[i][i]=0\;(i=0,\ldots,N-1)$ である．また， $\mathrm{dist}[A _ j][B _ j]=\mathrm{dist}[B _ j][A _ j]=1\;(j=0,\ldots,M-1,\ A _ j \neq B _ j)$ である ( $A _ j = B _ j$ の場合は最短長は $0$ であるため除く必要がある)．

以上を基底ケースとして，テーブルの残りの部分を幅優先探索により埋めることができる．

具体的な手続きを以下に示す．なお，以降は幅優先探索に用いるキューを $q$ ，頂点 $u$ を始点とする辺の集合を $E(u)$ と表すことにする．また， $u$ を始点， $v$ を終点とする文字 $c$ が書かれた辺を $(u, v, c)$ と三つ組にして表現する．

基底ケースの頂点組 $(u,v)$ を $q$ に push する．
$q$ が空なら，全ての $\mathrm{dist}$ を確定済みとして終了する．空でないなら，3 に進む．
の先頭要素を pop する *1．の組を全探索する．このとき，各に対して，次のような場合分けを行う．全探索を終えたら，2 へ戻る．
1. $c _ u \neq c _ v$ のとき:
  何もしない
2. $c _ u = c _ v$ かつ $\mathrm{dist}[x][y]$ が未確定のとき:
  $\mathrm{dist}[x][y]=\mathrm{dist}[y][x]=\mathrm{dist}[u][v]+2$ 確定し *2， $q$ に $(x,y)$ を push する．
3. $c _ u = c _ v$ かつ $\mathrm{dist}[x][y]$ が確定済みのとき:
  何もしない