HHKBプログラミングコンテスト2022 Winter(ABC282) A～D問題 ものすごく丁寧でわかりやすい解説 python 灰色～茶色コーダー向け #AtCoder

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)　A～D問題の解説記事です。
灰色～茶色コーダーの方向けに解説しています。

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

更新時はツイッターにて通知します。
https://twitter.com/AtCoder4

株式会社PFU様

採用情報

A Dif:7

はじめに空の文字列を用意します。
Kが1以上なら"A"を付け足します。
Kが2以上なら"B"を付け足します。
Kが3以上なら"C"を付け足します。
...
これを"Z"までやれば答えが出せます。(【提出1】)

できなくはないけどちょっとめんどくさいですね。
楽をするなら文字コードを文字に変換するchrを使いましょう。
パソコンで扱う文字にはそれぞれ文字コードという数字が割り振りされています。
"A"なら65，"B"なら66、...という感じです。
chr(文字コード)と書くことで文字コード→文字へ変換できます。
よって65+0,65+1,...65+(K-1)までchrで変換しながらくっつけていけばOKです。
1~(K-1)までiに順に格納しながら処理をするときは
for i in range(K):
と書きます。
(【提出2】)

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

【提出1】

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

# 空の文字列を用意
ans=""

# Kが1以上なら
if 1<=K:
    # "A"を追加
    ans+="A"
if 2<=K:
    ans+="B"
if 3<=K:
    ans+="C"
if 4<=K:
    ans+="D"
if 5<=K:
    ans+="E"
if 6<=K:
    ans+="F"
if 7<=K:
    ans+="G"
if 8<=K:
    ans+="H"
if 9<=K:
    ans+="I"
if 10<=K:
    ans+="J"
if 11<=K:
    ans+="K"
if 12<=K:
    ans+="L"
if 13<=K:
    ans+="M"
if 14<=K:
    ans+="N"
if 15<=K:
    ans+="O"
if 16<=K:
    ans+="P"
if 17<=K:
    ans+="Q"
if 18<=K:
    ans+="R"
if 19<=K:
    ans+="S"
if 20<=K:
    ans+="T"
if 21<=K:
    ans+="U"
if 22<=K:
    ans+="V"
if 23<=K:
    ans+="W"
if 24<=K:
    ans+="X"
if 25<=K:
    ans+="Y"
if 26<=K:
    ans+="Z"

# 答えの出力
print(ans)

【提出2】

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

# 空の文字列を用意
ans=""

# i=0~(K-1)
for i in range(K):
    # ansに文字コード「65+i」の文字をくっつける
    ans+=chr(65+i)

# 答えの出力
print(ans)

B Dif:72

あるペアについて全問正解できるということは、すべての問題について少なくとも片方が「o」であるということです。
逆に言うと両方が「x」である問題が一問でもあればそのペアは全問正解できないということです。

まずは参加者Aと参加者Bのペアが全問正解できるかを判定する関数を作りましょう。
引数はSA,SBです。これらはそれぞれ参加者Aの正誤、参加者Bの正誤(Sの内容)を表します。
全問正解できるならTrue、そうでなければFalseを返します。

# A,Bのペアが全問正解できるか確認する関数
def Judge(SA,SB):
    # 全問正解できている間はOK=True
    OK=True
    # i=0~(N-1)
    for i in range(N):
        # SAのi文字目が「x」　かつ　SBのi文字目が「x」
        if SA[i]=="x" and SB[i]=="x":
            # OKをFalseに変更
            OK=False

    # OKを返す
    return OK

まずOKという変数をTrueにしておき、もし1問でも正解できない問題が出てきたらFalseに変更するという方法です。

これができたらあとは全ペアについて判定を行うだけです。これには二重ループを使います。

まずSの情報をリストに記録しましょう。これをSlistとします。
次に以下のようにループを2つ書きます。

# A,Bのペアが全問正解できるか確認する関数
def Judge(SA,SB):
    # 全問正解できている間はOK=True
    OK=True
    # i=0~(N-1)
    for i in range(M):
        # SAのi文字目が「x」　かつ　SBのi文字目が「x」
        if SA[i]=="x" and SB[i]=="x":
            # OKをFalseに変更
            OK=False

    # OKを返す
    return OK

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

