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

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

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

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

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

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

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

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

置換(replace関数)　　　　　　　・・・　問題B
文字列シフト(自作rolling)　　　・・・　問題C

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

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

AtCoder Beginner Contest 286

A問題：Range Swap

A – Range Swap

問題(要約)

長さNの数列Aが与えられており、P番目からQ番目の項とR番目からS番目の項までを入れ替えた数列を出力する

解答

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

# 番号2
# 番号3
A[p-1:q],A[r-1:s]=A[r-1:s],A[p-1:q]

# 番号4
print(*A)

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

入力nを受け取る
- 空白区切りで、N, P, Q, R, S が与えられている為、下記の処理を行いながら受け取る
  - input()で入力を受け取る
  - split()で空白区切りでリスト化を行う
  - map関数により、各要素に対して整数型(int)に変換する(キャスト)
  - リストの0番目をn, 1番目をp, 2番目をq, 3番目をr, 4番目をs に代入する
- 空白区切りで、数列Aの要素が与えられている為、下記の処理を行いながら受け取る
  - input()で入力を受け取る
  - split()で空白区切りでリスト化を行う
  - map関数により、各要素に対して整数型(int)に変換する(キャスト)
  - mapオブジェクト形式になっているため、list()で配列化を行う
pythonの値の入れ替えとスライスを用いる
- 値の入れ替え
  - 例）a=1, b=2 の時に、a, b = b, a とするとaとbの値が入れ替えができる
    　　つまり、a=2, b = 1 となる
- スライス
  - 配列の後に[ ] をつける事により、その箇所の配列だけを取り出すことができる
    例）A=[1,2,3,4,5] の時に、A[1:3] = [2,3] となる
    ＊範囲に注意 [a:b] の時は、インデックス a から b-1 までになる
- 上記の値の入れ替えとスライスを用いる事により、P番目からQ番目の項とR番目からS番目の項を入れ替える。配列Aを直接入れ替えを行なっている
配列Aを直接入れ替えたため、配列のアンパック（＊）を行いながら出力する。
アンパックは、配列の前にアスタリスクをつける事により、配列内の要素を空白区切りで出力ができる。
if文を用いて下記の条件式が成り立つかを判断する

B問題：Cat

B – Cat

問題(要約)

長さNの文字列Sの na を全て nya に置き換えて得られる文字列を出力する

解答

# 番号1
n=input()

# 番号2
print(input().replace("na","nya"))

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

入力を受け取る
- 入力Nをinput()で受け取る。コードで使用する必要がないので、受け取るだけ
文字列を受け取りながら変換を行う
- input()で文字列を受け取る
- replace関数を用いる事により、第１引数の部分を第２引数に変換する
- print文で nya に変換した文字列を出力する

C問題：Rotate and Palindrome

C – Rotate and Palindrome

問題(要約)

長さNの文字列Sに対して、回文にするコストを求める。各操作は以下の費用がかかる

A円掛かる：Sの左端の文字列を右端に移動する
B円掛かる：任意の1文字を好きなSiに入れ替える

解答

# 番号1
def rolling(str , n):
    return str[n:] + str[:n]

# 番号2
n,a,b=map(int,input().split())
s=input()

# 番号3
# 番号4
ans=float('inf')

# 番号5
for i in range(n):
    rolls=rolling(s,i)
    cnt=0
    for j in range(n//2):
        if rolls[j] != rolls[-j-1]:
            cnt+=1
    ans=min(ans,a*i + b*cnt)

# 番号6
print(ans)

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

自作関数rollingを定義する
- 第1引数にstr(文字列)、第2引数に n(整数)を設定する
- この関数の機能としては、スライスを用いて整数 n 分を左側にシフトする
  - str[ n : ] 部分で、文字列 str の n 文字目から最後まで抽出
  - str[ : n] 部分で、文字列 str の最初からn 文字目までを抽出
  - returnで上記を足し合わせたものを戻す事により、文字列を n 文字分シフトできる
入力を受け取る
- 空白区切りの入力a, b, n を受け取る
  - map関数で整数型に変換して、各要素に代入する
- sは文字列のまま受け取る
rolling関数を用いて、全てのパターンの費用を算出し、最低の金額を出力する
最小金額を保持するための変数ansを準備する。初期値は、無限大に設定する (pythonでは、float(‘inf’)で設定できる)
文字列 s の文字数分シフトの全組み合わせ確認するため、for文を文字数分だけ繰り返す。
- 定義したrolling関数を用いて、文字列 s をfor文のカウンタ変数 i 分シフトし、変数rollsに代入する
- 作成したrollsが回文にするために何文字変更が必要かをカウントするため、変数cntを準備する
- 上記のcntを求めるために、for文を文字列の半分の数(n//2)実行する
  - if文を用いて先頭から j 文字目と後ろから j 文字目を比較する
  - 先頭は、インデックス 0 が1文字目、後ろからは、インデックス -1 が1文字目のため、rolls[j] (先頭から)とrolls[-1-j] (後ろから) となる
    - 先頭からと後ろからの文字が異なる場合は、cntを１増やす
- 変数 ans を最小値に更新する
  - min関数を用いて下記の２つを比較し、小さい方をansとする
    - 現状のans値
    - 文字列を i分シフトした費用 a * i 、文字変換を行う費用 b * cnt を足し合わせたもの。つまり、今回作成した文字列rollsを回文にするための費用
変数 ans は最小費用になっているため、ansを出力する