競技プログラミングをやってみた話その1

Why？

競技プログラミング、所謂競プロと呼ばれるもの自体はPaizaやpythonのチュートリアルで触れてきましたが私が文系で数学が非常に苦手であるという理由からCランクでも結構苦戦するレベルで正直、勉強の効率が悪いと感じていて、その後フレームワークを使ってモノを作るということをしている中で

「あれ？ 別に必要ないのでは？」

と思ってしまい、以後苦手意識を持ってしまい手を付けてきませんでした。

しかし、先日企業の選考の過程でスキルチェックを受けることになり所謂AtCoderのようなところで受けてきたのですが、受験前に少し改めてPaizaをやり、その上で受験してみて

アルゴリズムはわかるのにそれをコードに起こせないという苦しさ・悔しさ
そもそもフレームワークを使ってモノを作るということと、競技プログラミングで求められる力(=これをやることで身につけたいこと)とは別のベクトルである

という二つのことに気づき、そもそもそれ以前にこういうスキルチェックをやるのが今後当たり前になるだろうにPaizaのCランク程度も解けないのでは話にならないのでは？ ということを感じ、重い腰を上げてこれからは少しこちらの方にも手を伸ばしてみようと考え、サクッとググってこちらの記事を見つけて、久方ぶりにAtCoderを始めてみたのでその過程を記録したいと思います。
とりあえず、参考記事中の類題を含めて第3問目まで終了したので、アウトプットと復習を兼ねつつ随時更新してそこまでのアウトプットを終えたら以後はまた別の記事に分けていきます。

ちなみにフレームワークを使ってモノを作るのと競技プログラミングでつける力は別ベクトルに感じたという話は、両者に関連性がないという話ではなく、競技プログラミングは主にデータを如何に効率的に操作・編集するかというところに重きを置いていて、そのためには各言語の組み込み関数の知識やそもそもの数学的考え方・知識が必要だという話です。
むしろ、フレームワークを使ってモノを作るだけならフレームワークが優秀なのでおおよそのことはできますが、じゃあデータを本格的に扱おうとか考えると競技プログラミングでやるようなスキルが必要になるだろうと思っています。
そういう意味でもさすがにCランク程度の力がないと恥ずかしいかな……と今回のスキルチェック受験を終えて思いました。

目標

PaizaのCランク程度、スキルチェック初見で50点はしっかり取れるようになりたい。
最適を詰めるのではなく、まずはforやwhileをしっかり扱えるようにというところを意識したい。

標準入力

問題で与えられた数値などを受け取る方法。
作法のようなものだと思って脳死で覚える。

# こういうデータを受け取りたい場合
1
2 3
test

# こう書く
N = int(input()) # N = 1
b,c = map(int,input().split()) # b = 2, c = 3
S = input() # S = test

やった問題

PracticeA - Welcome to AtCoder

書いたコード

N = int(input())
b,c = map(int,input().split())
S = input()
sum = N + b + c

# .formatを使うと引数に設定したものを{}を置いたところと置き換えられる
print("{} {}".format(sum, S))

ABC086A - Product

書いたコード

a,b = map(int,input().split())

# 偶数判定は0で割った余りが0であるかどうか。よく出るけどよく忘れる
def Check(A,B):
  result = A * B
  if result % 2 == 0:
    print('Even')
  elif result % 2 != 0:
    print('Odd')

Check(a,b)

ABC081A - Placing Marbles

書いたコード

# 文字を1文字ずつ分解してリストにする
l = list(input())
# リスト内の要素をint型に変換する
l= [int(s) for s in l]
count = 0

for i in l:
  if i == 1:
    count += 1
print(count)

ABC081B - Shift only

書いたコード

N = int(input())
num_list = list(map(int,input().split()))
count = 0
bool = True
# whileとforを組み合わせつつ、どのタイミングでどのループを終了させるのかというのが肝
while bool:
  for i in range(N):
    if num_list[i] % 2 != 0:
      print(count)
    #   今回はwhileでnum_list内の要素を1/2し続けたいのでwhile自体を止めてしまう
      bool = False
    else:
      num_list[i] = num_list[i] // 2
  count += 1

