初心者必見！40代サラリーマンが競プロでPythonチャレンジ【ABC307_A-C問題】

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

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

こんな人にオススメしたい

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

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

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

今回使用している機能・アルゴリズム

順列(permutations) 　　　　　　　　　　　　・・・　問題B

今回の参加コンテスト(ABC307)
感想

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

AtCoder Beginner Contest 307

A問題：Weekly Records

A – Weekly Records

問題(要約)

日々の歩数が与えられる。各週の歩数の合計を求める

解答

# 番号1
n=int(input())
A=list(map(int,input().split()))

# 番号2
weekly=[]
total=0

# 番号3
for i in range(1,7*n+1):
    total+= A[i-1]
    if i%7==0:
        weekly.append(total)
        total=0

# 番号4
print(*weekly)

考え方 (下の番号は、コード内のコメント番号と連携している)

for文を使って、7日間区切り(7で割って余り0)になったら、そこまでの合計を出力する

以下、プログラム内容詳細

入力n, Aを受け取る
weeklyとtotalの変数を準備する
- weekly: 週ごとの歩数を記憶する(リスト型)
- total: 日毎の合計を出して格納する
for文を1から 7*n+1 まで繰り返す
- 標準の0からにすると、余り検出の時に１番目の余りが0になるのを避ける為
- totalに日々の歩数を足す
- if文を用いてカウンタ変数 i 割る 7 の余りが 0 かどうかを判断する
  - 条件に当てはまったら、weeklyの配列にtotalの数を追加
  - 次の週の合計のためにtotalを0にする
配列のアンパック（*：アスタリスク）を用いて空白区切りでweeklyの値を出力する
for文を文字数回分 (n回) 繰り返す

B問題：racecar

B – racecar

問題(要約)

英小文字からなるN個の文字列が与えられる。その文字列の中から2つ取り出し連結させた文字列が回文になるかどうかを判断する

解答

# 番号1
from itertools import permutations

# 番号2
n=int(input())
S=[input() for _ in range(n)]

