AtCoder Beginner Contest 197（Sponsored by Panasonic）D,E,F問題メモ

AtCoder Beginner Contest 197（Sponsored by Panasonic）

全探索、幾何、DP、など比較的バラエティに富んだ問題セットで面白かった。

D - Opposite

• 2次元平面上に $N$ 角形（偶数）がある
• 頂点を反時計回りに $p_0,p_1,...,p_{N-1}$ としたとき、$p_0$ と $p_{N/2}$ の座標が与えられる
• $p_1$ の座標を求めよ
• $4 \le N \le 100$

$N$ 角形の中心の座標は $\dfrac{p_0+p_{N/2}}{2}$ でわかる。 $p_1$ は、そこを中心として $p_0$ を $\dfrac{360}{N}$ 度だけ回転させたもの。

回転を扱うときは中心を原点に持ってきた方がやりやすいので、全体を平行移動して、回転させ、元に戻す。
平行移動後の $p_0$ を $p'_0 = (x'_0,y'_0)$、回転角 $\theta = \dfrac{360}{N}$ として、行列を以下のようにかけるとよい。

\begin{eqnarray} \begin{pmatrix} x'_1 \\ y'_1 \end{pmatrix} = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix} \begin{pmatrix} x'_0 \\ y'_0 \end{pmatrix} \end{eqnarray}

また、複素平面でも回転を扱える。
$(x,y)$ を $x+yi$ に対応させると、$p'_1 = p'_0 \times (\cos\theta + i\sin\theta)$ となる。

Python3

from math import pi, cos, sin

n = int(input())
x0, y0 = map(int, input().split())
x2, y2 = map(int, input().split())

xm = (x0 + x2) / 2
ym = (y0 + y2) / 2
x0 -= xm
y0 -= ym

theta = 2 * pi / n

x1 = cos(theta) * x0 - sin(theta) * y0
y1 = sin(theta) * x0 + cos(theta) * y0

x1 += xm
y1 += ym
print(x1, y1)

$p_0,p_1,p_{N/2}$ は $p_1$ を直角とした直角三角形である。

円周角は中心角の半分なので、$\angle p_0p_{N/2}p_1 = \dfrac{360}{2N}$ となる。

三角関数から各辺の長さが求まるので、2頂点の座標とあわせて、残り1点を特定できる。

E - Traveler

• 数直線上に $N$ 個のボール
• $i$ 番目のボールの座標は $X_i$ で、整数 $C_i$ が書かれている
• 原点から、全てのボールを回収して、原点に戻る動きを考える
  • ボールは、同じ座標にいるときのみ回収できるが、スルーしてもよい
• 回収順に並べたとき、ボールに書かれた整数は広義単調増加になっていないといけない
• 最短の移動距離を求めよ
• $1 \le N \le 2 \times 10^5$

$C_i$ が小さい順に、同じ整数が書かれたボールを全回収する、を繰り返すことになる。

同じ整数 $c$ が書かれた中で左端と右端のボールの座標をそれぞれ $l_c,r_c$ とすると、 $c$ のボールを回収するフェイズでは、絶対に $l_c$ から $r_c$ までは移動する必要があり、またその間に他の $c$ のボールは回収できる。

つまり、$c$ より小さい数字のボールを回収し終えた座標を $p$ とすると、以下の2通りの移動のみを考えて、損しない。

• $p→l_c→r_c$
• $p→r_c→l_c$

$c$ のボールを回収し終えた瞬間にいる可能性のある座標は $l_c$ か $r_c$ の2通りということになり、これをもってDPする。

• $DP[c][p:0/1]=$ 小さい順に整数 $c$ が書かれたボールまでを回収し終えたとき、$p=0$:左端、$p=1$:右端にいるときの (座標, 最小距離)

最後に原点に戻る操作を忘れないように注意。
便宜的に $c$ がめちゃ大きいボールを原点に置いておくと、DP更新と同じ処理で書ける。

Python3

from collections import defaultdict

n = int(input())
INF = 1 << 60
lll = defaultdict(lambda: INF)
rrr = defaultdict(lambda: -INF)
for _ in range(n):
    x, c = map(int, input().split())
    lll[c] = min(lll[c], x)
    rrr[c] = max(rrr[c], x)

lll[INF] = rrr[INF] = 0

keys = sorted(lll.keys())

dp1 = [0, 0]
dp2 = [0, 0]

