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

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

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

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

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

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

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

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

rot90(行列回転)　　　　　　　　　　　　　　　　　・・・　問題B
defaultdict (コンテナデータ型、辞書のサブクラス)　・・・　問題C

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

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

AtCoder Beginner Contest 298

A問題：Job Interview

A – Job Interview

問題(要約)

評価を表す長さNの文字列Sにおいて、下記条件が満たすかを判断する

良 (“o”) が一つでも含まれている
不可 (“x”) が一つも含まれていない

解答

# 番号1
n=int(input())
S=input()

# 番号2
result=False

# 番号3
for s in S:
    if s == "o":
        result=True
    elif s == "x":
        result=False

# 番号4
if result:
    print("Yes")
else:
    print("No")

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

入力を受け取る
- 入力nは整数のため、input()で受け取り、整数型(int)に変換(キャスト)を行っている
- ２行目の入力は文字列のため、input()で受けとる (文字列のまま扱う)
条件が当てはまるかどうかを判断するため、boolean型(True/False)の変数resultを準備する
初期値は、Falseに設定しておく
for文を用いて一つづつの文字を確認する
- カウンタ変数を s とし、文字列 S を一つづつ取り出す
  - 取り出した文字列 s が、o (良) と等しい場合は、resultをTrueとする
  - 取り出した文字列 s が、x (不可) と等しい場合は、resultをFalseとする
boolean型のresultの結果を確認する
- もし、result = Trueの時は、print関数で “Yes” を出力する
  ＊ boolean型を用いる場合、==True を省略することができる
- もし、result = Falseの時は、print関数で “No” を出力する

B問題：Coloring Matrix

B – Coloring Matrix

問題(要約)

N行N列のA, Bがあり、Aを好きな回数回転させて(0回も含む)、A_i,j = 1部分がB_i,j =1 が成立するかを判断する

解答

# 番号1
import numpy as np

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

# 番号3
rotA = []
for k in range(4):
    rotA.append(np.rot90(A,k))

# 番号4
for r in rotA:
    result = True
    for i in range(n):
        for j in range(n):
            if r[i][j] ==1 and B[i][j] !=1:
                result = False
        if result == False:
            break
    else:
        exit(print("Yes"))

# 番号5
print("No")

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

モジュールnumpyをインポートし、このコード上では、np として呼び出せるようにする
入力を受けとる
- 入力Nは数字のため、input()で入力を受け取り整数型(int)に変換する
- 入力Aは、N行に渡る入力になるため、内包表記を用いて2次元配列の形で入力を受けとる
  - １行も空白区切りで与えられているため、input()で受け取り、split()で空白区切りに分割
  - map関数を用いて各要素に整数型(int)を適用する
  - map関数の形式を配列に変換する
  - (内包表記) 上記のリストの操作をfor文回繰り返す
    (入力例1の場合)　A＝[[0, 1, 1], [1, 0, 0], [0, 1, 0]] の2次元配列を得られる
- 入力Bは、入力Aと同じ形式のため、上記同様に取り込みをする
行列Aを回転させて得られる行列を作成する
- for文とnumpyのrot90関数を用いて、４種類(反時計回りに90度,180度,270度,360度)の回転行列を作成する
  - np.rot90関数は、括弧内に (行列、回転数) を与えることにより行列を回転できる
  - 回転数は、反時計回り90度を基準として、90 * (1+回転数) となる
    つまり、回転数が0の時は、90度回転を行い、回転数4の時は回転前と同じになる
  - 上記で作成したN行N列の配列を配列rotAに追加する(appendを用いて追加)
番号3 で作成した回転行列に対して、要求されている条件が当てはまるかを確認する
- 配列rotAを一つづつfor文を用いて取り出す
  - 条件が当てはまっているかを確認するため、boolean型のresult (Trueで初期化) を定義する
  - N行N列の全箇所を調べるために、二重for文を作成する
  - 外側のfor文は、行方向を取り出す
    - 内側のfor文は、列方向を取り出す
      - if文を用いて以下の条件に当てはまっているかを確認する
      - 回転行列の i 行 j 列が1であり、行列Bの i 行 j 列が1ではない
        
        確認しようとしている回転行列は、条件に当てはまらないため、
        result = False にする
    - 変数result=Falseの場合は、現在の回転行列では条件に当てはまらないため、これ以上の検索は無意味なため、break で外側のfor文を抜ける
      ＊内側のfor文内でbreakを使っても、内側のfor文を抜けるだけになるため、この位置で使っている
  - for文のelse関数を用いて、for文が一通り処理できた後の処理を決めておく。
    途中のbreakでfor文を抜けなかった場合に実行される
    - result=TrueでN行N列の回転行列AとBを確認し、条件に合っていることになる
      - print関数で “Yes” を出力し、exit関数でコードをぬける
