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

AtCoder

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

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

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

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

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

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

AtCoder Beginner Contest 299

A問題:Treasure Chest

A – Treasure Chest

問題(要約)

3種類の文字 ( . | * ) (ドット, 縦棒, アスタリスク) からなる文字列Sにおいて、下記の条件が満たすかどうかを判断する

  • * が 2本の縦棒 ( | ) の間に位置しているかどうか

解答

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

# 番号2
# 番号3
Tate=[]
Kome=[]

# 番号4
for i in range(n):
    if S[i]=="|":
        Tate.append(i)
    elif S[i]=="*":
        Kome.append(i)

# 番号5
if Tate[0] < Kome[0] < Tate[1]:
    print("in")
else:
    print("out")

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

  1. 入力を受け取る
    • 入力nは整数のため、input()で受け取り、整数型(int)に変換(キャスト)を行っている
    • 2行目の入力は文字列のため、input()で受けとる (文字列のまま扱う)
  2. 縦棒とアスタリスクが、文字列Sの何番目に現れるかを格納し、縦棒1と縦棒2の番目に対してアスタリスクの番目がその間に入っているかを確認する
  3. 縦棒とアスタリスクが何番目に現れたかを記憶するための、からの配列を用意する
    Tate = [ ] 縦棒用の空配列、Kome = [ ] アスタリスク用
  4. for文を用いて一つづつの文字を確認する
    • カウンタ変数を i とし、文字列 S[i] を一つづつ取り出す
      • 文字列 S[i] が、縦棒の場合は、Tate配列に番目( i )を追加する
        * Tate配列には、左側縦棒の番目と右側縦棒の番目が保持される
      • 文字列 S[i] が、アスタリスクの場合は、Kome配列に番目( i )を追加する
  5. if文を用いて、問題の条件に当てはまるかどうかを確認する
    • 左側の縦棒の番目 < アスタリスクの番目 < 右側の縦棒の番目 が成り立つかを確認する
      Tate[0] < Kome[0] < Tate[1] と同じ意味になる
      • 条件に当てはまれば、print文で “in” を出力する
      • 条件に当てはまらなければ、print文で “out” を出力する

B問題:Trick Taking

B – Trick Taking

問題(要約)

N人のプレイヤーから、色と値を持ったカードを出す。下記の条件にて勝者が決まるため、勝者のプレイヤー番号を出力する

  • 色がTであるカードが1枚以上場に出されていた場合は、色がTである値が一番大きいカードを出したプレイヤーが勝者となる
  • 色がTであるカードが一枚も場に出されなかった場合は、プレイヤー1が出したカードと同じ色のカードのうち、値が一番大きいカードを出したプレイヤーが勝者となる

解答

# 番号1
n,t = map(int,input().split())
C=list(map(int,input().split()))
R=list(map(int,input().split()))

# 番号2
# 番号3
tmax,pmax=0,0
tplayer,pplayer=-1,-1

# 番号4
for i in range(n):
    if C[i]==t and tmax<R[i]:
        tmax = R[i]
        tplayer = i
    elif C[0]==C[i] and pmax<R[i]:
        pmax = R[i]
        pplayer = I

# 番号5
if tmax != 0:
    print(tplayer+1)
