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

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

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

A - Seismic magnitude scales

32の(A-B)乗を出力すればよいです。
pythonではaのx乗を
a**x
と書きます。

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

【提出】

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

# 答えの出力
print(32**(A-B))

B - typo

1文字目と2文字目,2文字目と3文字目,...と、入れ替えたパターン全てを試してTと一致するか確認します。

文字列そのまま扱うと入れ替えが面倒なので一文字ずつのリストにするとよいでしょう。文字列をリストに変換するときは
list(S)
と書くことでSを一文字ずつリストにすることができます。

Sのi文字目とi+1文字目を入れ替えたいときは、
S_list[i],S_list[i+1]=S_list[i+1],S_list[i]
と書けばOKです。

途中でプログラムを終了するときは
exit()
と書きます。

【提出】

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

# S,Tが一致していれば
if S==T:
    # Yesを出力
    print("Yes")
    # 終了
    exit()

# S,Tを一文字ずつリストへ
S_list=list(S)
T_list=list(T)

# i=0~(Sの文字数-1)まで
for i in range(len(S)-1):
    # i文字目,i+1文字目とi+1文字目,i文字目を交換
    S_list[i],S_list[i+1]=S_list[i+1],S_list[i]
    # S_listとT_listが一致していれば
    if S_list==T_list:
        # Yesを出力
        print("Yes")
        # 終了
        exit()
    # 交換したものをもとに戻す
    S_list[i],S_list[i+1]=S_list[i+1],S_list[i]
    
# 一致しないままforを抜けたらNoを出力
print("No")

C - Select Mul

Bit全探索を使います。

各桁の数字についてAグループとBグループに分け、それぞれ大きい順に数字を並べて掛け算する、というのを全ての場合について試します。
例としてN=123456の場合
0桁目の数(左から1つ目)=「1」がAグループの場合、Bグループの場合
1桁目の数(左から2つ目)=「2」がAグループの場合、Bグループの場合
2桁目の数(左から3つ目)=「3」がAグループの場合、Bグループの場合
...
5桁目の数(左から6つ目)=「6」がAグループの場合、Bグループの場合
と考えるとありうるグループ分けはたかだか2^6通り(2^(Nの桁数)通り)しかないということがわかります。

Aグループに「1,2,4」
Bグループに「3,5,6」
が入った場合はそれぞれ数字の大きい順に並べて421×653=274913となります。

グループ分けを行うにあたってBit全探索を使います。
Bit全探索についてよくわからない人は以下を読んでください。

Bit全探索について
取る、取らない　など2択を全パターン試す場合に使用します。
例えば6個の選択についてならば6桁の2進数を対応させてそれぞれを確認します。
2進数が101001ならば
0個目(右から1桁目)=1→取る
1個目(右から2桁目)=0→取らない
2個目(右から3桁目)=0→取らない
3個目(右から4桁目)=1→取る
4個目(右から5桁目)=0→取らない
5個目(右から6桁目)=1→取る
というように対応付けが行なえます。

2進数の000000~111111(N桁)までループを回すときは以下のように書くと良いです。
for bitnum in range(1<<N):
1<<Nはシフト演算で、1を左にN個シフト=2進数の100...0(0がN個)=2^Nを表します。
上記のように書くことでbitnum=000000~111111のように順に確認ができます。

右からx桁目(右端は0桁目)が0か1かは以下のように書くことで確認できます。
if bitnum>>x & 1==1:
bitnumを右にxシフトさせたあと1とアンド演算しています。
結果が
0ならばx桁目は0
1ならばx桁目は1
であることがわかります。
※if bitnum>>x and 1==1:　と書かないよう注意！！

例えば101001(=10進数の41)の右から3桁目(右から4つ目)を確認する場合
101001>>3=000101であり、
000101 & 1(=000001)=1
となりますから、右から3桁目は1とわかります。

この問題ではNの各桁について2進数の桁を割り当て、
0ならばグループA
1ならばグループB
へ割り振りしていきます。

