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

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

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

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

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

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

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

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

roll関数(行列シフト(スクロール))　　　　　　　　　・・・　問題B

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

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

AtCoder Beginner Contest 300

A問題：N-choice question

A – N-choice question

問題(要約)

整数A, BとN択の選択肢が与えられます。選択肢からA＋Bの解を選び、選択肢番号を回答する

解答

# 番号1
n,a,b=map(int,input().split())
C=list(map(int,input().split()))

# 番号2
for i in range(n):
    if a+b == C[i]:
        exit(print(i+1))

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

入力を受け取る
- 入力の1行目には、N A B が空白区切りで与えられいる為
  - input()で入力を取り込む
  - split()で空白区切りのリスト化を行う
  - map関数を用いて、各要素に対して整数型(int)を適用する
  - 要素の1番目をn, 要素の2番目をa, 要素の3番目をb に代入する
- 入力の2行目には、選択肢の要素が空白区切りで与えられているの為
  - 上記同様にinput()で取り込み、split()でリスト化し、map関数で整数型に変換する
  - map関数のままだと、mapオブジェクトの状態になっている為、list()を適用することにより、リスト化する
選択肢の値を一つづつ取り出し、a+bの条件に当てはまるかを確認する
- for文を用いて配列Cの要素を一つづつ取り出す
  - if文を用いて、a+b が各要素と等しいかを確認する
    - 条件が等しい場合は
      - 要素番号の調整を行う。つまり、カウンタ変数 i に +1 を行う
        
        配列の始まりは0番目始まり
        
        問題文は1番目はじまりのための調整
      - 条件が合う場合のは１条件のみのため、要望の番目が見つかったら、exit()関数を用いて、求める番目をprint()で出力しながらプログラムを終了させる

B問題：Same Map in the RPG World

B – Same Map in the RPG World

問題(要約)

縦Hマス横Wマスの2つのグリッドA, Bがあり、横方向のシフト(列ズラし)、または、縦方向のシフト(行シフト)を行い、2つのグリッドが等しくなるかどうかを判断する

解答

# 番号1
import numpy as np

# 番号2
h,w=map(int,input().split())
A=[list(input()) for _ in range(h)]
B=[list(input()) for _ in range(h)]

# 番号3
# 番号4
# 番号5
for i in range(h):
    rollAi = np.roll(A,i,axis=0)
    for j in range(w):
        rollAj = np.roll(rollAi,j,axis=1)
        bool=True
        for k in range(h):
            for l in range(w):
                if rollAj[k][l] != B[k][l]:
                    bool=False
                    break
            if bool==False:
                break
        else:
            exit(print("Yes"))
# 番号6
print("No")

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

モジュールnumpyをインポートし、このコード上では、np として呼び出せるようにする
＊行・列シフトを行うためにNumpyを用いる
入力を受けとる
- 空白区切りで入力されるH, Wの受け取り
  - input()で入力を受け取る
  - split()で分割し、リスト化する
  - map関数を用いて各要素に対して整数型(int)を適用する
  - リストの1番目の要素をh, 2番目の要素をw に代入する
- 入力Aは、h行に渡る入力になるため、内包表記を用いて2次元配列の形で入力を受けとる
  - input()で受け取り、配列(リスト)化を行う
  - (内包表記) 上記のリストの操作をfor文回繰り返す。[ ] で囲む
- 入力Bは、入力Aと同じ形式のため、上記同様に取り込みをする
Numpyのroll関数を用いて、全条件の横方向と縦方向のシフトを配列Aに適用し、配列Bと一致するかを調べる
- Numpyのroll関数は、下記の引数を伴う
  - 第1引数：シフトを行う配列
  - 第2引数：シフトを行う行・列数 (下・右方向にシフト)
  - 第3引数(axis= )：シフトを行う方向、axis=0 で行方向、axis=1で列方向
4重のfor文で全検索を行う。それぞれのカウンタ変数の役割は下記
- カウンタ変数 i：配列Aの縦方向のシフトを行う
- カウンタ変数 j：配列Aの横方向のシフトを行う
- カウンタ変数 k：行番地を指定
- カウンタ変数 l：列番地を指定
for文を用いてカウンタ変数 i を h 回繰り返す
- roll関数を用いて配列 A を縦方向のシフトを i行適用した配列 rollAi を作成する
- for文を用いてカウンタ変数 j を w 回繰り返す
  - roll関数を用いて配列 rollAi を横方向のシフトを j行適用した配列 rollAj を作成する
  - 探索の効率化のため、各要素の違いがあった場合は、現在の配列の要素比較を中断し、次の探索に行くためのboolean型の配列 bool を初期値Trueで作成する
  - ここからは作成した縦・横方向のシフト配列 rollAj と配列B の各要素を全探索で比較する
    - 行方向の位置をカウンタ変数 k を用いて示す
      - 列方向の位置をカウンタ変数 l を用いて示す
      - if文を用いて、配列 rollAj と B の要素[k][l] が違っているかを確認する
        
        違っている場合は、これ以上 rollAj を調べる必要がないため、boolをFalseにする
        
        breakで一番内側のfor文 (カウンタ変数 l の所) を抜ける
      - if文を用いて、boolがFalseかどうかを確認する
        
        bool=Falseの場合、その時の rollAj は B と異なっているため、ここでもbreakを行い、内側から２番目 (カウンタ変数 k の所) を抜ける
    - 各要素の違いがない場合のみ、else文を実行する。つまり、全ての要素で
      　rollAj = B が成り立った場合である
      - 成り立つ条件が見つかったため、printで Yes を出力しながら、exitでプログラムを終了させる
