LoginSignup
1
1

More than 1 year has passed since last update.

@sano192

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

Last updated at Posted at 2022-08-17

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

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

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

freee株式会社様について

本コンテストはfreee株式会社様が主催されています。
詳細はホームページを御覧ください。

A - "atcoder".substr()　Dif:8

pythonでは文字列SのL~R番目を
S[L:R+1]
と書きます。Rではなく(R+1)となることに注意してください。
また、先頭の文字を0文字目、次を1文字目、...というように数えるため、問題文でいうL,R番目から一つずれます。
以上からL~R文字目は
S[L-1:R]
とすれば出力ができます。

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

【提出】

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

# 「atcoder」をSへ格納
S="atcoder"

# (L-1)~(R-1)番目を出力
print(S[L-1:R])

B - Nice Grid　Dif:55

行、列に番号を振ってみます。
ABC264_B_1.png

行1に対して列1~15
行15に対して列1~15
列1に対して行1~15
列15に対して行1~15

行3に対して列3~13
行13に対して列3~13
列3に対して行3~13
列13に対して行3~13
...
という部分が黒に塗られていることがわかります。
これを二次元配列で実際に作ってしまいましょう。
最初は15*15で全ての要素が0での二次元配列を作ります(実際には0行目、0列目があるので16*16です)
そして上記の行、列番号を黒で塗ったという意味で1にします。
あとは(R,C)のマスが0か1か確認すればOKです。

【提出】

# 入力の受け取り
R,C=map(int,input().split())
# マス目を作る
# 最初は全てのマスが0
Grid=[[0]*16 for i in range(16)]

# i=1~15
for i in range(1,16):
    # 1行i列=1
    Grid[1][i]=1
    # 15行i列=1
    Grid[15][i]=1
    # i行1列=1
    Grid[i][1]=1
    # i行15列=1
    Grid[i][15]=1

# i=3~13
for i in range(3,14):
    Grid[3][i]=1
    Grid[13][i]=1
    Grid[i][3]=1
    Grid[i][13]=1

# i=5~11
for i in range(5,12):
    Grid[5][i]=1
    Grid[11][i]=1
    Grid[i][5]=1
    Grid[i][11]=1

# i=7~9
for i in range(7,10):
    Grid[7][i]=1
    Grid[9][i]=1
    Grid[i][7]=1
    Grid[i][9]=1

# R行C列が1ならば
if Grid[R][C]==1:
    # 「black」を出力
    print("black")
# R行C列が0ならば
else:
    # 「white」を出力
    print("white")

C - Matrix Reducing　Dif:758

Aに対して操作を1回ずつ行うと考えるのではなく、残す行、列をどれにするかと考えます。
行、列は最大10です。行それぞれについて残す、残さないという二択になるので2^10通りのパターンがあります。列も同様です。
よって全体のパターン数は
2^10*2^10=2^20=1048576
となります。だいたい10^6なのでこれなら全パターン試しても間に合います。

全てのパターンを試すために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)(N桁)と代入して順に確認ができます。

右から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=101であり、
101 & 1 =1
となりますから、右から3桁目は1とわかります。

bit全探索の解説動画を作りましたので、本問が難しいと感じた方は是非御覧ください。
シフト演算、アンド演算についてより詳細に解説しています。

本問では行、列それぞれに2進数を作り、桁ごとに行、列を残すか決めます。0なら消す、1なら残すという形です。
ABC264_C_1.png

実装では以下のようにします
(1)行の2進数を作る(GyouBit=Gb)
(2)列の2進数を作る(RetuBit=Rb)
(3)空の配列(Aremove)を作る。※最終的にAremoveとBが一致するかを確認します
(4)0行目、1行目、...について、Gbの0桁目、1桁目を見て残す行か確認
(5)(残す行なら)空の配列(Retu)を作る
(6)0列目、1列目、...について、Rbの0桁目、1桁目を見て残す行か確認。残す列なら要素をRetuへ追加
(7)RetuをAremoveへ追加
これで行、列のうち残すもの(2進数の桁が1の行、列)だけがAremoveへ残りますので、Bと一致するか確認します。

pythonでは間に合わないのでpypyで提出します。

【提出】

# pypyで提出

# 入力の受け取り
H1,W1=map(int,input().split())
A=[]

# i=0~(H1-1)
for i in range(H1):
    # リストとして受け取り
    tmp=list(map(int,input().split()))
    # Aに追加
    A.append(tmp)

# 入力の受け取り
H2,W2=map(int,input().split())
B=[]

# i=0~(H2-1)
for i in range(H2):
    # リストとして受け取り
    tmp=list(map(int,input().split()))
    # Bに追加
    B.append(tmp)

# (1)行の2進数を作る(GyouBit=Gb)
for Gb in range(1<<H1):
    # (2)列の2進数を作る(RetuBit=Rb)
    for Rb in range(1<<W1):
        # (3)空の配列(Aremove)を作る
        Aremove=[]

        # i=0~(H1-1)
        for i in range(H1):
            # (4)0行目、1行目、...について、Gbの0桁目、1桁目を見て残す行か確認
            # ⇔Gbの右からi桁目と1をアンド演算して1なら残す
            if Gb>>i & 1 ==1:

                # (5)(残す行なら)空の配列(Retu)を作る
                Retu=[]

                # k=0~(W1-1)
                for k in range(W1):
                    # (6)0列目、1列目、...について、Rbの0桁目、1桁目を見て残す行か確認
                    # ⇔Rbの右からi桁目と1をアンド演算して1なら残す
                    if Rb>>k & 1 ==1:
                        # 残す列なら要素をRetuへ追加
                        Retu.append(A[i][k])

                # (7)RetuをAremoveへ追加
                Aremove.append(Retu)
                        
        # 操作後のAとBが一致したら
        if Aremove==B:
            # 「Yes」を出力
            print("Yes")
            # 途中終了
            exit()

# 「No」を出力
print("No")

D - "redocta".swap(i,i+1)　Dif:414

まず「a」の位置を確認し、先頭に来るまで入れ替え操作を行います。
次に「t」の位置を確認し、2番目に来るまで入れ替え操作を行います。
次に「c」の位置を...
と操作を繰り返すのが最適戦略です。これをこのまま実装できればOKです。

・Sをリストへ展開する
入れ替え操作を行う時、文字列のままだと扱いづらいので1文字ずつリストへ展開しましょう。
list(S)と書くことで展開ができます。

・「a」の位置を確認
Sの何番目が「a」かを確認します。
リスト.index(文字)とすれば「文字」が何番目にあるかを確認できます。

・入れ替え
リスト[x],リスト[y]=リスト[y],リスト[x]
と書くとリストのx番目とy番目を入れ替えることができます。よく使う書き方なので覚えておきましょう。

【提出】

# 入力の受け取り
S=input()
# 「atcoder」をTに格納
T="atcoder"

# 1文字ずつリストへ展開
Slist=list(S)

# 答え
ans=0

# i=0~6
for i in range(7):
    # Tのi文字目がSlistの何番目か確認
    indx=Slist.index(T[i])

    # indxがiでない(正しい位置に来ていない)間
    while indx!=i:
        # indx番目と(indx-1)番目を入れ替え
        Slist[indx],Slist[indx-1]=Slist[indx-1],Slist[indx]
        # 次の文字へ
        indx-=1
        # 操作回数をカウント
        ans+=1

# 答えの出力
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 灰・茶・緑問題 超詳細解説 AtCoder 詳細解説』

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

『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

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1