Atcoder-ABC197をpythonでA,B,C,D問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC197を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
- 3文字の入力が与えられるが、先頭文字を末尾に移動して表示すれば良い
S = list(input()) print(S[1]+S[2]+S[0])
B問題
- 与えられた情報を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)
C問題
AC半分WA半分で本番中は解けなかった
- 与えられた数列を分割する方法を全部網羅するのにどうするか?が考慮が足りなかった
- bit探索を用いて、数列の分割を網羅的に探索する
- 例えば、長さ6(=N)の数列は、5(=N-1)つの分割するポイントがあるので、それをbitを用いて表現する
- あとは、全文探索(1 ~ 2N-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)
D問題
解き方はイメージできたが、時間切れで実装しきれず
- 各点Pは、P0とPN/2の中点を中心(点O)とした円上に存在する
- P1は、2pi/N だけP0をずらしたところに存在する
- P1は、半時計周りにずらすので、+ 2pi/Nする
- P0とPN/2の距離の半分が半径になる
- P1は、2pi/N だけP0をずらしたところに存在する
- 中心からのP1の角度は
atan2
を用いることで求められる
- 原点を中心にした円上の座標は半径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)
まとめ
- 解説を軽くみて、無事D問題まで解けた。次は、時間内に解けて早く茶色コーダになれるように頑張りたい