# Sの情報を格納するリスト
Slist=[]

# i=0~(M-1)
for i in range(N):
    # 入力の受け取り
    S=input()
    # リストへ格納
    Slist.append(S)

# 答え
ans=0

# A=0~(N-1)
for A in range(N):
    # B=(A+1)~(N-1)
    for B in range(A+1,N):
        # 全問正解できるなら
        if Judge(Slist[A],Slist[B])==True:
            # 答えにカウント
            ans+=1

# 答えの出力
print(ans)

C Dif:104

「変換するスイッチ」を用意します。
これは「"」が来るたびにON、OFFが入れ変わるもので、ONになっている間は「,」を「.」に変換します。
最初はONです。

例を見てみましょう。
S：b",b",d
最初、スイッチはONです。
0文字目は「b」です。
1文字目は「"」です。ここでスイッチが切り替わり、OFFになります。
2文字目は「,」です。スイッチはOFFなので変換はしません。
3文字目は「b」です。
4文字目は「"」です。ここでスイッチが切り替わり、ONになります。
5文字目は「,」です。スイッチはONなので変換して「.」になります。
6文字目は「d」です。
最終的な答えは「b",b".d」です。

基本的にはこれで処理できるのですが、以下のように「"」の数が奇数の場合は少々厄介です。
S：b",b",d"a,
7文字目は「"」(3つ目)なのでこのタイミングでスイッチはONになるのですが、後ろに"がないため9文字目の「,」は変換してはいけません。
よって予め「"」の数を数えておき、奇数個かつ最後の「"」ではスイッチを切り替えしない(もう一度切り替えする)という処理を入れておきます。

実装ではスイッチをTrue,Falseや1,0などの変数にして解けばOKです。
True→False,False→Trueに変換するときはnotをつけます。

ちなみに「"」は普通の文字と同様に"""とダブルクオーテーションで囲っても文字列として認識されません。
"\""というように前にエスケープ記号「\」をつけます。

【提出】

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

# 「"」の個数
C=S.count("\"")

# 答え
ans=""

# 「変換するスイッチ」
Switch=True

# それまでに出現した「"」の個数
k=0

# i=0~(N-1)
for i in range(N):
    # Sのi文字目が「"」なら
    if S[i]=="\"":
        # 個数をカウント
        k+=1
        # スイッチの切替
        # True→False,False→True
        Switch=not Switch

        # 合計個数が奇数　かつ　最後の「"」ならば
        if C%2==1 and k==C:
            # スイッチを再度切り替え
            Switch=not Switch

    # スイッチがONなら
    if Switch==True:
        # S[i]をくっつける(「,」ならば「.」へ変換)
        ans+=S[i].replace(",",".")
    # そうでなければ(スイッチがOFFならば)
    else:
        # S[i]をくっつける
        ans+=S[i]

# 答えの出力
print(ans)

D Dif:1154

まずは図を書いて考えてみましょう。
例えば以下のようなグラフの場合

色分けすると図のようになります。

左のグラフ(連結成分)をグラフ1(①～⑥)、右のグラフをグラフ2(⑦～⑨)として情報をまとめてみます。
「グラフ1」
辺：5　赤：2　青：4
「グラフ2」
辺：2　赤：2　青：1

では二部グラフのままで辺を追加するにはどこからどこを繋げばいいでしょうか。
まずグラフ1の中では赤↔青につなげばいいですね。(①↔④,①↔⑤,①↔⑥)
赤は2個、青は4個なので組み合わせを考えると辺の引き方は2*4=8通りになりますが、すでに辺が5本あるので8-5=3となります。

同様に考えるとグラフ2の中で赤は2個、青は1個で、2*1=2通りからすでにある辺を2本引いて2-2=0となります。

