ABC209 A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

ABC209(AtCoder Beginner Contest 209)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

その他のABC解説、動画などは以下です。

A - Counting

A≤BならばB-A+1
B<Aならば0
が答えになります。

これらの条件をif文で書き、それぞれを出力します。

入力の受け取り、出力がわからない方は以下の記事を参考にしてください。

【提出】

# 入力の受け取り
A,B=map(int, input().split())

# もしA<=Bならば
if A<=B:
    # B-A+1を出力
    print(B-A+1)
# そうでないならば(B<Aならば)
else:
    # 0を出力
    print(0)

B - Can you buy them all?

問題文の通り
偶数番目の商品は(定価-1)円
奇数番目の商品は(定価)円
として合計を計算し、合計がX以下か、Xより大きいかを判定します。

ただし、pythonでリストを受け取った場合、
A[0]=A1,A[1]=A2,...
と0始まりで番号が1つずれてしまいます。

ゆえに
A1=A[0]：奇数番目の商品の定価
A2=A[1]：偶数番目の商品の定価
A3=A[2]：奇数番目の商品の定価
...
となります。
よってA[i]について
iが偶数の場合(iを2で割ったあまりが0)→奇数番目の商品のため、A[i]円を足す
iが奇数の場合(iを2で割ったあまりが1)→偶数番目の商品のため、(A[i]-1)円を足す
と少々ややこしいことになるということだけ注意してください。

【提出】

# 入力の受け取り
N,X=map(int, input().split())
A=list(map(int, input().split()))

# 合計の値段を格納する変数
sum_price=0

# i=0~N-1まで
for i in range(N):
    # 奇数番目の商品=iが偶数
    # ⇔iを2で割ったあまりが0ならば
    if i%2==0:
        # 合計にA[i]を追加
        sum_price+=A[i]
    # 偶数番目の商品=iが奇数
    # ⇔iを2で割ったあまりが0でない=あまりが1
    else:
        # 合計にA[i]を追加
        sum_price+=A[i]-1

# もし合計がX以下ならば
if sum_price<=X:
    # Yesを出力
    print("Yes")
# そうでなければ(X<sum_priceならば)
else:
    # Noを出力
    print("No")

C - Not Equal

Cの順番が変わっても答えは変わりません。とりあえず小さい順にソートしましょう。
(数列問題は8割くらいがソートでなんとかなります)

ソートしたあとの数列がC=[2,4,6,7]となったとします。
ついでにあとあとのことを考えてC1,C2,...をC0,C1,...と0始まりに読み替えます。
問題文のC1=C[0]
問題文のC2=C[1]
...
となるだけです。(Aも同様に0始まりとして考えます)

A0として選べるのは1または2です。つまり2通りです。
A1として選べるのは1~4ですがA0で選んだものと重複してはいけないので-1して3通りです。
A2として選べるのは1~6ですがA0,A1で選んだものと重複してはいけないので-2して4通りです。
A3として選べるのは1~7ですがA0,A1,A2で選んだものと重複してはいけないので-3して4通りです。
ゆえに234*4=96通りとなります。

上記を一般化して考えると
Aiとして選べるのは1~C[i]ですが、A0,A1,A2,...Ai-1で選んだものと重複してはいけないので-iして(C[i]-i)通り
となります。

あとは
(C[0]-0)*(C[1]-1)*(C[2]-2)*...*(C[N-1]-(N-1))
を計算するだけです。
ただし途中でC[i]-i=0となったら答えは0ですから、途中で終了すれば良いです。

10^9+7等で余りを取った値を出力する問題は必ず計算しながら一回一回余りを取ってください。
余りを計算がすべて終わった後に取るよう実装すると、計算途中に変数の値が大きくなりすぎて計算が追いつかずTLEします。

【提出】

# 入力の受け取り
N=int(input())
C=list(map(int, input().split()))

# mod=10^9+7と定義
mod=10**9+7

# Cをソート
C.sort()

# 答えを格納する変数
ans=1

# i=0~N-1まで
for i in range(N):
    # もしC[i]-i=0ならば
    if C[i]-i==0:
        # 0を出力
        print(0)
        # 終了
        exit()
        
    # ansにC[i]-iをかける
    ans*=C[i]-i
    # あまりを取る
    ans%=mod
# 答えを出力
print(ans)

D - Collision

以下の入力を例として考えましょう。
【入力例】
4 2
1 2
1 3
2 4
3 4
1 4

街の関係を図にすると以下のようになります。

以下の手順で街に色を付けます。
(1)街1に赤色を塗る
(2)街1と隣接する街に青色を塗る
(3)青色を塗った街に隣接する街に赤色を塗る
(4)赤色を塗った街に隣接する街に青色を塗る
すべての街に色がつくまで(3)～(4)を繰り返します。

結果、以下のようになります。

図を見ればわかるように
赤の街から移動する場合、必ず次に青の街へたどり着きます。
青の街から移動する場合、必ず次に赤の街へたどり着きます。
つまり赤→青→赤→青→...という移動になります。

・1番目のクエリ(3 4)
3：青
4：赤
で違う色です。
違う色の場合、高橋くんは青→赤→青→...、青木くんは赤→青→赤→...と、常に違う色の街にいるはずです。
であればどこかの街の上で出会うことはできませんから、道の上で会います。

