(ABC289)A-C問題のpythonでの解法

AtCoder
2023.03.31

こんにちは、こんぶちゃ(茶コーダー)です！

初心者視点から競プロAtCoderのABC289のA問題〜C問題の自身の解答と解答説明をしていきます。

こんな人にオススメしたい
  • 競技プログラミング初心者で、問題の解き方がわからない方
  • AtCoderの公式解説は読んだが、内容が理解できなかった方
  • Pythonでの解法を知りたい方

まだまだ学習の身ですので、最適コードではない部分も多々あるかと思いますが、その部分は同じ学習者として温かい気持ちで応援＆ご助言頂けば嬉しいです。

では早速行ってみましょう！

今回使用している機能・アルゴリズム
  • deque (コンテナデータ型、スタック・キュー)　　　・・・　問題B
  • defaultdict (コンテナデータ型、辞書のサブクラス)　・・・. 問題C
  • bit全探索　　　　　　　　　　　　　　　　　　　　・・・　問題C

今回の参加コンテスト(ABC289)

AtCoder Beginner Contest 289

A問題：flip

A – flip

問題(要約)

0と1からなる文字列sにおいて、0→1、1→0 に置き換えた文字列を出力する

解答

s=input()

for c in s:
    if c == "0":
        print(1,end="")
    else:
        print(0,end="")
print()

考え方

  1. 入力の文字列を受け取る
  2. for文を用いて、文字列sから一文字づつ取り出す
    • if文を使って、取り出した単語c が 0 と等しかったら、print文で数字の1を出力する。
      ただし、print文は改行を伴うため、endのオプションを入れることにより、改行をなくす
      ＊ 0にダブルクォーテーションがついているが、これは0を文字列のままで扱っている。
    • 取り出した単語cが 1 と等しかったら、print文で数字の0を出力する。
      こちらも上記同様に、print文のendオプションを用いる
  3. atCoderの回答の最後には改行が必要なため、空のprint()を用いることにより改行を追加する

B問題：レ

B – レ

問題(要約)

漢文の読み順を求める問題。
　1からNまでの数字列が小さい順に並べてあり、整数間にMこの レ点 が挟まっている。

  • 下記の条件以外の時は、左から順番に数字を読み上げる。
  • 数字の次に レ点 がある場合は、右隣の数字を先に読み上げる。
    ただし、右隣の数字にレ点がついていた場合は、更に右隣の数字を先に読み上げる
    • 右隣にレ点がなければ、一つづつ戻りながら数字を読み上げていく

問題の説明文では、グラフを使っていましたが、わたしはデックを用いて解きました。

解答

# スタックとキューを一般化したdeque(デック), double-ended queueを用いる
# 右からも左からも自由に取り出せるコンテナ(筒のイメージ)
# collectionsモジュールからdeque関数を利用できるようにする
# from ... import 関数名　とすることにより、コード内で直接関数名を用いる事ができる
# collections.deque() と記載しなくて良くなる
from collections import deque

# 空白区切りのnとmをinput()で受け取り、split()を用いて分割(リスト化)
# map関数を用いて、リストのそれぞれにintを適用する
n,m=map(int,input().split())
# 上記同様に受け取り、全体をリストで扱うためlist()化する
A=list(map(int,input().split()))

# 下記参照
d=deque()
ans=[]
for i in range(1,n+1):
    if i in A:
        d.append(i)
    else:
        ans.append(i)
        while len(d)>0:
            ans.append(d.pop())
print(*ans)

