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

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

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

A - Exact Price

Xが100で割り切れるなら条件を満たします。

ただし、0の場合は条件を満たしません。
「Xが0でない」という条件は
X!=0
と書きます。

「Xが100で割り切れる」かつ「Xが0でない」
という条件をif文でつくればOKです。

「Yes」「No」は文字列なので出力するときに"Yes","No"とダブルクオーテーションをつけてください。

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

【提出】

# 入力の受け取り
X=int(input())

# Xが100で割り切れる　かつ　X=0でないならば
if X%100==0 and X!=0:
    # Yesを出力
    print("Yes")
# そうでなければ(100で割り切れない　または　X=0)
else:
    # Noを出力
    print("No")

B - String Shifting

右シフトを何回か行って得られる文字列は全て左シフトのみを適切な回数行うことで得られます。
例：「abcd」を右シフト3回⇔「bcda」⇔「abcd」を左シフト1回
ですから左シフトを(文字数)回実際に行って、得られた文字列をリストへ格納し、ソートすればよいです。

リストの末尾の要素はリスト[-1]とすることで確認することができます。

【提出】

# 入力の受け取り
S=input()

# 作った文字を格納するリスト
S_list=[]

# Sの文字数回処理する
for i in range(len(S)):
    # Sの先頭の文字を末尾へ(左シフト)
    S=S[1:]+S[0]
    # リストへ作った文字を追加
    S_list.append(S)

# ソートする
S_list.sort()

# 辞書順最小=リストの先頭
S_min=S_list[0]
# 辞書順最大=リストの末尾
# リスト[-1]でリストの末尾の要素が取り出せる
S_max=S_list[-1]

# 辞書順最小を出力
print(S_min)
# 辞書順最大を出力
print(S_max)

C - Doukasen

まず両端から火をつけて何秒後に燃え尽きるか考えましょう。
これは左端からのみ火をつけて、全て燃え尽きるまでにかかる時間の半分です。

i本目の導火線が燃え尽きるまでにかかる時間=距離/速さ=A[i]/B[i]です。
これをi=1~Nまで足して2で割れば、両端から火をつけて燃え尽きるまでの時間がわかります。
(実装では簡単のため0インデックス、すなわち1本目=A[0],B[0],2本目=A[1],B[1],...としています)

時間がわかったら左端から何cm進めるか調べます。
残り時間をtimeとして
・もし残り時間内にi本目の導火線を全て燃やせるなら
　時間(=距離/速さ)を残り時間(time)から引く
　A[i]cm進む
・そうでなければ(もし残り時間内にi本目の導火線を全て燃やせないなら)
　(速さ(B[i])×残り時間)cm進む
　終了する
と実装すればよいです。

【提出】

# 入力の受け取り
N=int(input())

# 入力の受け取りリスト
A=[]
B=[]

# 左端からのみ火をつけたとき、燃え尽きるまでにかかる時間
full_time=0

# N回
for i in range(N):
    # 入力の受け取り
    a,b=map(int, input().split())
    # リストへ格納
    A.append(a)
    B.append(b)
    # 時間=距離/速さを計算して足す
    full_time+=a/b

# 両端から火をつけたとき、燃え尽きるまでにかかる時間
# 左端から火をつけたときに燃え尽きるまでの時間の半分
time=full_time/2

# 左端からtime秒ですすめる距離
dist=0

# i=0~Nまで
for i in range(N):
    # もし残り時間内にi本目の導火線を全て燃やせるなら
    if A[i]/B[i]<=time:
        # 時間=距離/速さを計算して残り時間から引く
        time-=A[i]/B[i]
        # A[i]cm進む
        dist+=A[i]
    # そうでなければ(もし残り時間内にi本目の導火線を全て燃やせないなら)
    else:
        # 距離=速さ×時間　進む
        dist+=B[i]*time
        # 時間がなくなったので処理を終了する
        break

# 距離を出力
print(dist)

D - Restricted Permutation

この問題の実装はBFS(幅優先探索)で使うテクニックを多く使います。
BFSを実装したことがない人は先にBFS問題に取り組むことをおすすめします。
比較的簡単なBFS問題は以下です。
https://atcoder.jp/contests/abc204/tasks/abc204_c
解説：https://qiita.com/sano192/items/f898c907cffaa1486dac#c---tour

また、拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」でもBFSを詳細に解説しています。
詳しくは最下部【広告】を御覧ください。

トポロジカルソートを使います。

入力例1を例に説明します。
N=4
M=3
②は①より前に現れる
③は④より前に現れる
②は④より前に現れる

これをまずはグラフで表現します。

上図矢印のとおりに進めば必ず条件を満たすという図です。
例えば②からは①か④へ進めますが、これは条件「②は①より前に現れる」「②は④より前に現れる」を表しています。

しかし問題は②→①へ進んだあとどこに行けばわからないということです。①からは矢印が伸びていません。
更にどこからスタートして良いかもわかりません。

そこで以下の手順を踏みます。

(1)それぞれの頂点に対して「入ってくる辺の数」を数える
(2)「入ってくる辺の数」が0の頂点のうち、一番数字が小さいものを記録する
(3)(2)で記録した頂点と、そこから伸びる辺を消す
(4)(2)～(3)を繰り返し、「入ってくる辺の数」が0の頂点がなくなったら終了