グループへの割り振りができたら数字の大きい順にソートします。
整数へ変換して掛け算の結果を確認すればOKです。

グループAまたはグループBに何も入っていないならば数字が作れないので飛ばします。

Bit全探索については拙著『AtCoder　凡人が『緑』になるための精選50問詳細解説』で更に詳しく解説しています。
以下リンクよりBit全探索の解説内容を確認できますのでぜひ御覧ください。
サンプルページ：https://qiita.com/sano192/items/abd5108d9c4f74e3efba

【提出】

# 入力の受け取り(文字列)
N=input()

# 答え　初期値は0
ans=0

# bitnum=(000...0)~(111...1)まで
for bitnum in range(1<<len(N)):
    # A,Bを用意
    A=[]
    B=[]

    # shift=0~Nの桁数-1まで
    for shift in range(len(N)):
    # bitnumのshift桁目が0か1か確認
        # 0ならば
        if bitnum>>shift & 1==0:
            # Aへ追加
            A.append(N[shift])
        # 1ならば
        else:
            # Bへ追加
            B.append(N[shift])
    
    # AまたはBが空なら
    if A==[] or B==[]:
        # 次のbitnum
        continue
    
    # 大きい順に並び替え
    A.sort(reverse=True)
    B.sort(reverse=True)

    # A,Bを結合
    A_join="".join(A)
    B_join="".join(B)

    # 整数にして掛け算
    tmp_ans=int(A_join)*int(B_join)

    # ansよりtmp_ansが大きかったらansを更新
    ans=max(ans,tmp_ans)

# 答えの出力
print(ans)

D - Online games

Aiの日にi番目のプレイヤーがログイン
Ai+Biの日にi番目のプレイヤーがログインをやめます。

つまり
Aiの日にプレイヤーが一人増え、
Ai+Biの日にプレイヤーが一人減ります。
プレイヤーが増減するそれぞれの日について人数をカウントし、日数を記録していきます。

具体的には以下のように実装します。

(1)Aiをstart,Ai+Biをendというリストへ格納する
(2)Ai,Ai+Biをdaysというセットへ格納する
　※daysはプレイヤーが増えるまたは減るというイベントが起こった日の一覧です
(3)daysをソートのためリスト(days_list)へ変換。start,end,daysをソートする
(4)days_list[i](=now)について、
　start=daysの日数分プレイヤーをプラス
　end=daysの日数分プレイヤーをマイナス
　（これでdays_list[i]の日に何人プレイヤーがいるかわかる)
(5)次のイベントが起こる日(days_list[i+1])までの日数分答えを追加

【提出】

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

# 開始日
start=[]
# 終了日
end=[]
# 開始または終了が起こる日(重複除去のためリスト)
days=set()

# N回受け取り
for i in range(N):
    # A,Bの受け取り
    A,B=map(int, input().split())
    # プレイヤーiの開始日
    start.append(A)
    # プレイヤーiの終了日(ログインをやめた日)
    end.append(A+B)
    # 開始日を追加
    days.add(A)
    # 終了日を追加
    days.add(A+B)

# 開始日,終了日をソート
start.sort()
end.sort()

# リストへ変換
days_list=list(days)
# ソート
days_list.sort()

# ログインしている人数
players=0

# 答えの格納リスト
ans=[0]*(N+1)

# 開始日の確認用
a=0
# 終了日の確認用
b=0

# days-1日目まで
for i in range(len(days_list)-1):
    # 今何日目か
    now=days_list[i]
    # now=開始日ならば
    while a<len(start) and start[a]==now:
        # プレイヤーがひとり増える
        players+=1
        # 次の開始日を確認
        a+=1
    # now=終了日ならば
    while b<len(end) and end[b]==now:
        # プレイヤーがひとり減る
        players-=1
        # 次の終了日を確認
        b+=1
    # プレイヤーの数<=Nならば
    if players<=N:
        # ans[プレイヤー人数]に次の「開始または終了が起こる日」-「今の日数」をプラス
        ans[players]+=days_list[i+1]-now

# 答えの出力
print(*ans[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】