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

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

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

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

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

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

AtCoder Beginner Contest 295

A問題：Probably English

A – Probably English

問題(要約)

英小文字からなる空白区切りの文字列Wが与えれ、これらのうち一つ以上下記の単語と一致するかを判断する
　判断する文字列：and, not, that, the, you 

解答

# 入力nを受け取り、整数型(int)に変換する
n=int(input())
# 空白区切りの文字列をsplit()を用いて分割する(リスト化される)
W=input().split()

# 下記参照
check_Words = ['and', 'not', 'that', 'the', 'you']

for w in W:
    if w in check_Words:
        exit(print("Yes"))
print("No")

考え方

1. 判断に用いる単語をリスト化(check_words)する。このリストに含まれるかを判断する
2. for文を用いて、配列Wの単語を一つづつ取り出す
   • if文を使って、取り出した単語w が check_words に含まれるかを確認する
     ＊ if文で “if 要素 in リスト” とすることにより、要素が入れるに含まれるか確認できる
     • 単語wがcheck_wordsに含まれていたら、”Yes”を出力しながらプログラムを終了させる
       ＊exit関数を用いることにより、プログラムを終了できる
3. 途中でプログラムが終了しなかった、つまり配列Wの中にcheck_wordsが含まれなかったことになるため、”No”を出力する

B問題：Bombs

B – Bombs

問題(要約)

　縦R行横C列の盤面があり、空きマス ” . ” (ピリオド)、壁マス ” # ” (シャープ)、爆弾配置マス 1〜9の数字(威力)、がそれぞれ置かれている。爆弾が爆発し、爆弾配置マスからのマンハッタン距離がその爆弾の威力以下であるマスは全て空きマス . に変わる。爆発後の盤面を表示する
　マンハッタン距離 = | r₁ – r₂ | + | c₁ – c₂ |

解答

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

# 空白区切りの入力R,Cを受け取り(input())、split()を用いて分割する(リスト化)
# map関数を用いてリストの各要素に対して、整数型(int)を当てはめる(キャスト)
r,c = map(int,input().split())

# 盤面をリスト化するため、内包表記を用いて入力を受け取る
# input()で一行目の入力を受け取り、list()でリスト化する
# 上記の処理をr回(行数分)繰り返す(for _ in range(r))
# for文のアンダーバーは、カウンタ変数が無いことを示している(iなどで置いても問題無し)
# 配列Bは [[一行目リスト], [二行目リスト], ・・・, [r行目リスト]] の形になる
B=[list(input()) for _ in range(r)]

# 下記参照
# 下記No.1,2部分
bombs=defaultdict(list)
walls=[]

# 下記No.3部分
for i in range(r):
    for j in range(c):
        if B[i][j].isdigit():
            bombs[B[i][j]].append((i,j))
        elif B[i][j]=="#":
            walls.append((i,j))

# 下記No.4,5, 6部分
broken=[]
for key in bombs:
    for rc in bombs[key]:
        for w in walls:
            dist = abs(rc[0]-w[0])+abs(rc[1]-w[1])
            if dist <= int(key):
                broken.append(w)

# 下記No.7,8の部分
for i in range(r):
    for j in range(c):
        if (i,j) in broken:
            print(".",end="")
        elif B[i][j].isdigit():
            print(".",end="")
        else:
            print(B[i][j],end="")
    print()

考え方

1. 爆弾の威力、座標位置を保持するために、bombsにdefaultdictのリスト型を適用する
   ＊ defaultdict() の( )内に、型を定義する事ができる、int, set, list など
   ＊ bombsのデータは、{key: [リスト]} の形をとる。入力例1だと、{ 1: [ 0, 1 ], 2: [ 3, 2 ]}
2. 壁の位置もリスト化するために空配列wallsを作る
3. 爆弾の威力・位置、壁の位置を取得する。盤面全ての位置を確認するため、r行方向とc列方向の２重のfor文を使う
   • if文で爆弾かどうかを判断するため、B[i][j]が数字かどうかを判断する
     ＊ B[i][j].isdigit()で文字列が数字かどうか判断し、数字ならTrueを返す
     • 盤面の値が数字なら、盤面の数字をkey、盤面の位置を値としてbombsに登録する
       ＊ bombs[ key ].append(盤面位置) の形で辞書に登録する
4. 爆弾で壊れた壁座標を保持しておくためにbrokenの空配列を準備する
5. ( for文内の大枠の考え方 )
   各威力の爆弾の位置と壁の位置から、マンハッタン距離を算出する。その距離が各威力内かどうかを判断し、威力内なら配列brokenに壁の座標を追加する
