AtCoder Beginner Contest (ABC) 228 Pythonで参戦しました。 A,B,C問題解説あり。
前回のやつ
こんばんわ。めりーです。
寒くなってきたので、押し入れからマフラーとセーターを引っ張り出して来たら、驚くほど汚れてたので人生初クリーニングに出してきました。
まぁ、去年使い終わったのをそのまま放置してたらこうなりますよね・・・。
というわけで、トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)参戦してきました。
今回はA,B,C問題まで解けたので、感想&解説しまーす。
言語はPython、提出はPyPyです。
目次
A問題 On and Off
On and Off
問題文
S時に電気をつけ、T時に電気を消します。
X時30分に電気は付いているでしょうか？
という問題。
方針は、
1. 入力する
2. SからTの間に0時を超えているかでif文で判別
3. 2の条件下で判定する
という方針でやりました。
コード
s,t,x = map(int,input().split())
if s <= t:
if s<=x<t:
print("Yes")
else:
print("No")
else:
if s<=x or x<t:
print("Yes")
else:
print("No")
解説です。
if s <= t:
if s<=x<t:
print("Yes")
else:
print("No")
まず、0時をまたがないバージョンです。
この場合は単純に、SからTの間にXがあればYesを出力します。
X = Tの場合はNoになります。
T時00分に電気を消して、X(=T)時30分に電気を消すからです。
else:
if s<=x or x<t:
print("Yes")
else:
print("No")
0時をまたぐバージョンです。
T(消灯時刻)～S(点燈時刻)の範囲外にあればYesです。
言い換えると、X < T もしくは、 S <= X にあればYesです。
B問題 Takahashi's Secret
Takahashi's Secret
問題文
高橋君にはN人友達がいます。
ある日、秘密がX君にばれます。
友達i君は秘密をAi君にばらします。
高橋君は何人の友達に秘密がばれるでしょうか？
という問題。
手順としては、
N個の要素を持った配列を全要素「0」で作ります。（以下フラグと呼ぶ。）
友達i君が秘密を知ったらフラグの要素iを1にします。
それを愚直に問題文の通りに実装すればOKです。
方針は、
1. 入力
2. フラグ建設
3. 順番に処理してく
4. 出力
という感じでやってきました。
コード
n,x = map(int,input().split())
a = list(map(int, input().split()))
x -= 1
ans = [0]*n
ans[x] = 1
for i in range(n):
if ans[a[x]-1] == 0:
ans[a[x]-1] = 1
x = a[x]-1
else:
break
print(sum(ans))
解説してきます。
x -= 1 ans = [0]*n ans[x] = 1
まず、Xが1始まりなので、0始まりにするために、Xを-1します。
ansをフラグとして作成します。
そして、起点になってる友達Xのフラグを1にします。
for _ in range(n):
if ans[a[x]-1] == 0:
ans[a[x]-1] = 1
x = a[x]-1
else:
break
メイン部分。
友達XがA[x]にチクるので、A[x]のフラグを1にします。
そして、XをA[x]に更新します。
それを繰り返していきます。
この処理が終了するのは、伝えられた友達が秘密を知っていた場合です。
つまり、フラグを1に変更する前にフラグが1だった場合、終了します。
C問題 Final Day
Final Day
問題文
N人が4日間試験を受けます。
各日、300点満点です。
人iが4日目のテストで、上位K人に入ることはあり得るか？
という問題。
とりあえず、人iの3日目までの成績に300(4日目のテストの満点)足して、他の人の3日目までの成績と比べて上位K位以内に入れれば可能性はありそうです。
上位K番目の人の点数は、ソートを使えば簡単にゲットできそうです。
なので、全ての人iについて全探索すればよさそうです。
というわけで、方針
1. 入力。
2. 現時点での合計点を計算して、ソート。
3. 各人iについて全探索する。
4. 人iの合計点に300足したものとソートした上位K番目の合計点とを比較して出力。
コード
n,k = map(int, input().split())
p = []
for _ in range(n):
P = list(map(int, input().split()))
p.append(sum(P))
p1 = sorted(p,reverse=True)
for i in range(n):
if p[i] + 300 >= p1[k-1]:
print("Yes")
else:
print("No")
解説してきます。
for _ in range(n):
P = list(map(int, input().split()))
p.append(sum(P))
Pの入力をするときに、合計値にして入力してます。
入力時に計算しておくと、配列Pの中に入るのが、
P = [人1の3日目までの合計点、人2の3日目までの合計点,...]
となります。
なので、この後ソートするときに楽になります。
p1 = sorted(p,reverse=True)で、ソートします。p1は配列pとは別の配列なので注意。
今回は降順(3,2,1みたいなやつ)で並べ替えてます。
なので、上位K番目の人の得点がp1[k-1]でわかります。
for i in range(n):
if p[i] + 300 >= p1[k-1]:
print("Yes")
else:
print("No")
全探索パート
i番目の人の3日目までの得点に300足して(p[i]+300)、それが上位K番目の人の得点(p1[k-1])より高ければYes、小さければNoを出力します。
それだけ。
今回のコンテストはD問題にも手を出してみたのですが、TLEに苦しんで正解できませんでした。
くそおおおおおおお
それでは。