ABC087B - Coins

書いたコード

# 硬貨の中から何枚かを選び、合計金額をちょうど X円にする方法は何通りあるか

A = int(input())
B = int(input())
C = int(input())
X = int(input())
# 初期値
count = 0
countA = 0
countB = 0
countC = 0

# R3
while countA <= A:
    countB = 0
    # R2
    while countB <= B:
        countC = 0
        # R1
        while countC <= C:
            if(500*countA + 100*countB + 50*countC == X):
                count += 1
            countC += 1
        countB += 1
    countA += 1
print(count)

# ネストされたループは内側から処理されていく
# つまり、まずR1の位置から処理が始まり、R1が終わるとcountB += 1を行い、R2の処理が始まる。このときcountC = 0と初期化されるのでR1の処理も再び行われる(このときcountB = 1である)
#　同様にR2が終わるとcountA += 1を行い、R3の処理が始まる。このとき、countA = 1 かつ countB = 0であり、またcountB <= BであることからcountC = 0

A - RGB Cards

書いたコード

# 半角スペース刻みの入力をintで受け取る
N = map(int,input().split())
# 受け取ったNを文字列に変換してリストにする
l = [str(i) for i in N]
# リストの文字列を結合
num = "".join(l)

if int(num) % 4 == 0:
  print('YES')
elif int(num) % 4 != 0:
  print('NO')

A - Infinite Coins

書いたコード

N = int(input())
A = int(input())

if N % 500 <= A:
  print('Yes')
else:
  print('No')

A - Duplex Printing

書いたコード

import math
N = int(input())

print(math.ceil(N / 2))

ABC 095 A - Something on It 　

書いたコード

S = input()
# 文字列はlist()で1文字ずつに分解できる
l = list(S)
count = 0

for i in l:
  if i == 'o':
    count += 1
sum = 700 + (100*count)
print(sum)

A - Already 2018

書いたコード

S = input()
l = list(S)

l[0] = '2'
l[1] = '0'
l[2] = '1'
l[3] = '8'

result = ''.join(l)
print(result)

B - i18n

書いたコード

S = input()
l = list(S)
# 先頭と末尾の間の文字数 = 文字数 - 2
num = len(l) - 2
print(l[0] + str(num) + l[-1])

B - Two Anagrams

書いたコード

s = input()
t = input()

l_s = list(s)
l_t = list(t)

# 辞書順でl_s < l_tが成り立つかどうか知りたい → l_sの辞書順最小(昇順) < l_tの辞書順最大(降順)が成り立つか判定すればいい
# sortedはもとの配列はそのままに新しい配列を作ってそれをソートする、reverse=Trueで降順
sample1 = sorted(l_s)
sample2 = sorted(l_t, reverse=True)

if sample1 < sample2:
  print('Yes')
else:
  print('No')

B - Break Number

書いたコード

N = int(input())
list = []
# 入力値は1以上なので初期値も1以上にする
sample = 1
count1 = 0

# 条件より1から入力値までの数値をリストに入れたい
for i in range(N):
  list.append(i+1)

# 作ったリストで探索処理
for l in list:
    # 新しく初期値を作る
    p_l = l
    count2 = 0
    # 割り続ける処理
    while l % 2 == 0 :
        l = l // 2
        count2 += 1
    # whileが終わったら条件分岐で冒頭の初期値を更新するかしないか選択
    if count2 > count1:
        count1 = count2
        sample = p_l
print(sample)

Maximum Difference

書いたコード

N = int(input())
l = list(map(int,input().split()))
count = 0
sample1 = 1

# 要素の数だけ繰り返す
for i in range(N):
    # さらにlをfor文にかける
    for j in l:
        # ループは内側から処理されるのでj = lが一周するまでl[i]は固定
        sample2 = abs(l[i] - j)
        if sample2 > sample1:
            sample1 = sample2
print(sample1)

# forを使わない場合
N = int(input())
l = list(map(int,input().split()))

# 絶対値の最大 = リストの要素の最大と最小との減算
l_max = max(l)
l_min = min(l)

abs = abs(l_max - l_min)

print(abs)

B - Palace

書いたコード