6. for文を用いて、辞書型のbombsから各keyを取り出す
   • 辞書型のbombsに取り出したkeyを与えることにより( bombs[key] )、各威力の座標リストを参照する。それをfor文で取り出すことにより、各威力の座標rcを取得する
     • 各爆弾の座標に対して、各壁との距離を求めるために、for文で各壁の位置wを取り出す
       • 取り出した爆弾の位置rc、壁の位置wからマンハッタン距離distを計算する
         ＊ rc, w は [R行, C列]のリスト型で格納してあるため、スライスで分解している
         ＊ abs関数は、( )内の絶対値を返す関数
         • マンハッタン距離が、爆弾の威力(key)以下かをif文で判断する
           • 上記が当てはまるなら、壁が壊れているため、配列brokenに座標を追加する
7. ( for文内の大枠の考え方)
   壊れた壁の位置を取得できたため、元の盤面を修正していく。一つづつprint関数で出力しながら修正を行う
   ＊ print関数の end オプションを用いる。end=”” にすることにより、改行が入らなくなる
   　 (print関数は改行での出力が基本となっている)
8. 盤面全ての位置を取得するために、外側のfor文で R行方向のカウンタ i を増やしていく(行方向スキャン)
   • 内側のfor文でC列方向のカウンタ j を増やしていく(列方向スキャン)
     • 座標 (i, j) が壊れた壁リストbrokenに含まれているかを確認する
       • brokenリストに含まれていれば、” . “を出力する(改行はなし)
     • 座標 (i, j) に爆弾が置かれていたかを判断する ( No.3と同様に isdigit関数を用いる)
       • 爆弾が置かれていた場合も、” . “を出力する(改行はなし)
     • 上記に当てはまらない場合は、元の盤面の情報( # か . )を出力する(改行無し)
   • 一行のデータ入力が完了したため、盤面の次の行に行くために改行が必要になる。中身が空のprint()を入力することにより改行だけを追加できる

C問題：Socks

C – Socks

問題(要約)

配列Aの中から、同じ数をペアを何組作れるか

解答

import itertools

n=int(input())
A=sorted(list(map(int,input().split())))

cnt=0
for key,group in itertools.groupby(A):
    num = len(list(group))
    cnt+=num//2

print(cnt)

考え方

1. それぞれの要素数を簡単に数えるために、イテレータ生成関数のitertoolsを利用する。
   import itertools でこのコードでitertoolsモジュールを使えるようになる
2. 入力nを取り込み、整数型(int)に変換する(キャスト)
3. 空白区切りの配列(A要素)を取り込み(input())、split()で空白区切りで分割しリスト化する。
   更に並び替えができるsorted関数を用いることにより、昇順に並び替えをする
4. ペアができた回数を記憶するために変数cntを用意し、初期値0にする
5. itertoolsモジュールの中のgroupby関数を用いて要素をグループにまとめ、for文でそれぞれを取り出していく (*1 下記に参考例を記載)
   　　　
   • groupはitertools.groupオブジェクトで出力されるためリスト化し、len関数を用いて要素の数を数える
     ＊itertools.groupオブジェクトは一度きりしか取得できないため、変数numに代入する
   • num(同じ要素の数)を2で割った商、つまり、ペアを作った回数を求め、cntに足す
     　cnt += num // 2 -> cnt = cnt + num // 2
     　＊ //：商を求める事ができる
6. ペアの数を足し合わせたcntを出力する

*1 itertoolsモジュールのgropuby関数のデータ構造

配列 B = [1, 1, 4, 4, 4, 7, 7] の配列において、groupby関数を使うことにより下記のように分類ができる。配列は昇順・降順にした方が扱いやすい(リスト内が更に分割される[[1],[1]] など)

上記の値を取り出すコードは下記になる

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

# itertoolsも利用できるようにする
import itertools

# 例としてBを下記で定義する
B=[1,1,4,4,4,7,7]

# 変数をgroupsにdefaultdictのリスト型を当てはめる
groups=defaultdict(list)

# itertoolsモジュールのgroupby関数を配列Bに適用し、for文を用いてkey, groupを取り出す
for key,group in itertools.groupby(B):
    # 辞書型のキーをkeyとし、生成されたgroupをリスト型にして追加する
    groups[key].append(list(group))

print(groups)
# 出力内容。{}の中が key: list の形となって出力されている
# defaultdict(<class 'list'>, {1: [[1, 1]], 4: [[4, 4, 4]], 7: [[7, 7]]})

感想

B問題が、爆弾の威力と位置の二つの値を扱う必要があり苦戦しました。時間はかかりましたが、解くことができました。前までだと解けなかったと思うので、少しずつですが実力がついてきていると信じて継続したいと思います。

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