実際にやってみましょう。

(1)それぞれの頂点に対して「入ってくる辺の数」を数える

赤い数字が入ってくる辺の数です。
例えば④は②と③から入ってきているので「2」です

(2)「入ってくる辺の数」が0の頂点のうち、一番数字が小さいものを記録する
「入ってくる辺の数」が0の頂点は②,③で、そのうち小さい方は②です。
これを答え(ansというリスト)へ記録します。
ans：2

(3)(2)で記録した頂点と、そこから伸びる辺を消す
②とそこから伸びる辺を消します。
以下のようになります。

②と辺を消したことで①,④の「入ってくる辺の数」が変わっています。

(4)(2)～(3)を繰り返し、「入ってくる辺の数」が0の頂点がなくなったら終了
「入ってくる辺の数」が0の頂点はまだあるので、繰り返しに入ります。

(2)「入ってくる辺の数」が0の頂点のうち、一番数字が小さいものを記録する
「入ってくる辺の数」が0の頂点は①,③で、そのうち小さい方は①です。
これを答えへ記録します。
ans：2 1

(3)(2)で記録した頂点と、そこから伸びる辺を消す
①とそこから伸びる辺を消します。
以下のようになります。

これらを繰り返すことで最終的に
ans：2 1 3 4
となり、答えが得られます。

ところでPが存在しない場合はどうなるでしょうか。
これはすなわち条件が矛盾している場合です。

以下のような入力を考えます。
N=3
M=3
②は①より前に現れる
③は②より前に現れる
①は③より前に現れる

これを図にすると以下のようになります。

この場合「入ってくる辺の数」が0の頂点が存在しないため、(2)～(3)の処理は行われません。
ゆえにansが空のリストになります。

一般には(1)～(4)の処理が終わった時、ansにN個の要素がない(ansの長さがN未満)であれば、どこかに矛盾した条件があり、Pが存在しないということになります。
その場合は「-1」を出力します。

それぞれの処理に対する実装のコツは以下です。
(1)それぞれの頂点に対して「入ってくる辺の数」を数える
まず「入ってくる辺の数」を記録するリスト(count)をつくります。
A,Bの入力を受け取ると同時に「入ってくる辺の数」をカウントします。
(A→Bと辺を張るからcount[B]にプラス1しておく)

(2)「入ってくる辺の数」が0の頂点のうち、一番数字が小さいものを記録する
「入ってくる辺の数」が0の頂点はcountを確認すればよいです。
このとき、リストやdequeではなくheapqへ格納することで、一番数字が小さいものを高速で取り出す事ができます。
heapqを使ったことがない人は以下を参照してください。

heapについて
heapはリストから最小値をO(logN)で取り出せるデータ構造です。
import：import heapq
リストのheap化 O(N)：heapify(リスト)
要素の追加 O(logN)：heappush(リスト,要素)
最小値の取り出し O(logN)：heappop(リスト)
【使用例】

# インポート
import heapq

# リストを用意
que=list()

# リストのheap化 O(N)：heapify(リスト)
heapq.heapify(que)

# 要素の追加 O(logN)：heappush(リスト,要素)
heapq.heappush(que, 6)
heapq.heappush(que, 1)

# 最小値の取り出し O(logN)：heappop(リスト)
min_x=heapq.heappop(que)

詳しく知りたい人は以下のページを見てください。

(3)(2)で記録した頂点と、そこから伸びる辺を消す
頂点と辺の削除については要するにその頂点(now)から進むことができる頂点(to)の「入ってくる辺の数」をマイナスしていけばよいです。
マイナスして0になったものがあれば用意したheapqへ頂点を格納します。

トポロジカルソートについてより詳細に知りたい人は以下のページがわかりやすいですから、読んでみてください。

【提出】

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

# 入ってくる辺の数をカウントするリスト
count=[0]*(N+1)
# つながっている辺の情報を格納
connect=[[] for i in range(N+1)]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int, input().split())
    # A→Bへ行ける
    connect[A].append(B)
    # Bへ入ってくる辺の数をプラス1
    count[B]+=1

# heapqをインポート
import heapq

# キューを用意
que=[]

# i=1~Nまで
for i in range(1,N+1):
    # 入ってくる辺の数が0の頂点があれば
    if count[i]==0:
        # キューへ追加
        que.append(i)

# キューをheap化
heapq.heapify(que)

# 答えの格納リスト
ans=[]

# キューが空になるまで
while 0<len(que):
    # 今いる頂点
    # キューから一番小さい番号のものを取り出す
    now=heapq.heappop(que)
    # 答えの末尾へ追加
    ans.append(now)

    # 今いる頂点から行ける頂点=to
    for to in connect[now]:
        # 辺を消す=toに入ってくる辺の数をマイナス1
        count[to]-=1
        # もし入ってくる辺の数が0になったら
        if count[to]==0:
            # キューへ追加
            heapq.heappush(que,to)

# 答えの長さがNならば
if len(ans)==N:
    # 答えを出力
    print(*ans)
# そうでなければ(N未満ならば)
else:
    # -1を出力
    print(-1)

【広告】

『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】