ABC197 参加記録 - Xenous の精進記録

4完0ペナ 45分でした
E 解けなかったのが惜しいですね。。

A - Rotate

3文字固定なので、入力で受け取った文字を求められた順で直接出力します。

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

B - Visibility

与えられた点から上下左右それぞれ外周か # にぶつかるまで何個 . があったか数えます。入力の際に # で囲ってしまっても良いですね。

H, W, X, Y = map(int, input().split())
X -= 1; Y -= 1
field = []
for _ in range(H):
    tmp = list(input())
    field.append(tmp)

ans = 1
for h, w in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
    i = h; j = w
    res = 0
    while True:
        if not (0 <= X+i < H and 0 <= Y+j < W):
            break
        if field[X+i][Y+j] != '.':
            break
        i += h
        j += w
        res += 1
    ans += res
print(ans)

C - ORXOR

1つ以上の空でない連続した区間に分ける方法を全探索します。分け方は、下の図のように、配列（黒マル）の要素を並べたときの間(矢印)のどこに仕切りを入れるか、と考えれば良いです。

f:id:Xenous:20210328091127p:plain — 区切り方の全探索

これは bit 全探索で可能です。python では標準ライブラリ itertools.combinations を使っても実装できます。具体的には、仕切りを $k$ 個選んだときの全ての場合を確かめて、 $k$ も $0$ から $N-1$ までループさせれば良いです。

from itertools import combinations

def bitOR(A:list) -> int:
    res = 0
    for a in A:
        res = res | a
    return res


def bitXOR(A:list) -> int:
    res = 0
    for a in A:
        res = res ^ a
    return res


def main():
    N = int(input())
    A = list(map(int, input().split()))
    ORmemo = [[-1] * (N+1) for _ in range(N+1)]
    ans = bitXOR(A)
    for k in range(N-1):
        for iters in combinations(range(1, N), k):
            res = []
            i = 0; rangeiters = list(iters) + [N]
            for j in rangeiters:
                if ORmemo[i][j] != -1:
                    res.append(ORmemo[i][j])
                else:
                    res.append(bitOR(A[i:j]))
                i = j
            ans = min(ans, bitXOR(res))
    print(ans)


if __name__ == "__main__":
    main()

一応、OR をとったときの値をメモ化しています。 $N$ が大きくないのでなくても大丈夫な気がします。

D - Opposite

正 $N$ 角形を構成する頂点は必ず円上にあります。与えられた2点から、その円の中心の座標が求まります。
$x_1, y_1$ は、円の中心から角度 $\theta$ だけ反時計回りに回転させたものと考えることができます。

原点を中心とした回転は回転行列を使えばすぐに求まります。以上より、円の中心の座標を使って原点に平行移動させ、原点周りの回転をして、元の位置に戻せば良いです。

N = int(input())
x0, y0 = map(int, input().split())
xN2, yN2 = map(int, input().split())
theta = 2*pi / N

# 中心を求める
midX, midY = (x0+xN2) / 2, (y0+yN2) / 2

# 原点に戻す
x, y = x0 - midX, y0 - midY

# 回転させる
tox, toy = x*cos(theta) - y*sin(theta), x*sin(theta) + y*cos(theta)

# 戻す
x1, y1 = tox + midX, toy + midY

print(x1, y1)

E - Traveler

本番で解けなかった問題です。
まず、取っていったときの色の番号が広義単調増加という制約があるので、色の番号が小さい方からみていくことになります。
また、結局は同じ番号のボールの最も左側と最も右側の位置だけわかっていれば良いです。同じ色のボールを回収するとき、間にあるボールをあえて取らないで取りに戻ることをしても、端からとったときと同じかそれ以上の移動が必要になってしまいます。

どのように調べるかですが、最初は距離が近い方を選んで探索することを考えていました。これだとサンプル3のように次の色が片側に寄っている場合を取りこぼす可能性があります。

結局のところ、どの色の番号を取得したときでもやることは同じで、次の2択になります。

同じ色のボールについて、左端から右端に向かって回収する
同じ色のボールについて、右端から左端に向かって回収する

直前で回収した色の右端か左端にいるので、もう少し具体的に書くと、次のような遷移になります。

$k$ 番目の色のボールを回収し右端にいて、 $k+1$ 番目の色のボールを左端から回収する。
$k$ 番目の色のボールを回収し右端にいて、 $k+1$ 番目の色のボールを右端から回収する。
$k$ 番目の色のボールを回収し左端にいて、 $k+1$ 番目の色のボールを左端から回収する。
$k$ 番目の色のボールを回収し左端にいて、 $k+1$ 番目の色のボールを右端から回収する。

この遷移を、色の番号が小さい方からDPで埋めていけば良いです。

N = int(input())
minX = dict(); maxX = dict()
colorset = set([])
for _ in range(N):
    X, C = map(int, input().split())
    if C not in minX: minX[C] = X
    else: minX[C] = min(minX[C], X)
    if C not in maxX: maxX[C] = X
    else: maxX[C] = max(maxX[C], X)
    colorset.add(C)
colorlist = list(colorset)
colorlist.sort()
M = len(colorlist)

# 初期化
DP = [[float('inf')] * 2 for _ in range(M + 1)]

# 初期条件
DP[0][0] = 0; DP[0][1] = 0

# 遷移
l0 = 0; r1 = 0
for i, c in enumerate(colorlist):
    # 右端から進んで左端に行くパターン
    DP[i+1][0] = min(DP[i][0] + abs(l0 - maxX[c]), DP[i][1] + abs(r1 - maxX[c])) + abs(maxX[c] - minX[c])
    # 左端から進んで右端に行くパターン
    DP[i+1][1] = min(DP[i][0] + abs(l0 - minX[c]), DP[i][1] + abs(r1 - minX[c])) + abs(minX[c] - maxX[c])
    l0 = minX[c]; r1 = maxX[c]

# 答え
ans = min(DP[M][0] + abs(l0), DP[M][1] + abs(r1))
print(ans)