for k in keys:
    l = lll[k]
    r = rrr[k]
    d = abs(l - r)

    lrl = dp1[1] + abs(dp1[0] - r) + d
    llr = dp1[1] + abs(dp1[0] - l) + d
    rrl = dp2[1] + abs(dp2[0] - r) + d
    rlr = dp2[1] + abs(dp2[0] - l) + d
    dp1[0] = l
    dp2[0] = r
    dp1[1] = min(lrl, rrl)
    dp2[1] = min(llr, rlr)

print(min(dp1[1], dp2[1]))

F - Construct a Palindrome

• $N$ 頂点 $M$ 辺の連結無向グラフ（単純とは限らない）
• $i$ 番目の辺は頂点 $A_i,B_i$ を結び、英小文字 $C_i$ が書かれている
• 頂点 $1$ から $N$ へのパスで、通る辺の文字を順に拾ったときにその文字列が回文になっているものがあるか判定し、ある場合は最短の長さを求めよ
• $2 \le N \le 1000$
• $1 \le M \le 1000$

持つ状態がちょっと特殊な最短経路探索。

回文を、両端から構成していくことを考える。
頂点を組で考えて、$1$ と $N$ から、どちらからも同じ文字が書かれた辺をたどっていく。

 ,-- a --②--...--⑤-- b --, ,--,
①-- b --③--...--⑥-- c --Ⓝ   a
 `-- c --④--...--⑦-- d --' `--'

上記のような場合は、$(1,N)$ からは $(3,5),(4,6),(2,N)$ などに行ける。回文の長さは2増える。

この頂点の組を、最短経路探索における“頂点”（ステート）とすると、 各ステートは両端からそこまでは回文となることが保証されていて、残りの間の埋め方を探索していくことになる。

また、あるステートからゴール（残りの間の文字を回文となるよう最短で埋める）までのコストは、 そのステートだけに依存する（たとえばそのステートへのたどり着き方などに依存しない）ので、 通常の最短経路探索と同じように、より悪いコストで同じステートに着いたときは、捨ててよい。

コストの増え方は全て +2 なので、Dijkstraを使わずともBFSで求められる。

ただし、終了条件に注意が必要。2通りある。

• A: $(3,3)$ のように頂点の組が同じになったとき
  • 長さ偶数の回文ができる
  • そこまでのコストが答えとなる
• B: $(3,4)$ で頂点 $3,4$ を結ぶ辺がある場合など（その辺の文字は何でもよい）
  • 長さ奇数の回文ができる
  • そこまでのコスト+1が答えとなる

BFSで探索中、Aが見つかったらそれが最小コストで確定するが、Bが見つかってもまだ確定しない。
キューの次に、同じコストでAに当てはまるものが控えているかも知れない。

Bが見つかったら暫定の答え $ans$ として覚えておき、キューから取り出されるコストが $ans$ 以上になったら、そこで確定する。

最短経路グラフにおける頂点（ステート）の個数は、元のグラフの頂点の組なので $O(N^2)$。

最短経路グラフの辺 $((a,b),(c,d))$ は、元のグラフで2本の辺 $(a,c),(b,d)$ が存在する必要があり、これも辺の組み合わせとなるので個数は $O(M^2)$。

$10^6$ 頂点 $10^6$ 辺の最短経路探索なら、十分間に合う。

Python3

from collections import defaultdict, deque

n, m = map(int, input().split())
links = [defaultdict(set) for _ in range(n)]
connected = [[0] * n for _ in range(n)]
for _ in range(m):
    a, b, c = input().split()
    a = int(a) - 1
    b = int(b) - 1
    c = ord(c)
    links[a][c].add(b)
    links[b][c].add(a)
    connected[a][b] = connected[b][a] = 1

stacked = [[0] * n for _ in range(n)]
stacked[0][n - 1] = stacked[n - 1][0] = 1
ans = 1 << 60

q = deque([(0, 0, n - 1)])
while q:
    cost, a, b = q.popleft()
    if cost >= ans:
        print(ans)
        exit()
    if a == b:
        print(cost)
        exit()
    if connected[a][b]:
        ans = cost + 1
        continue
    common = links[a].keys() & links[b].keys()
    for c in common:
        for u in links[a][c]:
            for v in links[b][c]:
                if not stacked[u][v]:
                    q.append((cost + 2, u, v))
                    stacked[u][v] = stacked[v][u] = 1

if ans == 1 << 60:
    print(-1)
else:
    print(ans)