考え方

  1. d = deque() で変数dをコンテナ型(deque)として扱えれるようにする
  2. 回答の数を保存するための空リストansを作成
  3. 回答の数字は、１始まりの数字であるため、i をカウンタとして1〜 n+1までfor文を繰り返す
    ＊ i の数字の範囲は、1, 2, … , n-1, n までの範囲になる(n+1は入らないことに注意)
  4. リストAは、レ点がついているところの番号リストであるため、if文を用いて、カウンタ i がリストAに入っているかを確認
    • カウンタ i がAに含まれている場合は、レ点のため読まれないため、デックdに一時保管する
    • カウンタ i がAに含まれていない場合は、回答の配列ansにカウンタ番号 i を追加する
      • レ点により、デックdに保管されている物をwhile文を用いて、デック→ans配列に移動する
      • while文の繰り返し条件は、len(d)>0 とすることにより、デックdの中身が入っている間繰り返しを実行している
        • d.pop()により、デックdに入っているものを右側から一つ取り出し(デックdの中身も削除)、ans配列に追加(append)を行う
      • 例：”３ レ 4 レ 5 “の場合
        • 一つ目の3にはレ点があるため、デックdに保存(d=[3]
        • 二つ目の4にもレ点があるため、デックdに保存(d=[3,4])
        • 三つ目の5にはレ点がないため、ansに5を追加(ans=[5])
        • デックd=[3,4]には二つの要素が入っているため、while文を実行する
        • d.pop()でデックdから一つと取り出して、ans配列に追加する
          (d=[3], ans=[5,4])
        • d=[3]の為、再度while文を実行する
        • d.pop()でデックdから一つと取り出して、ans配列に追加する
          (d=[], ans=[5,4,3])
  5. リストのアンパック(リスト内全てを空白区切りで出力)を用いて、print文でansを出力

C問題：Coverage

C – Coverage

問題(要約)

　1以上N以下の数字の集合がM個あり(S1, S2, … , SM)、それぞれの集合Siは1以上N以下の数字で構成されている。任意に集合を選び、選んだ集合の組み合わせに1〜Nまで全て含まれている組み合わせの数を求める。

解答

# 辞書型のサブクラスで、各keyに対して簡単にリストを登録できるdefaultdict関数を用いる
# collectionsモジュールからdefaultdict関数を利用できるようにする
# from ... import 関数名　とすることにより、コード内で直接関数名を用いる事ができる
# collections.defaultdict() と記載しなくて良くなる
from collections import defaultdict

# 空白区切りのn,mの入力を受け取り、map関数にて整数型(int)に変換(キャスト)を行う
n,m=map(int,input().split())

# 以下参照
S=defaultdict(set)

for i in range(m):
    c=int(input())
    tmp=list(map(int,input().split()))
    for t in tmp:
        S[i].add(t)
cnt=0
for i in range(2**m):
    comb=[]
    for j in range(m):
        if (i>>j) & 1:
            comb.append(1)
        else:
            comb.append(0)
    tmp_set=set()
    for k in range(m):
        if comb[k] == 1:
            tmp_set.update(S[k])
    if len(tmp_set)==n:
        cnt+=1
print(cnt)

考え方

  1. 変数Sを辞書型サブクラスのdefaultdictとして扱う設定を行う。
    ( )内に辞書型のvalue(右側)の型を宣言する。ここでは集合(set)で設定する。
    例：　S = { “key” : {1, 2, 3}}　コロンの右側が集合として取り扱われる
  2. 入力で与えられている集合を取り込み変数Sに取り込む
    • 与えられる個別の集合はm個ある為、for文をm回繰り返す。
      また、カウンタに i を用いることにより、取り込んだ集合が何番目に当たるかをカウントする
      • それぞれの集合の個数を示す入力cを取り込む(このコードではcは使っていない)
      • 空白区切りの集合をリスト化しtmpに一時保存する
        (この後に、変数Sに代入するための仮保管)
      • for文を用いて、リストtmp内の一つづつ取り出す
        • リストtmpから一つづつ取り出した t を変数Sに登録していく
        • S[i].add(t) は、辞書型のキーを i とし、value(コロンの右側)に.addで追加していく。valueは集合型と設定しているため、addを用いている
      • 入力例1では、{0: {1, 2}, 1: {1, 3}, 2: {2}} となる
  3. 組み合わせをカウントするために変数cntを初期値0で準備する
  4. bit全探索を用いて集合Sが取りうる場合を全て確認する
  5. それぞの集合において、選択する、選択しないの2択になるため、2mの組み合わせが存在する。
  6. for文を用いて全ての組み合わせを実施する
    pythonでは階乗はアスタリスク2つ( ** )で示す
    • bit全探索で生成される組み合わせを一時的に記憶するための空のcomb配列を準備する
    • ビット全探索を用いて、個数mが取りうる組合せのパターンを作成する
      ＊ 下に3個の集合の場合の一例を載せています
  7. 各集合をマージするための空の集合tmp_setを準備する
  8. comb配列から1になっている所を上記の集合tmp_setに追加を行うためfor文を用いる
    • もし、comb[i] が 1 になっていれば、update()関数を用いて、tmp_set集合を更新していく。(update関数で他の集合を一括で追加可能)
  9. tmp_set集合は集合の為重複は排除されるため、tmp_set集合が長さ n と等しければ、n までの全ての要素を含んでいることが言えるため、長さを確認する
    • tmp_set集合の長さが n と等しい場合は、cnt に 1 をたす。
  10. それぞれの要素数を簡単に数えるために、イテレータ生成関数のitertoolsを利用する。
    import itertools でこのコードでitertoolsモジュールを使えるようになる

＊　集合3つの場合の組み合わせ一覧 (bit全探索の補足)

上記のコードでは、

  1. “for i in range(2**m)” 部分が23の組合せ
  2. “for j in range(m)” 部分が0,1,2ビットシフト
  3. 上記1の２進数化と上記2のビットずらしを “if (i>>j) & 1” で判断している

組み合わせリストを[S1, S2, S3]として扱っている

23の組合せ2進数化0ビットシフト1ビットシフト２ビットシフト組合せリスト
0000000[0, 0, 0]
1001100[1, 0, 0]
2010010[0, 1, 0]
3011110[1, 1, 0]
4100001[0, 0, 1]
5101101[1, 0, 1]
6110011[0, 1, 1]
7111111[1, 1, 1]

感想

B問題が、レ点の問題に関しては問題文の意図はグラフでの回答の記載だったが、思いつきませんでした。他の方法でも対応ができる柔軟力がついたと考え、勉強を続けたいと思います。

それでは、良い競プロライフを〜！

コメント

タイトルとURLをコピーしました