- 縦・横方向のシフトを行なっている配列 rollAj とB の各要素を比較した時に、違いがある場合に
条件を満たしている場合は、exit関数で途中でプログラムを抜けている。つまり、途中でプログラムを抜れなかった → 条件が満たせなかった事になるため、No を出力する

C問題：Cross

C – Cross

問題(要約)

縦Hマス横Wマスのグリッドが与えられ、各マスには # . のどちらかの文字が書かれています

#を使って幾つかのバツ印が面上に配置しているため、サイズに応じた数を求める

＊バツ印同しは繋がったり、共有したりしていない

解答

# 番号1
h,w=map(int,input().split())
C=[list(input()) for _ in range(h)]

# 番号2
N=min(h,w)
S=[0]*N

# 番号3
# 番号4
centerPoint=[]

# 番号5
for i in range(1,h-1):
    for j in range(1,w-1):
        if C[i][j]=="#" and C[i-1][j-1]=="#" and C[i-1][j+1]=="#" and C[i+1][j+1]=="#" and C[i+1][j-1]=="#":
            centerPoint.append((i,j))

# 番号6,7
for i,j in centerPoint:
    for s in range(1,N+1):
        if C[i-s][j-s]=="#" and C[i-s][j+s]=="#" and C[i+s][j+s]=="#" and C[i+s][j-s]=="#":
            pass
        else:
            S[s-2]+=1
            break

# 番号8
print(*S)

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

入力を受けとる
- 空白区切りで入力されるH, Wの受け取り
  - input()で入力を受け取る
  - split()で分割し、リスト化する
  - map関数を用いて各要素に対して整数型(int)を適用する
  - リストの1番目の要素をh, 2番目の要素をw に代入する
- 入力Cは、h行に渡る入力になるため、内包表記を用いて2次元配列の形で入力を受けとる
  - input()で受け取り、配列(リスト)化を行う
  - (内包表記) 上記のリストの操作をfor文回繰り返す。[ ] で囲む
解答は、サイズ毎のバツの個数を出力するため、先にサイズ毎の枠を作っておく
- Nは、H, W の最小値のため、N=min(h, w) で求める
- サイズ毎の個数をカウントする配列Sを作成する。個数はN個で初期値は0とする
  S = [0] * N -> S = [0, 0, 0, … 0] (N個の 0 のリストを定義できる)
次の手順で各サイズのバツ印を探していく
- バツ印の中心点を探す
- 各中心点に対して、バツ印のサイズを求める
バツ印の中心座標を記憶するための空配列 centerPoint を準備する
中心点になり得るグリッド位置を全検索を行う。最初の行と最終行は中心点になり得ないため、for文の範囲を1〜h-1 とする ( 0始まりのため、1番目は2行目を指す)
- 列方向に対しても行方向と同様な考えで、1〜w-1 の範囲でfor文を作る
  - if文で下記の条件が当てはまるかを確認する (中心点の条件を満たすか？)
    - 中心座標が # であるか (C[i][j] = “#”)
    - 中心座標から、左上、右上、右下、左下の４箇所が # であるか
      - 左上：C[i-1][j-1]==”#”
      - 右上：C[i-1][j+1]==”#”
      - 右下：C[i+1][j+1]==”#”
      - 左下：C[i+1][j-1]==”#”
    - 上記の条件が当てはまる場合は、i, j 座標をcenterPoint に追加する
      - リストの追加のため、appendを用いる
      - i, j を組みで保持するために、タプルの形( ) で追加する
配列 centerPoint に登録した中心点に対してそれぞれのバツのサイズを求める
centerPoint配列の各要素は、タプルの形で登録されているため、カウンタ変数に i, j を用いて、要素を取り出す
- for文を用いてsのサイズを1〜Nまで変えていき、それぞれのバツのサイズを求める
  - if文を用いて斜め4方向に # が存在するかを確認する
    - if文が成り立つ場合( # が存在する) は、何もしない (pass)
    - if文が成り立たない場合は、s-1 がサイズの大きさとなる
      - 解答用のリストSは 0 始まりのため、更に -1 をする
      - バツ印の個数カウントは、S[s-2]の要素を増やす
      - 今回のバツ印の個数カウントができたので、breakで抜け、次の中心点を調べる
求める回答は、配列内を空白区切りで出力のため、リストのアンパック(アスタリスク)を用いて出力を行う