AtCoder Beginner Contest 197 - 競プロはじめました

コンテストに初めて参加しました．A，B，Dを解くことができました．練習では，紙を用意していなかったのですが，今回は図を描きながら取り組みました．

少し複雑な探索が必要になると，方針がわからず解けませんでした．このあたりの勉強が課題です．

まずは，提出された回答の中身が理解できるようになることを目指します！

A - Rotate
B - Visibility
C - ORXOR
D - Opposite
E - Traveler
F - Construct a Palindrome

A - Rotate

こうしました．

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

最初に提出された回答がこちら．なるほど，これなら文字数が増えても対応できますね．

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

B - Visibility

点$(X,Y)$を中心に縦方向，横方向に1マスずつずらしていき，'.'の個数を数えました．ループの添字がどう動いているのか混乱します．また，$(X,Y)$という座標と，リストの添字が1つずれることも鬱陶しいです．

h,w,x,y = map(int, input().split())
l=[input() for i in range(h)]

ans=1
for i in range(h-x):
  if l[x+i][y-1] == '.':
    ans += 1
  else:
    break

for i in range(x-1):
  if l[x-2-i][y-1] == '.':
    ans += 1
  else:
    break
  
for i in range(w-y):
  if l[x-1][y+i] == '.':
    ans += 1
  else:
    break
  
for i in range(y-1):
  if l[x-1][y-2-i] == '.':
    ans += 1
  else:
    break
  
print(ans)

C - ORXOR

探索方法が思いつかず，手が出ませんでした．

わかりやすかった回答は以下です（Submission #21295839 - AtCoder Beginner Contest 197（Sponsored by Panasonic））．内容を読み取ると，

$A$の左から順に，①考えている区間に入れるか，②考えている区間に入れずに区間を閉じるか，を考える．
1. $A[i]$を区間に入れる場合は，その区間について累積してORをとったもの（メモ1）と$A[i]$のORをとり，保持する（メモ1を上書きする）．
2. $A[i]$を区間に入れない場合は，確定している区間のXOR（つまり，メモ1とメモ2のXOR）をとり，保持する（メモ2を上書き）．また，メモ1を$A[i]$で上書きする．
上の操作が$A[0]$から$A[N-1]$まで終わったら，他の区切り方と比較し，小さければANSを上書きする．

となっています．コード中の$c$がメモ1で，$x$がメモ2です．$A[N-1]$まで終了したら，メモ1と$A[N-1]$を含む区間（メモ2）とのXORを取る処理が必要です．また，ANSの初期値は大きければ良いので，ANS=float('inf')でも大丈夫です．

N=int(input())
A=list(map(int,input().split()))
ANS=1<<30
def f(c,x,i):
  global ANS
  if i==N:
    ANS=min(ANS,c^x)
  else:
    f(A[i],c^x,i+1)
    f(c|A[i],x,i+1)

f(0,0,0)
print(ANS)

この探索方法は，「部分和問題」がわかれば，理解出来るようになります．

また，ビット演算の記事をメモしておきます：

Python ビット演算超入門 - Qiita

D - Opposite

点$p_{0}$と点$p_{N/2}$を結ぶ直線は，図形の中心を通ります．よって，図形の中心は

\begin{aligned}
\biggl(\frac{x_{0}+x_{N/2}}{2}, \frac{y_{0}+y_{N/2}}{2}\biggr)
\end{aligned}

で求められます．

中心から点$p_{1}$へ向かうベクトルは，中心から点$p_{0}$に向かうベクトルを$2\pi/N$だけ反時計回りに回転させることで得られます．

$p_{1}$の座標は「図形の中心座標＋中心から点$p_{1}$へ向かうベクトル」で得られます．

import numpy as np
n = int(input())
a=np.array(list(map(int, input().split())))
b=np.array(list(map(int, input().split())))

center=(a+b)/2
vec=(a-b)/2
deg=2*np.pi/n

x=center[0]+np.cos(deg)*vec[0]-np.sin(deg)*vec[1]
y=center[1]+np.sin(deg)*vec[0]+np.cos(deg)*vec[1]

print(str(x)+' '+str(y))

E - Traveler

$C_{i}$のソートまではしたのですが，同じ$C_{i}$の中の優先度が決められず．．．

import numpy as np
n = int(input())
l = np.array([list(map(int, input().split())) for i in range(n)])
l=l[np.argsort(l[:, 1])]

問題文に「ボールを回収できる時に必ずしも回収する必要はありません」とありますが，

回収した場合でもその後取れる行動に変化はない
回収しなかった場合，後で必ずその地点を通る必要がある

ので，回収したほうが選択肢が増えることになります．よって，回収できるときに回収すべきです．

