競技プログラミング備忘録

標準入力の受け取り方法について

atcoderには上の画像のような標準入力が存在する。これの受け取り方がかなり厄介で大学1年生のとき競技プログラミングを始めようと思ったがこの標準入力の受け取り方で躓きあきらめてしまったのでここに私が知る限りのpythonでの標準入力の受け取り方を記述していき私と同じような事になる人を減る事を望んでいます！
入力のコードの解説はpythonの備忘録で詳しく解説していこうと思います！

単純な数値の入力の受け取り方

もっとも基本的な数値の受け取り方です。
下に受け取り方のコードを示します！

N = int(input())

二つの文字列が一行に並んでいる場合

上のように入力のための文字列が一行に2つある場合は,下のようなコードで
入力を受け取ることができる。

N, K = map(int, input().split())

リストでの入力の受け取り

全探索

A11 - Binary Search 1

この上記の例題を通して全探索について学んだ！
全探索とはその名前の通りにしらみつぶし一つ一つ調べていく方法で計算数は膨大になるが様々な問題に利用できる汎用の高いアルゴリズムである。

この問題のコードの実装例

＃入力の受け取り
N, X = map(int, input().split())
A = list(map(int, input().split()))
#全探索を行う部分
for i in range(N):
  if A[i] == X:
    print(i+1)
    break

コードの解説
解説といってもシンプルなコードなので特に解説する事はないのだが一応
解説をしておくとfor文をデータ数分回してあげてXが配列のなかの何番目にあるのかを出力している。さらにbreak文でXが見つかったら終わるようにしてある。”注意”print(i+1)で＋１をする理由は配列が０から数えはじめるからである

2分探索法

2分探索法とは,昇順や降順に整理されて並べられているデータに対して行えるアルゴリズムです。具体的な処理としては調べたい数字がそのデータの中間値に対してHighかRowかを判定し続けることで判定します。

実装例

N, X = map(int, input().split())
A = list(map(int, input().split()))
# LとRはデータの左と右の意味
L = 0
R = N-1
while L <= R :
#Mは中心を意味する(middleのM)
  M = (L+R)//2
  if A[M] < X:
    L =  M+1
  if A[M] > X:
    R =  M+1
  if A[M] == X:
    print(M+1)
    break