# 番号3
for a,b in permutations(S,2):
    ss = a + b
    # 番号3-1
    for i in range(len(ss)//2):
        if ss[i]!=ss[-i-1]:
            break
    else:
        exit(print("Yes"))

# 番号4
print("No")

考え方(下の番号は、コード内のコメント番号と連携している)

順列を生成できるpermutationsを用いて、すべての組み合わせの順列を作成し、回文であるかを確認する

itertoolsモジュールのpermutations(順列)をインポートする
入力 n, S を受け取る。Sは内包表記を用いて複数行にわたる入力を受け取る
permutationsを用いて順列を作成し、for文に適用することにより全ての組み合わせを取り出す
- permutationsは第1引数に配列、第2引数に順列の要素数を指定 (今回は2つ)
- permutationsはタプルで戻す。要素数を2つにしている為、for文でa,bの2つを受け取る
- 二つの文字列を繋げたものを変数ssに代入する
  1. for文を用いて回文であるかどうかを判断する
    - 繰り返し回数は、文字列の半分にする。前半と後半が同じことが確認できればいい為。
    - スライスを用いて、ss[i] == ss[-i-1] を確認する。
      ＊ i = 0 の場合: ss[0] == ss[-1] となり、初めと最後の文字を指定できる
    - 上記のss[i] == ss[-i-1] が成り立たなければ、現在のssは回文ではないため、breakで次の文字列の確認に進む
    - breakされなかった場合にfor文のelseに移行する、つまり、回文であるため、”Yes”と出力しながらプログラムを終了させる
途中でプログラムが終わらなかった、つまり、回文が見当たらなかたため、Noを出力する

C問題：Ideal Sheet

C – Ideal Sheet

問題(要約)

黒いマス # と透明なマス . からなるシートA, Bを1枚ずつと、透明なマスのみからなる無限に広がるシートCが与えられる。また、黒いマスと透明なマスからなる理想とするシートXがある。シートA, B, C から、シートXが作り出せるかを判断する

解答

# 番号1
hashA,hashB,hashX=[],[],[]
Hash = [hashA, hashB, hashX]

# 番号2
for k in range(3):
    h,w = map(int,input().split())
    mp = [list(input()) for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if mp[i][j]=="#":
                Hash[k].append((i,j))

# 番号3
setHashX = set(hashX)

# 番号4
for i in range(-11,11):
    for j in range(-11,11):
        tmpA=set()
        for k in range(len(hashA)):
            tmpA.add((hashA[k][0]+i, hashA[k][1]+j))

        # 番号4-1
        if tmpA <= setHashX:

            for m in range(-11,11):
                for n in range(-11,11):
                    tmpB = set()
                    for l in range(len(hashB)):
                        tmpB.add((hashB[l][0]+m, hashB[l][1]+n))
                    
                    # 番号4-2
                    if (tmpA | tmpB) == setHashX:
                        exit(print("Yes"))
# 番号5
print("No")

考え方(下の番号は、コード内のコメント番号と連携している)

各シートの黒マスの関係性に着目し、最後に抜けがないかを確認している

各シートの黒マス # の座標位置を取り出す
透明なシートへの貼り付けは任意の位置にできるので、可動できる全ての範囲に各シートを動かす
動かしたシートAとシートBの組み合わせがシートXに一致しているかを調べる

以下詳細

入力を効率的に取得するための変数を設定する
- hashA, hashB, hashX: 各シートの # 位置を記憶する
- Hash: 上記の３つをリスト化 (for文で一括処理するため)
入力を受け取り、# の位置をHashに格納する
- カウンタ変数 k : シートA, B, X の３つに繰り返すため繰り返し回数を3回に指定
- カウンタ変数 i : 各シートの縦方向
- カウンタ変数 j : 各シートの横方向
- for文とカウンタ変数 i, j を用いて、各シートを全スキャンする
  - マーク # があった位置の i, j を各hash* に追加する
    ＊ appendは一項目づつしか追加できないため、( ) タプル形式にしている
シートXの # と比較するために、集合に変換する
＊検索スピード：　リスト　<<　集合　(集合の方が断然早い！直接指定)
シートAを透明シート上に配置する全パターンを考える
- 各シートは 10 x 10 であるため、上下左右全てに動かした場合を想定し、for文の範囲を-11~ 11 に設定する
  ＊少し余分な可能性もあるが、# のみに注目することによりfor文の回数は低減
- シートAの # 位置を移動させた後の # の位置を格納する tmpA (集合) を用意する
- hashA に格納されている番地全てを i, j 分動かして tmpA に格納する
  1. tmpA が setHashX に含まれる(包括)されているかを確認する
    ＊集合演算子 “<=” を用いている。集合演算子まとめは、補足参照
    - 全てのtmpAがsetHashXに含まれている場合は、今度はシートBについてもシートAと同様に確認する
    - カウンタ変数は、m, n を用い、tmpBに移動後のシートBの # 位置を保持する
  2. tmpAとtmpBを組み合わせた位置が、setHashBと同じ場合に、過不足なくシートXを表せれることになる
    - つまり、tmpAとtmpBの和集合 (tmpA | tmpB) と setHashXが等しいかを比較する
    - 上記が成り立つ場合は、”Yes”を出力し、プログラムを終了させる
Yesの場合は、プログラムが途中で終了するため、最終行まで辿り着いた場合は”No”を出力する

補足：pythonでの集合演算子

pythonで使える集合演算子をchatGPTにまとめて頂きました

記号	集合演算子	意味	例
\|	union	和集合	A \| B
&	intersection	積集合	A & B
–	difference	差集合	A – B
<=	issubset	包含関係をチェック	A <= B
<	<	真包含関係をチェック	A < B
>=	issuperset	逆包含関係をチェック	A >= B
>	>	真逆包含関係をチェック	A > B
set()	–	空集合を作成	set()
in	–	属するかどうかをチェック	x in A
not in	–	属さないかどうかをチェック	x not in A