exit関数でコードを終了することが出来ない場合にこの行になるため、print関数で “No” を出力する

C問題：Cards Query Problem

C – Cards Query Problem

問題(要約)

　1からNまでの番号がついたN個の箱と、何も書かれていない無数のカードがあり、Q個の処理を実行する

1 i j : カードを1枚選んで、数 i を書き込み、箱 j に入れる
2 i : 箱 i に入っているカードの全ての数を昇順で答える
＊同じカードが複数枚ある場合は、入っている数だけ出力すること
3 i : 数 i が書かれたカードが入っている箱の番号を昇順で全て答える
＊数 i が書かれたカードが複数枚同じ箱に入っていても、箱の番号は1度だけ答える

解答

# 番号1
from collections import defaultdict

# 番号2
n=int(input())
q=int(input())

# 番号3
box=[list() for _ in range(n+1)]
num=defaultdict(set)

# 番号4
for _ in range(q):
    tmp=list(map(int,input().split()))
    if tmp[0]==1:
        box[tmp[2]].append(tmp[1])
        num[tmp[1]].add(tmp[2])
    elif tmp[0]==2:
        print(*sorted(box[tmp[1]]))
    else:
        print(*sorted(num[tmp[1]]))

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

collectionsモジュールのdefaultdict関数をインポートする
- 辞書型のサブクラスで、各keyに対して簡単にリスト, 集合などを登録できる
- from … import 関数名　とすることにより、コード内で直接関数名を用いる事ができるcollections.defaultdict() と記載しなくて良くなる
入力を受けとる
- Nは整数型なので、input()で受け取り整数型(int)に変換(キャスト)する
- QもNと同様に受けとる
カードを格納しておく箱とカードに対する箱番号がわかるための空配列と空集合を準備する
- 箱の数は、1始まりのため n+1 個の空の2次元配列を準備する
  例： [ [ ], [ ], [ ], ・・・, [ ] ] : 内側の[ ]がそれぞれの箱を示し、外側の[ ] が箱全体
- defaultdictを用いて、集合(set)の辞書型を準備する
  例：{ key1 : { item1-1, item1-2, … }, key2 : { item2-1, item2-2, … } }
  ＊集合を用いることにより、重複を排除することができる
各クエリを実行していく
- 与えられるクエリはQ個のため、for文をQ回繰り返す
  - 与えられるクエリをtmp配列で受けとる
    - クエリの種類につき配列数が異なるため、配列型で受けとる
  - 入力の1文字目の数字がクエリの種類を表すため、tmp[0]で条件分けを行う
  - tmp[0]が1の場合
    - カードに数 tmp[1] を書き込み箱 tmp[2] を代入する
      - つまり、配列boxのtmp[2]番目にtmp[1]を追加する
        　　box[tmp[2]].append(tmp[1])
    - カード tmp[1] が箱 tmp[2] に関連付ける
      - つまり、辞書型でカード tmp[1] をキーとして、箱 tmp[2]をvalueとして設定する
        　　num[tmp[1]].add(tmp[2])
        　　＊集合のため、appendでなく、addを用いる
  - tmp[0]が2の場合
    - 箱 tmp[1] に入っているカードを全て昇順で出力する
      - 昇順を行えるsorted関数を用いて、配列を昇順化を行う
      - リストのアンパック(＊)を用いることにより、リストを空白区切りで出力が可能になる
  - その他 (tmp[0]が3) の場合
    - カード tmp[1] に関連付いている箱を昇順で出力する
      - 集合でまとめているが、上記tmp[0]==2の時と同様な考え方を行える
        （sorted関数、リストのアンパック）