else:
    print(pplayer+1)

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

  1. それぞれの入力を受けとる
    • 1行目は、NとTが整数型で空白区切りになっているため
      • input()で受け取り
      • split()で空白毎に区切りリスト化
      • map関数を用いて、各要素に整数型(int)を適用(キャスト)する
      • 要素1番目を n 、要素2番目を t に代入する
    • 2行目の入力Cは、整数型の空白区切りの並びになっているため、上記同様に取り込みmap関数までは同様に適用する
      • list()を適用することにより、各要素の塊の配列として扱う
    • 3行目の入力Rは、配列Cと同様に処理を行う
  2. 場にTがある場合と場にTがない場合の両方の場合において、それぞれの色に対する最大値とその時のプレイヤー番号を保持する
  3. 番号2で示したそれぞれの色に対する最大値、プレイヤー番号を保持するための変数を準備する
    • tmax:色がTの時の最大値
    • pmax:色がプレイヤー1と同じ時の最大値
    • tplayer:色がTの時のプレイヤー番号
    • pplayer:色がプレイヤー1と同じときのプレイヤー番号
  4. プレイヤーの手札をプレイヤー1から順番に確認するため、for文をn回回す
    • if文を用いて各条件が当てはまるかを確認する
      • プレイヤーの出した色 C[i] が t と同じかどうか
      • R[i] が tmax (色がTの時の最大値) より大きいかどうか
        • 上記の条件が当てはまる場合は、tmaxとtplayerの数を更新する
          • tmax を R[i] に更新する
          • tplayerを i に更新する
    • elif を用いて下記の条件が当てはまるかを確認する
      • プレイヤーの出した色 C[i] が C[0] (プレイヤー1の色) と同じかどうか
      • R[i] が pmax (色がプレイヤー1と同じ時の最大値) より大きいかどうか
        • 上記の条件が当てはまる場合は、pmaxとpplayerの数を更新する
          • pmax を R[i] に更新する
          • pplayerを i に更新する
  5. if文を用いて場に T の有無を確認し、T の有無に応じた回答をする。つまり、tmax が0でない(場に T があった)事を判断する
    • tmax が0でない場合は、tplayer + 1 を出力する
      * プレイヤー1を i = 0 にしているため、+1 を行い順番合わせを行う
    • tmax が0の時は、pplayer を出力する
      * プレイヤー1を i = 0 にしているため、+1 を行い順番合わせを行う

C問題:Dango

C – Dango

問題(要約)

2種類の文字 – o からなる文字列Nにおいて以下の条件が当てはまる最大の部分列の長さLを求める

  • 先頭の文字と末尾の文字のうちちょうど一方が – であり、そのほかの 文字はすべて o である。

 上記の条件に当てはまらない場合は、 -1 を出力する

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

# 番号2
# 番号3
barBool = False
l,lmax=0,0

# 番号4
for i in range(n):
    if S[i]=="o":
        l+=1
    else:
        lmax = max(lmax,l)
        l=0
        barBool = True

# 番号5
lmax=max(lmax,l)

# 番号6
if barBool and lmax != 0:
    print(lmax)
else:
    print(-1)

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

  1. 入力を受けとる
    • Nは整数で与えらているため、input()で受け取り、intで整数型にキャストする
    • Sは文字列のため、input()で文字列のまま受け取る
  2. 与えられた条件が当てはまるかを確認しながら、最大の部分列の長さLを求める
  3. 条件を確認するための変数を準備する
    • 文字 – の有無を確認するためのboolean型のbarBoolを初期値Falseで設定する
    • 部分列の長さを一時的に記憶するための変数を l とする (初期値は0)
    • 最大部分列の長さを lmax とする (初期値は0)
  4. for文を用いて文字列Sを一文字ずつ確認していく
    • S[i] が o の時
      • l に1をプラスする
    • S[i] が – の時
      • 一時的に長さを記憶している l と現行の lmax を比較し、大きい方を lmax とする
      • 一時的な長さ変数 l をリセットする ( 0 にする)
      • 文字 – が存在した事を記憶するためbarBool = True とする
  5. 最後の文字列が o の時に、lmax が上記では更新されないため、再度 lmax の更新がないかを確認する
  6. 与えられた条件が満たされているかを確認し、それに応じた回答を出力する
    • barBool が True で、かつ、lmax が 0 でない場合、つまり部分文字列Lが存在するため、最大の長さが格納してある lmax を出力する
    • 上記の条件に当てはまらない場合は、条件を満たしていないため、-1 を出力する

感想

今回のA〜C問題はfor文と条件を設定することにより解ける問題で、比較的簡単だったと思います。

自分は、30分以内でC問題まで解くことができ、以前よりスピードが付いたと思います。

D問題は解けませんでしたが、C問題までのスピードで順位も3000番台前半で、良い成績!

っと喜んでいたら、悪意ある攻撃で今回は、Unratedに急遽変更になってしまいました。。。

気を取り直して、次回も頑張りたいと思います。

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

P.S. 拙い文章にも関わらず最後までお読み頂きありがとうございますm(_ _)m

コメント

タイトルとURLをコピーしました