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

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

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

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

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

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

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

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

順列(permutations) 　　　　　　　・・・　問題C

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

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

AtCoder Beginner Contest 302

A問題：Attack

A – Attack

問題(要約)

体力Aの敵に対して、1回の攻撃でBを減らせる場合に何回攻撃する必要があるか

解答

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

# 番号2
if a%b==0:
    print(a//b)
else:
    print(a//b+1)

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

a, bの入力を受け取る
aがbで割り切れない時は、1回追加で攻撃をする必要があるため、if文で条件分けを行う。
- a割るbの余りが0：a/bの商(a//b)を出力
- a割るbの余りが0ではない：a/bの商(a//b)に1を加算して出力

B問題：Find snuke

B – Find snuke

問題(要約)

縦Hマス x 横Wマスの各マス目に英小文字が書き込まれている。マス目の中に、s, n, u, k, e がこの順番に(縦・横・斜めのいずれかの方向)順番に1つだけ並んでいる。そのマス目を出力する

解答

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

# 番号2
words=["s","n","u","k","e"]
dh=[-1,-1,-1,0,1,1,1,0]
dw=[-1,0,1,1,1,0,-1,-1]

# 番号3
for i in range(h):
    for j in range(w):
        if S[i][j]==words[0]:
            # 番号3-1
            for k in range(8):
                # 番号3-2
                for n in range(1,5):
                    if 0<=i+n*dh[k]<h and 0<=j+n*dw[k]<w:
                        if S[i+n*dh[k]][j+n*dw[k]] != words[n]:
                            break
                    else:
                        break
                # 番号3-3
                else:
                    for n in range(5):
                        print(1+i+n*dh[k],1+j+n*dw[k])
                    exit()

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

入力h, w, Sを受け取る
- 入力 S は、内包表記を用いて、2次元配列で受け取る
for文の中で用いる定数を先に設定しておく
- wordsは、今回探す文字 s n u k e をリスト化しておく
- dh, dwは縦・横・斜めの移動座標を設定しておく。
  - 今回の設定では、左上から時計回りに設定。(dh[0], dh[w]) = (-1,-1)となる
外側の２重のfor文 (カウンタ変数 i, j ) にて、全てのマス目から”s” (words[0]) がないか調べる
1. 8方向(dh, dw)にwordsの残りの文字がないかを調べる
2. wordsを配列にしたことにより、”s”の場所からの移動距離と文字順を連携して調べることができる。例えば、行方向は、i+n*dh[k] で示し、ここの n がwordsの配列と連携できる
  - 下記の条件にあては増す場合は、break で for文を抜け、次の向き条件を確認する
    - dh, dwを足した値がマス目を超えた場合
    - wordsの配列に当てはまらなかった場合
3. 番号3-2のfor文(カウンタ変数 n)内でbreakが発生しなかった場合のみこの else 文を実行する。つまり、文字条件が見つかったことになるため、解答の出力形式に従って、解答を出力する

C問題：Almost Equal

C – Almost Equal

問題(要約)

英小文字からなる長さMの文字列N個S₁, S₂, …, S_N が与えられている。S_i は互いに異なる。文字列の順番を入れ替え(文字列自体は変更しない)、下記の条件を満たせれるかを確認する

文字列の順番を入れ変えた文字列をT₁, T₂, …, T_N とするとき、文字列 T_i の1文字を別の文字に変更したら、T_i+1 にすることができる

解答

# 番号1
import itertools

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

# 番号3
for perm in itertools.permutations([x for x in range(n)]):
    # 番号3-1
    for i in range(1,n):
        # 番号3-2
        cnt=0
        for j in range(m):
            if S[perm[i-1]][j] != S[perm[i]][j]:
                cnt+=1
        # 番号3-3
        if cnt != 1:
            break
    # 番号3-4
    else:
        exit(print("Yes"))
print("No")

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

解法としては、文字列順の全てのパターンを列挙し、文字数の違いが1つだけかを判断していく

イテレーター(itertools)をインポートする
- 文字列の順番の組み合わせを列挙するために活用
入力をそれぞれ受け取る
- 文字列Sは、内包表記を用いて2次元配列で受け取る
文字列順の全ての組み合わせをitertoolsのpermutationsを算出しfor文で取り出す
1. 文字列順のT_i-1とT_iを比較するため、1 〜 n まで for文を繰り返す
2. 変数cntで T_i-1 と T_i の文字の差異数を数える。カウンタ j で文字数分確認する
  - S[perm[i]][j]の構成としては、perm[i]で生成した順列の組みのi番目を抽出し、S[perm[i]]で文字列Sのperm[i]番目を選択し、その j 文字目を指している
3. cnt≠1の時は、条件を満たさないため、breakで現在の順列を抜けて次を確認する
4. cnt条件が全て満たす時のみ else が実行されるため、Yes を出力してプログラムを終了させる
途中でプログラムが終了しなかったということは、条件に見合うことができなかったため、Noを出力する

補足：順列(permutations)

イテレーターのpermutations(順列)は、2つの引数を取る。以下の引数説明とその下のコードを参照

第1引数：順列を作りたいリスト
第2引数：いくつの順列を作りたいか

import itertools

# 第2引数に 3 を渡した場合
for perm in list(itertools.permutations([1,2,3],3)):
    print(perm)

# 出力
"""
>>(1, 2, 3)
>>(1, 3, 2)
>>(2, 1, 3)
>>(2, 3, 1)
>>(3, 1, 2)
>>(3, 2, 1)
"""

# 第2引数に 2 を渡した場合
for perm in list(itertools.permutations([1,2,3],2)):
    print(perm)

# 出力
"""
>>(1, 2)
>>(1, 3)
>>(2, 1)
>>(2, 3)
>>(3, 1)
>>(3, 2)
"""