今日公開した記事にABC195参戦記がありますが、ABC195はPanasonicさん主催のABCでした。
今回のABC197はPanasonicさんがスポンサードのコンテストです。
Panasonicさんありがとうございます。
前回も書きましたが、家の中はPanasonicさんの製品で一杯です。これからもよろしくお願いします！ちなみに少額株主です。
今回も茶色コーダーの私が、参加記録のメモを残していきます。使用言語はPython3です。
A – Rotate
文字列操作が出来るかを問われる問題。今回は、任意の場所の文字列を取り出す事と文字列の結合ですね。
私は、問題文をよく読んでなくて、1文字目だけを最後に持ってくると思って以下のようなコードで提出してACしています。
# AtCoder Beginner Contest 197（Sponsored by Panasonic）
# A - Rotate
S=input()
print(S[1:]+S[0])この問題は、入力が3文字であることが保証されているため、初めのうちは以下のようなコードがわかりやすいかと思います。
S=input()
print(S[1]+S[2]+S[0])上記のように、Python3では文字列もindexで指定すれば任意の文字を取り出せます。また、文字列の一部を範囲指定して取り出すこともできます。スキップも可能です。
S="abcdefg"
print(S[0]) # => a
print(S[1:4]) # => bcd
print(S[-1]) # => g
print(S[3:-1]) # => def
print(S[::2]) # => acegB – Visibility
比較的単純な二次元グリッドの探索が出来るかを問われる問題。
グリッドの情報を二次元配列として保持して、指定された座標から、上下左右にいくつ ” . ” が続いているかを数える問題ですが、X , Y が二次元配列で操作する、どっちを指しているのかがわかりにくくなりがちな問題だと思います。
あとは、上下左右に確認するため、スタート地点が重複することに注意が必要です。
重複分の考慮については、私はsetを利用しました。答えから3を引くのでも大丈夫です。
# AtCoder Beginner Contest 197（Sponsored by Panasonic）
# B - Visibility
H,W,X,Y=map(int,input().split())
X-=1
Y-=1
area=[]
for _ in range (H):
s=input()
area.append(s)
# print(area)
ansset=set()
# ansls=[]
# 上方向の確認
for i in range (H+1):
if X-i<0:
break
if area[X-i][Y]=="#":
break
ansset.add((X-i+1,Y+1))
# ansls.append([X-i+1,Y+1])
# 下方向の確認
for i in range (H+1):
if X+i>=H:
break
if area[X+i][Y]=="#":
break
ansset.add((X+i+1,Y+1))
# ansls.append([X+i+1,Y+1])
# 左方向の確認
for i in range (W+1):
if Y-i <0:
break
if area[X][Y-i]=="#":
break
ansset.add((X+1,Y-i+1))
# ansls.append([X+1,Y-i+1])
# 右方向の確認
for i in range (W+1):
if Y+i >=W:
break
if area[X][Y+i]=="#":
break
ansset.add((X+1,Y+i+1))
# ansls.append([X+1,Y+i+1])
print(len(ansset))
# print(len(ansls)-3)C – ORXOR
BIT全探索が出来るかが問われる問題。
今回もC問題解けませんでした。制約が少ないことより、BIT全探索も頭をよぎりましたが、ビット演算子に惑わされたのが大きかったです。まぁ、言い訳ですね。
長さNの数列の間に、区切るか、区切らないかの2通りの選択肢を全通り試せばよいことまでは解説を見て理解しました。
その後の実装については自分で書いてACすることが出来ました。
今回は、数列の要素を選ぶか選ばないか。ではなくて、数列の要素の間を区切るか区切らないか。なので、数列の要素の間はN-1個分BIT全探索します。
こういうのを植木算と呼ぶらしいのですが、この前こどもと一緒に算数の事典見てたら載っていました。
BIT全探索の部分は以下の通りです。
N=3
for i in range(2**N):
P=[]
for j in range(N):
if i>>j & 1 ==1:
P.append(1)
else:
P.append(0)
print(P)
# >>
'''
[0, 0, 0]
[1, 0, 0]
[0, 1, 0]
[1, 1, 0]
[0, 0, 1]
[1, 0, 1]
[0, 1, 1]
[1, 1, 1]
'''これで、数列の要素間を区切るか区切らないかの全通りがわかります。
あとは、各パターンで、区切られるまでBIT演算子 ” | ” ( or ) を計算していき、区切られたら次の区間を計算していく。計算結果は配列に格納しておきます。
ORの計算が終わったら、先ほど格納しておいた配列の要素間で、BIT演算子 ” ^ ” ( xor ) を計算していき最小値の更新を確認すればOKです。
# AtCoder Beginner Contest 197（Sponsored by Panasonic）
# C - ORXOR
N=int(input())
A=list(map(int,input().split()))
N-=1
ans=2**35
for i in range(2**N):
P=[]
for j in range(N):
if i>>j & 1 ==1:
P.append(1)
else:
P.append(0)
O=[] # orの計算結果の格納場所
temp_or=A[0]
for k in range (N):
if P[k]==1:
O.append(temp_or)
temp_or=A[k+1]
else:
temp_or=temp_or|A[k+1]
else:
O.append(temp_or)
temp_xor=O[0]
for l in range (1,len(O)):
temp_xor=temp_xor^O[l]
ans=min(ans,temp_xor)
print(ans)私は1つのケースでWAが出て、ずっとコードとにらめっこしていたのですが、初期のansが10**9+7だとWAになりました。
つまり、十分大きい数字だと思っていた10億7よりも小さい数が出てこなかったということです。今回の制約は2**30ということで、1,073,741,824よりも大きい数を答えようの変数に用意しないとダメでした。こういう部分の感覚も磨いていきたいですね。
Panasonicさんの主催、協賛のコンテストすべてでレートが下がっています・・・
-25,-26,-27と順調に減り幅が増えています。
パナソニックさんのコンテスト怖い。
コメント