したがって，公式解説にあるように，同じ色のボールの座標が$l=x_{1} < x_{2} < \cdots < r=x_{k}$であれば，最後に回収するのは端にある$l=x_{1}$か$r=x_{k}$になります．

$x$にいる状態からスタートして，これらのボールを全て回収するのに要する時間は

最後に回収するのが$l=x_{1}$である場合：
- （$x \leq l$なら，$l=x_{1}$をスルーすることになり，非合理的な選択肢）
- $x \leq r$なら，$(r - x) + (r - l)$（$r$を取りに行って折り返す）
- $x > r$なら，$x-l$（大きい順に回収）
最後に回収するのが$r=x_{k}$である場合：
- （$x \geq r$なら，$r=x_{k}$をスルーすることになり，非合理的な選択肢）
- $x \geq l$なら，$(x-l) + (r - l)$（$l$を取りに行って折り返す）
- $x < l$なら，$r-x$（小さい順に回収）

となります．

次の回答がわかりやすかったです（多少書き換え，コメントを加えたものを掲載します）．
Submission #21303571 - AtCoder Beginner Contest 197（Sponsored by Panasonic）

# a→b→cの所要時間
def abc(a,b,c):
    # 逆順でも所要時間は同じ．a<=cだけ考え，a>cなら入れ替えればよい．
    if a > c:
        a,c = c,a
    # a<=cの場合
    if a <= b <= c:
        return c-a
    elif b <= a <= c:
        return a-b + c-b
    else:
        return b-a + b-c  # b>cならa<=c<b

N = int(input())

Clis = []  # [色リスト]
Cdic = {}  # 色:[座標リスト]
for i in range(N):
    X,C = map(int, input().split())
    if C not in Cdic:
        Cdic[C] = []  # C:[空リスト]
        Clis.append(C)
    Cdic[C].append(X)  # Cの座標を追加

Clis.sort()
# 最後に0に戻ってくるために，仮想的な色と座標0を追加
Cdic[10**9] = [0]
Clis.append(10**9)

l,r = 0,0  # 初期位置
lc,rc = 0,0  # 初期時刻

for C in Clis:
    Cdic[C].sort()  # 色Cの座標リストを昇順に
    nexl,nexr = Cdic[C][0],Cdic[C][-1]  # 色C座標の最小値・最大値(次ステップのスタート地点候補)

    NLC = min( lc + abc(l,nexr,nexl) , rc + abc(r,nexr,nexl) )  # l/r→nexr→nexlの所要時間
    NRC = min( lc + abc(l,nexl,nexr) , rc + abc(r,nexl,nexr) )  # l/r→nexl→nexrの所要時間

    l,r = nexl,nexr  # 次ステップの初期位置
    lc,rc = NLC,NRC  # 次ステップの初期時刻

print (min(lc,rc))

最初の述べたロジック通りに書き換えると次のようになります（殆ど変わりません）．

# 最後にlを回収する場合の所要時間
def time_l(x, l, r):
    if x <= r:
      return r-x + r-l
    else:
      return x-l

# 最後にrを回収する場合の所要時間
def time_r(x, l, r):
    if x >= l:
      return x-l + r-l
    else:
      return r-x

N = int(input())
Clis = []  # [色リスト]
Cdic = {}  # 色:[座標リスト]
for i in range(N):
    X,C = map(int, input().split())
    if C not in Cdic:
        Cdic[C] = []  # C:[空リスト]
        Clis.append(C)
    Cdic[C].append(X)  # Cの座標を追加

# 最後に0に戻ってくるために，仮想的な色と座標0を追加
Cdic[10**9] = [0]
Clis.append(10**9)

xl, xr = 0, 0  # 初期位置
tl, tr = 0, 0  # 初期時刻
Clis.sort()  # 色Cのリストを昇順に
for C in Clis:
    # 色C座標の最小値・最大値
    cl, cr = min(Cdic[C]), max(Cdic[C])
    
    # 累積所要時間
    tl_tmp = min( tl + time_l(xl, cl, cr), tr + time_l(xr, cl, cr) ) # 最後にlを回収する場合
    tr_tmp = min( tl + time_r(xl, cl, cr), tr + time_r(xr, cl, cr) )  # 最後にrを回収する場合
    
    xl, xr = cl, cr  # 次ステップの初期位置
    tl, tr = tl_tmp, tr_tmp  # 次ステップの初期時刻

print (min(tl, tr))

混乱せずに，こんなコードが書けるといいですね．私は，今読み返しても混乱気味です．．．

A - Rotate

B - Visibility

C - ORXOR

D - Opposite

E - Traveler

F - Construct a Palindrome