次にグラフ1からグラフ2を考えましょう。
例えば①→⑧をつなげても二部グラフのままであることは簡単にわかります。
更に①→⑦につなげたとしても、グラフ2の色をすべて反転させれば二部グラフのままになります。
(⑦,⑨を青、⑧を赤にすればいいですね)
まとめるとグラフ1とグラフ2のどの頂点を結んだとしても二部グラフにできるということです。
グラフ1は頂点が2+4=6個、グラフ2は2+1=3個頂点があるので合計6*3=18個の組み合わせができます。

そういうわけで合計3+0+18=21が答えになります。

これを一般化すると
(1)各連結成分ごとにグラフ1，グラフ2、...と番号を割り振り、頂点に色を付ける
(2)グラフ1、グラフ2、...ごとに(赤の個数)*(青の個数)-(辺の本数)を計算して足す
(3)グラフ1、グラフ2、...の頂点数の組み合わせを掛け算して足す
という操作になります。
ただし、例えばグラフ10000まである場合、(3)で普通に組み合わせを計算すると10000C2回の計算が必要になり、TLEしますので工夫が必要です。
例えば頂点の数がグラフ1=4個、グラフ2=5個、グラフ3=8個、グラフ4=12個だった場合、4*5+4*8+4*12+5*8+5*12+8*12になりますね。
これを(4*(5+8+12)+5*(4+8+12)+8*(4+5+12)+12*(4+5+8))/2と計算すれば計算回数を減らすことができます。
つまり(グラフiの頂点数)*(頂点数の総和-グラフiの頂点数)をi=1,2,3,...について計算して、最後に2で割るということです。

二部グラフの塗り分けはBFSで行えばOKです。

BFSを書いたことがないという人にはこの問題は難易度が高いので、まず易しい問題で練習することをおすすめします。
ABC209Dあたりがおすすめです。
問題：https://atcoder.jp/contests/abc209/tasks/abc209_d
解説：https://qiita.com/sano192/items/faf544347362c3f89630#d---collision

各頂点について、グラフ番号と色の情報を保持し、頂点1からスタートする場合、頂点2からスタートする場合、...と順に処理します。
すでに色が塗られているならスルーです。
なお、ひとつでも二部グラフにできないグラフがあったらその時点で答えは0になります。

【提出】

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

# つながっている頂点の格納リスト
connect=[[] for i in range(N+1)]

# グラフに含まれる辺の本数を数えるためのリスト
EdgeList=[]

# M回
for i in range(M):
    # 入力の受け取り
    A,B=map(int, input().split())
    # 頂点Aから出ている辺が1本ある
    EdgeList.append(A)
    # A→Bへ行けることを記録
    connect[A].append(B)
    # B→Aへ行けることを記録
    connect[B].append(A)

# 各頂点の情報
# [グラフの番号,色]
vertice=[[0,"White"] for i in range(N+1)]

# グラフの番号
GraphNo=1

# dequeのインポート
from collections import deque

# 頂点を順に探索
# i=1~N
for i in range(1,N+1):
    # i番目の頂点色が白ならば
    # ↔まだ色が塗られていない
    if vertice[i][1]=="White":
        # キューを用意
        que=deque()
        # キューへ頂点iを追加
        que.append(i)
        # 頂点iにグラフ番号を記録
        vertice[i][0]=GraphNo
        # 頂点iに赤色を塗る
        vertice[i][1]="Red"

        # キューが空になるまで
        while 0<len(que):
            # キューから頂点を取り出す
            # 今いる頂点
            Now=que.popleft()
            # 今いる頂点のグラフ番号、色
            NowNo,NowColor=vertice[Now]

            # To：今いる頂点から行ける頂点
            for To in connect[Now]:
                # 行ける頂点のグラフ番号、色
                ToNo,ToColor=vertice[To]
                # 行ける頂点の色が白
                if ToColor=="White":
                    # グラフ番号を割り振り
                    vertice[To][0]=GraphNo
                    # 今いる頂点の色が赤
                    if NowColor=="Red":
                        # 青を塗る
                        vertice[To][1]="Blue"
                    # 今いる頂点の色が青
                    else:
                        # 赤を塗る
                        vertice[To][1]="Red"
                    # キューへ追加
                    que.append(To)
                # 今いる頂点と行ける頂点の色が同じ
                # ↔二部グラフにできない
                elif NowColor==ToColor:
                    # 0を出力
                    print(0)
                    # 終了
                    exit()

        # 次のグラフ番号へ
        GraphNo+=1

