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

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

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

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

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

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

AtCoder Beginner Contest 301

A問題：Overall Winner

A – Overall Winner

問題(要約)

TとAからなる長さNの文字列Sが与えられており、各試合の勝者を示している。T：高橋くん、A：青木くん　が勝者。勝った試合が多い方を出力する。ただし、勝った数が同じ場合は、先にその勝ち数に到達した者を出力する

解答

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

# 番号2
# 番号3
if n%2 == 0:
    required_wins = n//2
else:
    required_wins = n//2 + 1

# 番号4
win_cnt_A,win_cnt_T = 0,0

# 番号5
for s in S:
    if s=="A":
        win_cnt_A+=1
        if win_cnt_A==required_wins:
            exit(print("A"))
    else:
        win_cnt_T+=1
        if win_cnt_T==required_wins:
            exit(print("T"))

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

1. 入力を受け取る
   • 整数型 n の入力を受け取る
     • input()で入力を受け取る
     • int()で整数型に変換する(キャスト)
   • 文字列 S の入力を受け取る
     • input()で入力を受け取る。文字列のまま扱う為、追加の処理は必要なし
2. 解法の方針
   • 勝利数が同数の時に先に勝利数に達した方を出力必要がある為、下記のステップで考える
     • 必要勝利数を先に求める
     • その勝利数に到達した時点で勝者を出力する
     • その時点でプログラムを終了させる