N = int(input())
average,temp = map(int, input().split())
elevation = list(map(int, input().split()))
newlist = []

# 平均気温算出の関数
def calcurate_temp(ele):
    result = average - (ele*0.006)
    return result
# 与えられた各標高のデータで平均気温を算出し、気温との絶対値を計算してそれをリストに入れていく
for i in range(N):
    t = calcurate_temp(elevation[i])
    sample = abs(temp - t)
    newlist.append(sample)
    pass
# .index()でリストの指定したインデックスを取得できる
# 今回は気温に近い = 絶対値が一番小さいインデックスが欲しいので以下のようになる
# またインデックスは0スタートなので+1したものを返す
ans = int(newlist.index(min(newlist))) + 1
print(ans)

# 関数を作らないでシンプルに書くパターン
N = int(input())
T,A = map(int,input().split())
l = list(map(int,input().split()))
new_list = []

for i in range(N):
    sample = l[i]
    test = T - (sample*0.006)
    abs_sample = abs(A - test)
    new_list.append(abs_sample)
print(new_list.index(min((new_list))) + 1)

B - OddString

書いたコード

S = input()
l = list(S)
new_list = []

for i in range(len(l)):
    # インデックスは0スタートなので奇数番目はインデックスが偶数になるときの文字となる
    if i % 2 == 0:
        new_list.append(l[i])
ans = "".join(new_list)
print(ans)

B - A to Z String

書いたコード

S = input()
l = list(S)
new_list = []
# 初期値はそれぞれ該当する文字が複数ある場合、最初だけ補足したいので条件を満たさないものを設定しておく
first_a = 200001
last_z = 0

for i in range(len(l)):
    if l[i] == "A":
        a_index = i
        if first_a >= a_index:
            first_a = a_index
    if l[i] == "Z":
        z_index = i
        if last_z <= z_index:
            last_z = z_index
for j in range(first_a - 1, last_z):
    new_list.append(l[j])
print(len(new_list))

B - Bitter Alchemy

書いたコード

N, X = map(int,input().split())
l = [int(input()) for _ in range(N)]
# 最低1個ずつ作るのでリストの要素を合計する
premise = sum(l)
# Xからpremiseを引いて材料の余りを出す
rest = X - premise
# あとは残った材料からできるだけ多くつくる = 材料の消費が少ない分量のモノをどれだけ作れるか計算して、前提条件を加える
print((rest // min(l)) + N)

# ソート関数を使う場合
N,X = map(int,input().split())
list = [int(input()) for _ in range(N)]
list_sum = sum(list)
sample = X - list_sum
# 最小を探したいのでリストの要素を昇順にする
list.sort()
 
print((sample // list[0]) + N)

ここまでやってみた感想

競技プログラミングは筋トレと呼ばれるのを耳にしますが、その意味を身を以て理解することができたなと思いました。
実はこの記事を書く前に初見と解き直しで2回、そしてこの記事書くにあたってもう一度解いてますが、文系の私だとここまでやってようやくちゃんと理解できたなぁと感じます。
ここまでで一番難しいなと感じたのは

B - Bitter Alchemy
B - Coins
B - Shift Only

以上3問でした。
Bitter Alchemyは単純にできるだけ多く = 最小を試行し続けるというロジックに思い至らなかったからという点、後ろ2つはforとwhileのネストやin rangeとの合わせ技の使い方を理解するという意味で難しかったなと思います。

これを書いている現在、冒頭で言及した選考は見事に落ちまたも0からのスタートとなってしまいましたが、これからもひとまずやれるだけやってみようかと思います。

参考記事

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
Pythonでリストをソートするsortとsortedの違い
Pythonで多重ループ（ネストしたforループ）からbreak
Pythonのfor文によるループ処理（range, enumerate, zipなど）
Pythonのwhile文によるループ処理（無限ループなど）
【Python】絶対値の計算方法について
【Python】競技プログラミング 基本入力まとめ
Pythonで文字列を連結・結合（+演算子、joinなど）
[Python]リストをforループ処理する
Python3の割り算は切り捨てではない
[Python] リストの最大値、最小値とそのインデックスを取得する
Pythonで小数点以下を切り捨て・切り上げ