トヨタシステムズプログラミングコンテスト2021(ABC228)参戦記

トヨタシステムズさん主催のABC228の参加記録です。

私はレート600台で、Python3で参加しています。
この記事は、ABC228のAからC問題までを私が理解出来た内容で書いていきます。
C問題までのACコード付きです。

A – On and Off

標準入出力と条件分岐が問われる問題。

先週のA問題も難しいと思いましたが、今回のA問題は、より難しいと思います。
S>Tの場合が要注意です。サンプル２に書いてある状況をfor文でシミュレーションするコードを書いてACしました。

# トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)
# A - On and Off

S,T,X=map(int,input().split())

if S>T:
    for i in range (S,25):
        if i == X:
            print("Yes")
            exit()
    for i in range(0,T):
        if i == X:
            print("Yes")
            exit()
else:
    for i in range (S,T):
        if i ==X:
            print("Yes")
            exit()

print("No")

条件分岐で書く場合は、以下のコードでACします。

S,T,X=map(int,input().split())
if S>T:
    if S<=X<=23 or 0<=X<T:
        print("Yes")
    else:
        print("No")
else:
    if S<X<=T:
        print("Yes")
    else:
        print("No")

また、SよりもT,Xそれぞれ大きい場合は、24を足してから判定してもACしますね。

S,T,X=map(int,input().split())
if S>T:
    T+=24
if S>X:
    X+=24
if S<=X<T:
    print("Yes")
else:
    print("No")

B – Takahashi’s Secret

while文が書けますか。が問われる問題。

この問題も、B問題の中でも、非常に難しい問題だと思います。

私は、秘密を知った人を変数に持って、秘密を教えたら変数の値を更新していく様子をシミュレーションして解きました。

各友達が秘密を知っているか。をboolの配列に持って置き、秘密をすでに知っていたらwhile文を抜けるようにしています。最終的に、上記のbool配列がTrueの数を数えれば、秘密を知っている人数がわかります。

1-indexと0-indexの違いにも注意が必要ですね。

# トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)
# B - Takahashi's Secret

N, X = map(int,input().split())
A = list(map(int,input().split()))
X -= 1

know = [False]*N

while know[X] == False:
    know[X] = True
    X = A[X]-1

print(sum(know))

C – Final Day

問題文にいろいろ書いてあるけれども、惑わされずに書いてあることがシミュレーションできるかが試される問題。
私は、ソートと二分探索 (Pythonのbisectモジュール) を使用して解きました。

以下、この問題を解く方針を記載していきます。

• 3日間の各日の得点が与えられるが、合計だけが必要な情報として保持する。
• 各生徒について、自分は満点、他人は0点だった場合に、K位以内に入っているかを確認する。
• 確認する方法は、以下の手順で行う。
  • 3日目までの合計得点をソートした配列を持っておく。
  • 3日目までの自分の合計得点に、4日目に満点(300点)取ったと仮定して、点数を加算する。
  • 上記得点が、ソートした配列のどのインデックスに挿入されるかを bisect.bisect_right() を用いて確認する。
  • 人数(P)と上記インデックスの差がK未満かどうかを判定する。
• 上記判定結果で、”Yes”と”No”のいずれかを print() する。

# トヨタシステムズプログラミングコンテスト2021(AtCoder Beginner Contest 228)
# C - Final Day

import bisect 

P, K = map(int,input().split())

# 各生徒の3日目までの合計得点を格納する配列
results_by_day3 = []
for i in range (P):
    a, b, c = map(int,input().split())
    # 合計得点だけ配列に追加する
    results_by_day3.append(a+b+c)

# 3日目までの合計得点をソートする。
ranking = sorted(results_by_day3)

for result_i in results_by_day3:
    # 自分だけ満点を取った時に、どの位置にいるかを取得する
    my_rank = bisect.bisect_right(ranking, result_i + 300)
    # 差がKより小さければ"Yes"を出力
    if P - my_rank < K:
        print("Yes")
    else:
        print("No")

上記コードがコンテスト中に書いたコードですが、二分探索をしなくても、解けることを後で知りました。

上記の確認方法の部分を少し変更します。

• 3日目までの合計得点をソートする。
• K位以内に入れる得点のボーダーは、ソートした結果の上からK番目の得点になる。
• 3日目までの得点に、4日目満点(300点)を足した得点が、上記ボーダー以上かを判定する。

こちらのほうが実装量も、計算量も小さく済みますね。

P, K = map(int,input().split())

# 各生徒の3日目までの合計得点を格納する配列
results_by_day3 = []
for i in range (P):
    a, b, c = map(int,input().split())
    # 合計得点だけ配列に追加する
    results_by_day3.append(a+b+c)

# 3日目までの合計得点をソートする
ranking = sorted(results_by_day3)
# K位以内に入れる得点を取得する
target_score = ranking[-K]

for result_i in results_by_day3:
    # 自分が満点の場合、上記の得点以上になるかを確認する
    if result_i+300 >= target_score:
        print("Yes")
    else:
        print("No")