・2番目のクエリ(1 4)
1：赤
4：赤
で同じ色です。
同じ色の場合、高橋くん、青木くんともに赤→青→赤→...と常に同じ色の街にいるはずです。
ゆえにどこかの街の上で出会います。

この解法は前提として
赤から移動すれば青へ、青から移動すれば赤へたどり着く
という条件が必要です。これが成り立たないとすれば図のようになっています。

2→3への移動について、青→青の移動ができてしまいます。
しかし図をよく見ると道路の本数が4本なので問題の条件(N-1本の道路)と合いません。ゆえにこのケースはありません。

赤、青に塗り分ける解法は 『N−1 本の道路』かつ『どの街からどの街へもいくつかの道路を通ることで移動できる』 という条件がついているから使える、ということを理解しておいてください。

実装ではBFS(幅優先探索)を使って各街に色を塗っていきます。
具体的には各街の色を格納するリストcolorsを作り、
街i が赤色ならcolors[i]=0
街i が青色ならcolors[i]=1
と割当していきます。

具体的な手順は以下です。
(1)各街の色、訪問済みかどうかを管理するリストを作る
(2)キューを用意し、スタート地点(街1)をキューへ入れる
(3)キューから今いる街の番号を取り出す
(4)今いる街から行ける街が訪問済みでなければ
　・訪問済みにする
　・今いる街と違う色を付ける
　・キューへ格納する
(3)~(4)をキューが空になるまで繰り返すと、すべての街へ色を割当できます。

あとはクエリを順に読み込み
2つの街が同じ色ならTown
2つの街が違う色ならRoad
を出力します。

BFSについては動画で実装方法を詳しく解説しているので、ぜひ御覧ください。

【提出】

# 入力の受け取り
N,Q=map(int, input().split())

# 道路の情報受け取りリスト
connect=[[] for i in range(N+1)]

# N-1本の道路
for i in range(N-1):
    # 入力の受け取り
    a,b=map(int, input().split())
    # a,bがつながっていると記録
    # (例)connect[1]=[2,3,4]ならば街1と街2,3,4がつながっている
    connect[a].append(b)
    connect[b].append(a)

# 各町の色を記録するリスト 赤：0 青：1 まだ塗っていない：-1
colors=[-1]*(N+1)
# 訪問済みかどうか記録するリスト
visited=[False]*(N+1)

# dequeを用意する
from collections import deque
que=deque()

# 街1を赤で塗る
colors[1]=0
# 街1を訪問済みにする
visited[1]=True

# キューに1を追加
que.append(1)

# キューが空でない間
while 0<len(que):
    # 今いる街
    now_town=que.popleft()
    # 今いる街の色
    now_color=colors[now_town]

    # to_town：now_townから行ける街
    for to_town in connect[now_town]:
        # もしto_townが訪問済みでなければ
        if visited[to_town]==False:
            # 訪問済みにする
            visited[to_town]=True
            # 今いる街が赤色なら
            if now_color==0:
                # 青色を塗る
                colors[to_town]=1
            # 今いる街が青色なら
            if now_color==1:
                # 赤色を塗る
                colors[to_town]=0
            # キューに追加
            que.append(to_town)

# クエリの読み込み
for i in range(Q):
    # 入力の受け取り
    c,d=map(int, input().split())
    # 街の色が同じなら
    if colors[c]==colors[d]:
        # townを出力
        print("Town")
    # そうでないならば(街の色が違うなら)
    else:
        # Roadを出力
        print("Road")

【広告】

『AtCoder　凡人が『緑』になるための精選50問詳細解説』

AtCoderで緑になるための典型50問をひくほど丁寧に解説した本(kindle)、pdf(booth)を販売しています。
値段：100円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

1～24問目まではサンプルとして無料公開しています

『AtCoder ABC201～225 ARC119～128 灰・茶・緑問題 超詳細解説』

ABC201~225、ARC119~128 の 灰・茶・緑DIfficulty問題(Dif：0～1199) を解説しています。
とにかく 細かく、丁寧に、具体例を豊富に、実装をわかりやすく、コードにコメントをたくさん入れて 解説しています。

サンプルを5問分公開しています

Qiitaにて無料公開している『ものすごく丁寧でわかりやすい解説』シリーズをベースにしていますが、 【キーワード】【どう考える？】【別解】を追加 し、 【解説】と【実装のコツ】を分ける ことでよりわかりやすく、 具体例や図もより豊富に 書き直しました。
Qiitaには公開していない ARC119~128の灰・茶・緑DIfficulty問題も書き下ろし ています。

値段：300円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】

【booth(pdf)】

『Excelでリバーシを作ろう!!　マクロ、VBAを1から学ぶ』

Excelのマクロ(VBA)で「三目並べ」「マインスイーパー」「リバーシ」を作る解説本です！
マクロ、VBAが全くわからない人でも大丈夫！　丁寧な解説と図でしっかり理解しながら楽しくプログラミングを学ぶ事ができます！
値段：300円(Kindle Unlimited対象)

サンプルとして「準備」～「三目並べ」を無料公開しています。

【kindle】

【booth(pdf】