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

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

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

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

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

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

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

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

大文字判定( isupper )　・・・　A問題

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

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

AtCoder Beginner Contest 291

A問題：camel Case

A – camel Case

問題(要約)

英小文字列の中に１文字の英大文字が含まれる文字列Sにおいて、大文字が何文字目に現れるか。

解答

S=input()

for i in range(len(S)):
    if S[i].isupper():
        exit(print(i+1))

考え方

入力を受け取り、変数Sに代入する
len(S)で変数Sの長さを求め、カウンタを i としてfor文を変数Sの長さ分繰り返す
スライスを用いてSの i 番目の文字列を取り出し(S[i])、isupper関数を用いて、大文字かどうかを判定する。
- S[i].isupper()がTrueの時、カウンタ番号 i + 1 を出力してプログラムから抜ける(exit)
  ＊大文字が1文字と決まっているため、for文の途中でもプログラムから抜けている
- S[i].isupper()がFalseの時、何もせず、次のfor文に進む

B問題：Trimmed Mean

B – Trimmed Mean

問題(解答)

　5N人の審査員がそれぞれ点数をつけ、点数の高い方のN人と点数の低い方のN人の得点を除いた3N人の平均点を求める

解答

# 入力nを受け取り、整数型(int)に変換(キャスト)を行う
n=int(input())
# 空白区切りの入力を受け取り(input())、split()で空白区切りで分割する
# map関数を用いてそれぞれの要素にint(整数型)を適用することによりキャストする
# map関数のままになっているため、list化する
X=list(map(int,input().split()))

# 下記参照
sorted_X = sorted(X)
points = sorted_X[n:-n]
sumPoint = sum(points)
avePoint = sumPoint / (3*n)
print(avePoint)

考え方

sorted関数を用いて、配列Xを昇順に並び替えを行い、sorted_Xに代入する
スライス(配列の部分を切り出す)を用いて、n番目から後ろからn番目までを切り出し、points配列に代入する
＊[n : -n]は、n番目から後ろからn番目を表す。つまり上下n個を配列から除外する
sum関数を用いて用いて、points配列を合計し、sumPointに代入する
有効な審査員の数は、3N人のため、sumPoint を3Nで割ることにより平均(avePoint)を求める
print関数にてavePointを出力する

かっこいい回答　(わたしが思う所の)

n=int(input())
print(sum((sorted(list(map(int,input().split())))[n:-n]))/(3*n))

空白区切りの入力Xの受け取りから、上記の1〜5を1行で記載している
こういうスマートなプログラムを書けるようになりたい。

C問題：LRUD Instructions 2

C – LRUD Instructions 2

問題(要約)

2次元平面の原点から入力文字列Sに従って、N回移動を行い同じ座標にいたことがあるかを判定

Sの i 文字目が R である時、(x + 1, y)
Sの i 文字目が L である時、(x – 1, y)
Sの i 文字目が U である時、(x, y + 1)
Sの i 文字目が D である時、(x, y – 1)

解答

# 入力 n を受け取り、整数型(int)に変換(キャスト)
n=int(input())
# 文字列を受け取る
S=input()

# 下記参照
direct = {"R":(1,0), "L":(-1,0), "U":(0,1), "D":(0,-1)}
x,y=0,0
pos = {(x,y)}
for i in range(len(S)):
    x,y = x+direct[S[i]][0], y+direct[S[i]][1]
    if (x,y) in pos:
        exit(print("Yes"))
    else:
        pos.add((x,y))
print("No")

考え方

入力文字をx,yの移動量に変換を行うため、辞書型を用いてdirectにそれぞれの移動量を定義する
例： direct[“R”] = (1, 0) ・・・xの移動量が + 1, yの移動量が 0
x, yの初期値を定義する。原点スタートのため、x, y ともに0とする
現在位置を示す集合pos を定義し、現在位置をタプル型が定義する
xとyを一つの塊として扱いたい為、( )に入れるタプル型を用いている
リストでなく、集合として扱うことにより順番を持たない代わりに集合内の検索が早くなる
for文を用いて、文字列を一つづつ選択する。len(S)で文字列長さを取得している
文字列に従ってx, yを移動させる
- 辞書型のdirectのキーにS[i]を渡すことにより、タプル( )が呼び出せる
- x, y を別々に移動させるため、呼び出したタプルを下記に分割する
  - 呼び出したタプルの[0]がx座標移動量
  - 呼び出したタプルの[1]がy座標移動量
- 現行のx, y に上記の移動量をそれぞれ足し合わせる
移動後の位置 (x, y) が今までに通ってきた事があるかを確認するために、集合posに (x, y)が含まれているかを確認する
＊リスト型だと含まれているか判定に時間がかかるため、集合として扱うのがポイント
- 集合に現行の(x, y)が含まれている場合は、”Yes”を出力し、exitでプログラムを終わらせる
- 集合に現行の(x, y)が含まれていない場合は、pos集合に現行の(x, y) を追加する
同じ経路を通った経緯がある場合は、プログラムが途中で抜けるようにしているため、最後までプログラムが走った場合、つまり、同じ経路を通っていないため、”No”と出力させる