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

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

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

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

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

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

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

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

積集合(集合の共通部分抽出)　　　　　　　・・・　問題C

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

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

AtCoder Beginner Contest 296

A問題：Alternately

A – Alternately

問題(要約)

N人が一列に並んでおり、男性(M)と女性(F)が交互に並んでいるか確認する

解答

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

# 番号 2 - 4
for i in range(1,n):
    if S[i-1] == S[i]:
        exit(print("No"))
print("Yes")

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

入力nとSを受け取る
- 入力nは整数のため、input()で受け取り、整数型(int)に変換(キャスト)を行っている
- Sは文字列で与えらるため、そのままinput()で文字列のままで扱う
男性(M)と女性(F)が交互になっていない、つまり、Sの隣同士が等しかったら”No”を出力する
MMやFFとなっていたら、”No”とする
for文を1番目からn番目まで繰り返し隣同士が等しいかを比べる
ポイント：0番目をスキップしていることにより、比べる対象の文字列Sの範囲外になるのを防ぐ
- スライス[ ]を用いて文字列Sの一文字を取り出し、if文で隣同士が等しいかを確認する
  - もし、隣同士 S[i-1] と S[i] が等しかったら、print文で”No”を出力しながら、exit()関数でプログラムを終了させる
for文において、隣同士が等しい場合が見つからなかった場合、つまりプログラムが途中で終了しなかった場合(exit()関数でプログラムを抜けない)、正しい並びになっているためprint文で”Yes”を出力する

B問題：Chessboard

B – Chessboard

問題(要約)

駒が一つ置かれており、チェス盤のどの位置に置かれているかを回答する

解答

# 番号1,2
S=[list(input()) for _ in range(8)]

# 番号3
R = [8,7,6,5,4,3,2,1]
C = ["a","b","c","d","e","f","g","h"]

# 番号4
for i in range(8):
    for j in range(8):
        if S[i][j]=="*":
            print(C[j],R[i],sep="")

考え方

8行に渡って入力されるチェス盤と駒の位置( * )を受け取る
内包リストを用いることにより一行で2次元配列を取り込むことができる
- 1行目S₁入力をinput()で取り込み、list関数にてリスト化を行う
  入力例1の場合：S₁ = [‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’] 見づらいですが、ピリオド( . )が8つ並んでいる
- list(input())の後のfor文により、for文直前の処理(list(input())を8回(range(8))を繰り返す
  カウンタは必要ないため、_ (アンダーバー：空を意味する) とする
- 配列Sは、[ [S₁], [S₂], [S₃], … , [S₇], [S₈]] の2次元配列となる
- 内包表記にするために、外側を [ ] で囲む
上記No.2で取り込んだ配列の位置に合わせて、チェス盤の位置を定義する
- 配列Sの左上は、[0][0]番地に対して、チェス盤は横(C)：a、縦(R)：8にあたる
  ＊縦の配列の番号と順番(配列は縦横、チェス盤は横縦)に注意が必要になる
2重のfor文を用いて、2次元配列Sの一つづつ確認していき、アスタリスク( * ) があった場合は、座標番号を出力する
外側のfor文は縦方向を順番にカウントしていく。カウンタを i とする
- 内側のfor文は横方向を順番にカウントしていく。カウンタを j とする。
- 2次元配列のスキャンの方向は、1行目の左 → 右、2行目の左 → 右、・・・順
  - 2次元配列S[i][j]の要素が ” * “であるかを確認する
    - アスタリスク(” * “)が見つけられたらチェス番地を出力する。
    - 配列Sのi, jとチェス盤のi, jをNo.3で関連づけて定義しているため、それぞれのカウンタ番後をそのまま用いてR[i], C[j]でチェス盤位置を取得することができる
      ただし、縦横並びが逆になっていることは注意が必要
    - print文でチェス盤の位置を出力する。横と縦の間の空白を削除するためsepのオプションを用いて、空白をなくす

C問題：Gap Existence

C – Gap Existence

問題(要約)

長さNの配列A=(A₁,A₂, … , A_N) があり、A_i – A_j = X となるものが存在するか判断する

解答

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

# 番号2
# 番号3
def add_to_each(a):
    return a + x

# 番号4
B = set(map(add_to_each, A))

# 番号5
if len(A & B)>0:
    print("Yes")
else:
    print("No")

考え方

入力 n, x と集合Aの取り込みを行う
- 空白区切りで与えられるn, x をinput()で取り込み、split()でそれぞれに分割する(リスト化)。
  map関数を用いて、リストそれぞれに整数型(int)に変換(キャスト)する
- 空白区切りの集合Aを上記同様に取り組み。一つの集合として扱うためset()を適用する
  本問題では、集合の積集合(共通部分判定)を行いたい為、集合として扱う
与えられた数式 Ai – Aj = X ( i, j は集合Aの任意の場所を選べる) を変形する
- Ai – Aj = X を書き直すと、Ai = X + Aj
- Ai と Aj は集合Aの任意の場所を選べれるため、下記を満たせればAi – Aj = X の判断ができる
  - 集合Aの各要素にXを足し合わせた新たな集合の中に、集合Aの要素を含んでいるか
集合Aの各要素にXを足し合わせるための自作関数add_to_each()を作成する
- 集合Aの各要素aを入力した場合に、 a + x を返す関数を作成する
集合Aの各要素にXを足し合わせた集合Bを作成する
- map関数を用いて、集合Aの各要素に対して、自作関数add_to_eachを適用する
- map関数の出力はmapオブジェクトになっているため、set関数を用いて集合として扱う
- 上記で作成した集合を集合Bとする
集合Aと集合Bの共通部分がないかを判断する
- 積集合(共通部分)を用いることにより、集合Aと集合Bの積集合( & )を取得する
- len関数を用いて、上記の積集合の数をカウントする
  - 積集合の数が1以上(共通部分がある)場合は、”Yes”を出力する
  - 上記にあてはまらない場合(共通部分無し)の場合は、”No”を出力する