日中、畑に行って少し疲れた状態でしたが、少し寝て復活したので、ABC204に参加しました。
ABC204のAからCまでの振り返りです。ACコード付きです。
使用言語はPython3です。レートは茶色下位くらいです。
A – Rock-paper-scissors
条件分岐が書けるかが問われる問題。
問題を解くだけであれば、条件分岐が書けるか。だけでよいのですが、「素早く解く。」となると話は変わってくると思います。
x==y の場合は簡単ですが、x!=y の場合での判定式を瞬時に書ける初学者の方は少ないのではないでしょうか。
方法は、いろいろあるとは思いますが、私は、x+yの数で判定しました。
まず、x==yかを確認し、この場合は、xと同じ数を出力する。
次からは、x+yの数字を確認していきます。
x+y==1 の場合、(x,y)の組み合わせは、(0,1)または、(1,0)なので、2を出力したらあいこになります。
x+y==2 の場合、同様に、(0,2)、(2,0)、(1,1)の組み合わせが考えられますが、(1,1)はx==yのため、1を出力すれば良いですね。残っている、(0,2)または、(2,0)に関しても、1を出力すればOKです。
x+y==3の場合、(x,y)の組み合わせは、(1,2)または、(2,1)なので、0を出力すればあいこになります。
これらを、コードにまとめて提出するとACします。
# AtCoder Beginner Contest 204
# A - Rock-paper-scissors
x,y=map(int,input().split())
if x==y:
print(x)
elif x+y==1:
print(2)
elif x+y==2:
print(1)
else: # x+y==3
print(0)この数字の足し算の考えは、私は、Linuxのchmodからヒントを得ました。
B – Nuts
繰り返し処理と条件分岐が書けるかが問われる問題。
for文で繰り返し処理をしていき、条件分岐、答え用の変数に加算し、最後にその変数を出力すればOKですね。
# AtCoder Beginner Contest 204
# B - Nuts
N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range (N):
if A[i]<=10:
pass
else:
ans+=A[i]-10
print(ans)C – Tour
経路問題が解けますか。な問題。
私はコンテスト中に解けませんでした。
まさかABCのC問題でグラフの問題が出てくるとは思いませんでした。出ちゃったものは仕方ないですが、この問題は、経路として通る(始点または終着点を含む)頂点の数調べていきます。これを各頂点実施して、総数を答えとして出力すればOKです。
Python3だとTLEするケースがあるので、PyPy3で提出しましょう。
# AtCoder Beginner Contest 204
# C - Tour
N,M=map(int,input().split())
G=[[i]for i in range (N)]
for i in range (M):
A,B=map(int,input().split())
A-=1 # 0-index
B-=1 # 0-index
G[A].append(B)
ans=0
for i in range (N):
# 頂点iから始まったときに
seen=set() # 既に訪れた事のある頂点
todo=[] # 行き来可能で、これから訪れる予定の頂点
seen.add(i)
todo.append(i)
while len(todo)>0:
t=todo.pop()
# 訪れた各頂点から行き来可能な頂点を全部todoに入れていく
for j in range (len(G[t])):
if G[t][j] in seen:
continue
else:
todo.append(G[t][j])
seen.add(G[t][j])
# 頂点iから始まった時に、訪れた頂点数を加算する
ans+=len(seen)
print(ans)
コンテスト中に解けませんでした。思い返すと、類題はコンテスト中に解いているので、残念ですね。
この問題をグラフのように見立てて、DFSで解いていたのに、今回の問題が解けなかったのが悔やまれます。その時の参戦記はこちら↓。
コメント