AtCoderBeginnerContest166復習＆まとめ（前半）

AtCoder ABC166

2020-05-03(日)に行われたAtCoderBeginnerContest166の問題をA問題から順に考察も踏まえてまとめたものとなります．
前半ではABCまでの問題を扱います．
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

A問題　Registration

問題文
AtCoder 社は、毎週土曜日にコンテストを開催しています。
コンテストには ABC と ARC の$2$つの種類があり、毎週どちらか一方が開催されます。
ABC が開催された次の週には ARC が開催され、ARC が行われた次の週には ABC が開催されます。
先週開催されたコンテストを表す文字列$S$が与えられるので、今週開催されるコンテストを表す文字列を出力してください。

このあたりは，特に悩むことなく解けるかなと思います．
受けとった文字列が ABC と ARC のどちらであるかをif文で判定すれば終わりです．

abc166a.py

s = input()
if s == "ABC":
    print("ARC")
else:
    print("ABC")

B問題　Trick or Treat

問題文
ある街に、$N$人のすぬけ君(すぬけ君$1$、すぬけ君$2$、...、すぬけ君$N$)が住んでいます。
この街には、$K$種類のお菓子(お菓子$1$、お菓子$2$ 、....、お菓子$K$)が売られています。お菓子$i$を持っているのは、すぬけ君$A_{i,1},A_{i,2},⋯,A_{i,d_i}$の計$d_i$人です。
高橋君は今からこの街を回り、お菓子を$1$つも持っていないすぬけ君にいたずらをします。このとき、何人のすぬけ君がいたずらを受けるでしょうか。

いたずらを受けるすぬけ君を記録しておくリストkun_listを作ります．
最初にお菓子の情報を与えない場合，全員がお菓子を持ってないことになるので，全すぬけ君はいたずらを受けることになります．
なので，そこに与えられたお菓子の情報を使って，お菓子を持っているすぬけ君をいたずらリストから外していけば，最終的にお菓子を持ってない，いたずらされるすぬけ君がリストに残るので，人数を数えることで解けます．

abc166b.py

n, k = map(int, input().split())
kun_list = [1] * n
for i in range(0, k):
    d = int(input())
    a_list = list(map(int, input().split()))
    for a in a_list:
        kun_list[a-1] = 0
print(sum(kun_list))

C問題　Peaks

問題文
AtCoder丘陵には$N$個の展望台があり、展望台$i$の標高は$H_i$です。 また、異なる展望台どうしを結ぶ$M$本の道があり、道$j$は展望台$A_j$と展望台$B_j$を結んでいます。
展望台$i$が良い展望台であるとは、展望台$i$から一本の道を使って辿り着けるどの展望台よりも展望台$i$の方が標高が高いことをいいます。 展望台$i$から一本の道を使って辿り着ける展望台が存在しない場合も、展望台$i$は良い展望台であるといいます。
良い展望台がいくつあるか求めてください。

解説では，展望台$i$から一本の道でいける（隣接する）展望台の最大の高さ$maxH_i$を各展望台で求めて，$H_i > maxH_i$であれば，良い展望台であるためその数を数える方法をとっていました．
自分は，全ての展望台をとりあえず良い展望台として，ten_listという展望台のリストを作りました．
道の情報が一つ与えられることにより，どちらか or 両方の展望台が良い展望台ではなくなっていくため，高さを比較して，ten_listを更新していきました（両方の展望台が良い展望台でなくなるのは高さが等しいとき）．
最後に，残った良い展望台の数を数えればOKです．

abc166c.py

n, m = map(int, input().split())
h_list = list(map(int, input().split()))
ten_list = [1] * n
for i in range(0, m):
    a, b = map(int, input().split())
    if h_list[a - 1] <= h_list[b - 1]:
        ten_list[a - 1] = 0
    if h_list[a - 1] >= h_list[b - 1]:
        ten_list[b - 1] = 0
print(sum(ten_list))

前半はここまでとなります．
後半はDEF問題の解説となります．
C問題がB問題とほとんど同じような感じで解ける問題だったので，コンテスト時，少し不安でしたが詰まることなくここまでは解けました．
しかし，今回のコンテストもABCまで解いた後，行き詰まり，試行錯誤しましたが結局"AC"は出せずに終わってしまい，C問題までの短距離走の速さ比べになってしまい反省しています．
確かC問題通したのが開始14分ごろだった．
やっぱり，難しい問題を一問くらいは通して，徒競走から抜け出したいと思っています．
とりあえず前半の最後まで読んでいただきありがとうございました．
後半に続く．