Atcoder-ABC197をpythonでA,B,C,D問題を解いてみた

目的

• Atcoderで上を目指すべく頑張っている中でABC197を解いたので、解説してみる
  • pypy7.3を使って解いている

A問題

atcoder.jp

• 3文字の入力が与えられるが、先頭文字を末尾に移動して表示すれば良い

S = list(input())

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

• 無事にACできた

B問題

atcoder.jp

• 与えられた情報を2次元のlistに情報を格納する
  • H * W の2次元配列を初期値0で作成する
  • 入力情報で、壁がある場合は1で更新する
• 与えられた点から、縦横それぞれを調べれば良い
  • 点から上を調べる、下を調べる、右を調べる、左を調べる
• 1つずつ調べ上げる中で、壁にぶつかったらそこで数えるのを止める
• 自分自身も含めないといけないので、それを重複して調べないようにすること

H, W, X, Y = map(int, input().split())

S = [[0] * W for _ in range(H)]
ans = 0

for i in range(H):
    s = list(input())
    for j, c in enumerate(s):
        if c == "#":
            S[i][j] = 1

# 基準点よりも上を調べる(自分自身を含める)
for x in range(X-1, -1, -1):
    if S[x][Y-1] == 0:
        ans += 1
    else:
        break

# 基準点よりも下を調べる(自分自身を含めない)
for x in range(X, H):
    if S[x][Y-1] == 0:
        ans += 1
    else:
        break

# 基準点よりも左を調べる(自分自身を含めない)
for y in range(Y-2, -1, -1):
    if S[X-1][y] == 0:
        ans += 1
    else:
        break

# 基準点よりも右を調べる(自分自身を含めない)
for y in range(Y, W):
    if S[X-1][y] == 0:
        ans += 1
    else:
        break


print(ans)

• コードはきれいではないが無事ACできた

C問題

AC半分WA半分で本番中は解けなかった

atcoder.jp

• 与えられた数列を分割する方法を全部網羅するのにどうするか？が考慮が足りなかった
  • bit探索を用いて、数列の分割を網羅的に探索する
  • 例えば、長さ6(=N)の数列は、5(=N-1)つの分割するポイントがあるので、それをbitを用いて表現する

数列を分割する点

• pythonには、ビット演算子が用意されているので、それを使えば良い

note.nkmk.me

• あとは、全文探索(1 ~ 2^N-1)を行い、xorの最小値を更新していけば良い
  • 数列の分割点をlistに入れてあげて、それを用いてスライスで数列を分割していく

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

ans = pow(2, 30)


def get_or(l):
    x = l.pop(0)
    for i in l:
        x = x | i
    return x


def get_xor(l):
    x = l.pop(0)
    for i in l:
        x = x ^ i
    return x


for i in range(1, 2 ** (N-1)):
    # スライスで分割する際に、頭を切れるように追加
    L = [0]
    # bit列を文字列表す
    bit = bin(i)[2:].rjust(N-1, "0")
    # 1がある場合は分割する
    for j, b in enumerate(list(bit)):
        if b == "1":
            L.append(j+1)
    # スライスで分割する際に、最後尾切れるように追加
    L.append(len(A))
    O = []
    for k in range(1, len(L)):
        # 分割した配列の計算結果をlistに追加
        O.append(get_or(A[L[k-1]:L[k]]))
    # orの結果をxorした結果をget_xorで取得し、小さければansを更新
    ans = min(ans, get_xor(O))

# len 1の時にはansが更新されなかったので修正した
if len(A) == 1:
    print(A[0])
else:
    print(ans)

• 無事にACできた

D問題

解き方はイメージできたが、時間切れで実装しきれず

atcoder.jp

• 各点Pは、P0とPN/2の中点を中心(点O)とした円上に存在する
  • P1は、2pi/N だけP0をずらしたところに存在する
    • P1は、半時計周りにずらすので、+ 2pi/Nする
  • P0とPN/2の距離の半分が半径になる

円状に点があるイメージ

• 中心からのP1の角度は atan2 を用いることで求められる
  • pythonのmath関数に存在するのでそれを使う

ja.wikipedia.org

• 原点を中心にした円上の座標は半径r, X軸からの角度θを用いて表すことができる
  • x=rcosθ
  • y=rsinθ
  • 円状で求めた点を、原点から、中心Oまでの距離をずらしてあげる

from math import atan2, cos, pi, sin, sqrt

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

# 円の中心座標
ox, oy = (x0+xn2)/2, (y0+yn2)/2
# 円の半径
r = sqrt((x0-xn2)**2 + (y0-yn2)**2)/2
# 点P1の座標角度を求める
theta = atan2(y0-oy, x0-ox) + 2*pi/N
x1, y1 = r*cos(theta), r*sin(theta)

# 原点から、中心Oまでの距離をずらす
print(x1+ox, y1+oy)

• 無事にACできた

まとめ

• 解説を軽くみて、無事D問題まで解けた。次は、時間内に解けて早く茶色コーダになれるように頑張りたい