3. 試合数が偶数の時と奇数の時で必要勝利数が変わるため、if文を用いて試合数が偶数かどうかを調べる
   • n%2==0、つまり n を 2 で割った余りが 0 の時 (偶数) 時
     • 必要勝利数 required_wins は n // 2、n を 2 で割った商とする
       例：4試合の場合は、先に2勝した方が勝者 ( required_wins = 4//2 = 2)
   • n%2==0が成り立たない時、奇数の時
     • 必要勝利数 required_wins は n // 2 + 1、n を 2 で割った商に1を加算する
       例：3試合の場合は、先に2勝した方が勝者 (required_wins = 3 // 2 + 1 = 2)
4. 青木くんと高橋くんの勝利数をカウントする変数をも準備する。初期値は0とする
   • pythonだと式の左側の変数の数と式の右側の値の数を合わすことにより1行で記載ができる
5. for文を用いて、文字列Sを一つづつ調べていく
   • カウンタ変数 s が”A”の時、
     • 青木くんの勝利数カウントを加算、つまり、win_cnt_Aに1を足す
       win_cnt_A += 1 は、win_cnt_A = win_cnt_A + 1と同じ意味
     • 青木くんの勝利数が要求勝利数 (required_wins) に達しかを確認する。つまり、if文を用いて、required_wins と win_cnt_A が一緒かを確認する
       • 条件が成り立てば、青木くんの勝利が確定するため、print文で A を出力させながら、プログラムを終了させる
         ＊プログラムの終了はexit関数で実行できる
   • カウンタ変数 s が”T”の時も青木くんの時と同様に対応が可能である
     win_cnt_A -> win_cnt_T に変換、出力は T を出力 する必要はある

B問題：Fill the Gaps

B – Fill the Gaps

問題(要約)

どの隣接する2項の値が異なる長さNの正整数の数列Aにおいて、下記の操作を行うことによりできた数列を出力する

• どの隣接する2項の差の絶対値も1である時、操作が終了する
• 隣接する2項の差の絶対値が1出ない時、2項間の差分の整数を挿入する
  例：　A=[2, 5] の時、2, 5の間の整数3, 4を挿入し、A=[2, 3, 4, 5]となる
  　　　A=[5, 2] の時、5, 2の間の整数4, 3を挿入し、A=[5, 4, 3, 2]となる

解答

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

# 番号2
# 番号3
B=[]

# 番号4
for i in range(1,n):
    B.append(A[i-1])
    if abs(A[i-1] - A[i]) != 1:
        if A[i-1]<A[i]:
            for j in range(A[i-1]+1,A[i]):
                B.append(j)
        else:
            for j in range(A[i-1]-1,A[i],-1):
                B.append(j)
B.append(A[-1])
print(*B)

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

1. 入力を受け取る
   • 入力Nをinput()で受け取り、整数型(int)に変換する(キャスト)
   • 空白区切りの数列Aを受け取る
     • input()で入力を受け取る
     • split()で空白区切りを行いリスト化する
     • map関数を用いて各要素に対して整数型(int)を適用する
     • listを用いて、mapオブジェクトを配列化を行う
2. 解答の方針としては、問題文の通りに進める。ただし、解答の配列を別に準備し、そこに格納していく。
3. 解答を格納する配列Bを準備する
4. for文を用いて2項の差を確認していく。
   • 2項の差を取り扱うため、0番目からではなく1番目からにしている
     ＊range関数の詳細は下記補足をつけています
   • 2項 A[i-1]と A[i] を比較していく前に A[i-1] を解答の配列Bに格納する
     • 2項を比較し、差の絶対値が 1 になっているかを確認する
       if文では、!= を用いて1以外であるかを確認している。
       ＊abs()関数は絶対値を求める関数
       • 2項の絶対値の差が1出ない場合を更に分岐させる
       • A[i-1] が A[i] よりも大きい場合と小さい場合で分岐をさせる
         ＊補完する数字がプラスステップなのかマイナスステップなのかの条件分け
         • A[i-1] が A[i] よりも大きい場合、for文を用いて2項間を補完する
           ＊rangeの範囲に注意すること。下記補足にrange関数の補足参照
         • A[i-1] が A[i] よりも小さい場合、for文を用いて2項間を補完する
           ＊range関数に第3引数を用いて、マイナスステップにする必要あり
           　下記補足のrange関数を参照
5. 上記のfor文において、A[i-1] とその補完数までしか配列Bに登録されないため、数列Aの最後の数字を配列Bに登録する。スライスを用いて[ -1] を与えることにより、最後の配列が指定できる
6. 配列のアンパック(＊）を用いることにより空白区切りで配列Bを出力する

補足：range関数

range関数の使い方は引数を3つ取ることができます。

0から開始するため終了点の考え方や、ステップ数にマイナスを持ってきた場合に注意が間違えやすいと思います (自分はプログラムの途中でrange関数部を出力させて結果をよく確認しています)

＊上記の表はchatGPTでrange関数に関してまとめてもらっています

C問題：AtCoder Cards

C – AtCoder Cards

問題(要約)

英小文字と @ からなる2つの文字列S, Tが与えられています。下記の条件のもとで2つの文字列を一致できるかどうかを判断する

• 記号@は、a, t, c, o, d, e, r の任意の文字に置き換えることができる
• 文字列は好きに並び替えができる

解答

# 番号1
S=input()
T=input()

# 番号2
# 番号3
char_codesS = [0] * 26
char_codesT = [0] * 26
atsS,atsT = 0,0

# 番号4
for i in range(len(S)):
    if S[i]=="@":
        atsS+=1
    else:
        char_codesS[ord(S[i])-97]+=1
    if T[i]=="@":
        atsT+=1
    else:
        char_codesT[ord(T[i])-97]+=1

# 番号5
atCoder_nums=set()

# 番号6
for a in ['a', 't', 'c', 'o', 'd', 'e', 'r' ]:
    atCoder_nums.add(ord(a)-97)

# 番号7
for i in range(26):
    if char_codesS[i] != char_codesT[i]:
        if i in atCoder_nums:
            if char_codesS[i] > char_codesT[i]:
                atsT-= char_codesS[i] - char_codesT[i]
                if atsT < 0:
                    exit(print("No"))
            else:
                atsS-= char_codesT[i] - char_codesS[i]
                if atsS < 0:
                    exit(print("No"))
        else:
            exit(print("No"))
# 番号8
print("Yes")

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

1. 入力を受け取る
   • 文字列Sをinput()で受け取る
   • 文字列Tをinput()で受け取る
2. 解答の方針としては、下記の考え方で推進
   • それぞれのアルファベットとアットマークの数を格納しておく配列と変数を準備する
   • 記号アットマークが取りうるパターンを抽出（アルファベット番号を記憶）
   • アルファベットリストの差異を確認し、差異があった部分に関してはアットマークで埋めることができるを確認していく
3. 文字列SとTのそれぞれのアルファベット・アットマークを格納できる変数を準備する
   • アルファベットを格納する変数をchar_codesS, char_codesTを準備する
   • アルファベットは26個あるため、配列のインデックスを26個準備し、初期値を0とする
   • アットマークに関しても、文字列S、T分のそれぞれを準備する(atsS, atsT)
4. 文字列SとT、それぞれのアルファベットとアットマークの数を数える
   • for文を用いて、各文字列を取り出し適用する部分の配列の数を増やしていく
     • 配列Sの要素を抽出
       • S[i] が、アットマークの場合、atsSに1づつ加算していく
       • S[i] が、文字列の場合
         • 文字をord関数を用いて数字化を行う
           ＊英小文字は、a: 97　〜　z: 122 が割り当てられている
         • 配列char_codesSは、aのインデックスを 0 で扱いたいため、ordで求めた数字から97を引く
         • 文字列に適用したインデックスのchar_codesSの要素を1加算する
           例：char_codesS[0] = 1 の場合は、文字aが1つあることを示す
     • 配列Tの要素を抽出
       • 上述の配列Sと同様にatsT, char_codesTを求める
5. 記号 @ は、a, t, c, o, d, e, r と代替可能であるため、これらの文字が配列char_codes* のどのインデックスになるかを記憶する。
   • 集合 atCoder_nums を準備する
     ＊配列でも問題ないが順番要素を必要としないため、集合として扱う
6. for文で記号 @ の代替文字の要素を一つづつ取り出す
   • char_codes*配列と同様に、ord(要素) – 97 することにより各文字に対するインデックス番号を求める
   • atCoder_numsの集合にインデックスを追加していく(集合のため add を用いる）
7. それぞれのアルファベットの数を格納したchar_codes*を一つづつ比較する
   • char_codes*はアルファベットの数分のインデックスを持っているため、for文を26回繰り返す。カウンタ変数は i とする
     • char_codesSとchar_codesTの相対するインデックスの値が等しくないかを確認する
       • 等しくない場合は、インデックスの番号がatCoder_numsに含まれるかを確認する
         • カウンタ変数 i によって選ばれている文字に対して、どちらの数が多いかを確認する。つまり、どちらの＠で代替するかを確認する
           • char_codesS[I] > char_codesT[I] の場合は、atsTからカウンタ変数 i によって選ばれている文字の数の差分をatsTから引く
             • この時に、atsTがマイナスになっているかを確認する
               • atsTがマイナスになると＠で代用ができていない為、Noを出力し、プログラムを終了させる
           • char_codesS[I] < char_codesT[I] の場合は、atsSからカウンタ変数 i によって選ばれている文字の数の差分をatsSから引く
             • この時に、atsSがマイナスになっているかを確認する
               • atsSがマイナスになると＠で代用ができていない為、Noを出力し、プログラムを終了させる
       • インデックスの番号がatCoder_numsに含まれない場合は、アットマークで代用ができない。つまり、ゲームに勝てない。No を出力し、プログラムを終了させる
8. 上記のfor文において、NGのパターンがあった場合は、Noを出力しながらプログラムが終了する。そのため、この行まで辿り着いた = OKパターン ということがわかるため、print文で Yes を出力させる

感想

初め問題Cの解法が思いつかずに暫く悩みました。

アルファベット→数字 の考え方を思い出し、上記の解答を思いつきました。

熟考した後にACをとれたときは嬉しい！

まぁ、AtCoderの解法ではdefaultdictを使って私よりスマートに解答してますけど・・・。自分で導き出したということで。

自分のレベルの少し上を目指して来週からも取り組んでいこうと思います。

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