# 各グラフ番号ごとの頂点本数
EdgeCount=[0]*(GraphNo+1)
# 各グラフ番号ごとの赤、青の頂点個数
GraphRB=[[0,0] for i in range(GraphNo+1)]

# x：EdgeListの各要素
for x in EdgeList:
    # 頂点xから出ている辺が一本ある
    # ↔頂点xが所属するグラフ番号へ辺の本数をプラス1
    EdgeCount[vertice[x][0]]+=1

# 各頂点のグラフ番号、色
for Number,Color in vertice:
    # 赤色なら
    if Color=="Red":
        # 所属するグラフ番号の赤色の個数をプラス1
        GraphRB[Number][0]+=1
    # 青色なら
    else:
        # 所属するグラフ番号の青色の個数をプラス1
        GraphRB[Number][1]+=1

# 答え
ans=0
# 各グラフ番号ごとの頂点個数
GraphEdgeCount=[0]*(GraphNo+1)

# i=1,2,3,...=(グラフ番号)
for i in range(1,GraphNo+1):
    # 赤、青の個数
    R,B=GraphRB[i]
    # (赤の個数)*(青の個数)-(辺の本数)
    ans+=R*B-EdgeCount[i]
    # 頂点の個数(赤の個数+青の個数)を追加
    GraphEdgeCount[i]=R+B

# 合計
CountSum=sum(GraphEdgeCount)
# 計算結果格納
tmp=0

# i=1,2,3,...=(グラフ番号)
for i in range(1,GraphNo+1):
    # 計算
    tmp+=GraphEdgeCount[i]*(CountSum-GraphEdgeCount[i])

# 2で割って追加
ans+=tmp//2

# 答えの出力
print(ans)

【広告】

『AtCoder 最速で緑になる 基礎・典型50問詳細解説』

ABC201～250から基礎・典型問題50問をとてつもなく丁寧かつ詳細に解説した本(kindle)、pdf(booth)です。
灰色、茶色コーダーにおすすめ！
値段：100円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BBB7RKTP

【booth(pdf)】
https://booth.pm/ja/items/4102300

冒頭5問をサンプルとして無料公開しています
https://qiita.com/sano192/items/6361ed72106cb6dd5843

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

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

【booth(pdf)】
https://sano192.booth.pm/items/3179185

1～24問目まではサンプルとして無料公開しています
https://qiita.com/sano192/items/eb2c9cbee6ec4dc79aaf

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

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

サンプルを5問分公開しています
https://qiita.com/sano192/items/3258c39988187759f756

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVK3SLV

【booth(pdf)】
https://booth.pm/ja/items/3698647

ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B09TVKGH17/

【booth(pdf)】
https://sano192.booth.pm/items/3698668

『AtCoder ABC226～250 ARC129～139 灰・茶・緑問題 超詳細解説』

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

サンプルを4問分公開しています
https://qiita.com/sano192/items/f8f09ea769f2414a5733

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G13QMS

【booth(pdf)】
https://sano192.booth.pm/items/4025713

ARC129～139の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0B7G337YF

【booth(pdf)】
https://sano192.booth.pm/items/4025737

『AtCoder ABC251～275 ARC140～151 灰・茶・緑問題 超詳細解説』

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

サンプルを4問分公開しています
https://qiita.com/sano192/items/810a4a7d5cf61321bb05

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

値段：300円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BRNTM9Z4

【booth(pdf)】
https://sano192.booth.pm/items/4455120

ARC140～151の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
https://www.amazon.co.jp/dp/B0BRNRXPCV

【booth(pdf)】
https://sano192.booth.pm/items/4455133

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

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

サンプルとして「準備」～「三目並べ」を無料公開しています。
https://qiita.com/sano192/items/9a47e6d73373d01e31fb

【kindle】
https://www.amazon.co.jp/dp/B09XLM42MW

【booth(pdf】
https://sano192.booth.pm/items/3785312