競技プログラミング

【競プロ】最初に解くべき過去問10問をPythonで分かりやすく解説します!【AtCoder】

プログラミング

こんにちは!サトシ(@satoshi365_blog)です!

 

この記事では、「競技プログラミング(AtCoder)に登録して、最初に解くべき10問」をPythonを使って解いていきます。

めちゃくちゃ分かりやすく解説もするので、初心者の方も安心してください!

 

競技プログラミングって何?という方はこちら↓

 

AtCoderとかいうサービスに登録したけど、初心者だし1問も解けないんじゃないか...

と不安になりませんか?その気持ち、めちゃくちゃ分かります

なぜなら、今の僕がそうだからです。笑

 

そんな僕にピッタリの問題集を見つけました。

それが、「AtCoder Beginners Selection」です。

AtCoder Beginners Selection とは?

drkenさんがQiitaというコミュニティで紹介した問題集です。

記事はこちら→ AtCoder に登録したら次にやること〜これだけ解けば十分戦える!過去問精選10問〜

 

この記事では、この問題集をPythonを使って解いていきます。

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

AtCoder Beginners Selection を解説(11問)

AtCoder Beginners Selection は全部で11問あります。

AtCoder Beginners Selection
  1. Welcome to AtCoder
  2. Product
  3. Placing Marbles
  4. Shift only
  5. Coins
  6. Some Sums
  7. Card Game for Two
  8. Kagami Mochi
  9. Otoshidama
  10. 白昼夢 / Daydream
  11. Traveling

では、解いていきます。

 

Welcome to AtCoder

この問題はこちらで解けます。

問題文

 

問題文
高橋君はデータの加工が行いたいです。
整数 a, b, c と、文字列 s が与えられます。a + b + c の計算結果と、文字列 s を並べて表示しなさい。

制約
・1 ≤ a, b, c ≤ 1000
・1 ≤ |s| ≤ 100

入力
入力は以下の形式で与えられる。

a
b c
s

出力
a + b + c と s を空白区切りで1行目に出力せよ。
また、出力の末尾には改行を入れること。

PracticeA-Welcome to AtCoderより引用

 

解答例

# -*- coding: utf-8 -*-
# 整数の入力 a = int(input())
# スペース区切りの整数の入力
b, c = map(int, input().split())
# 文字列の入力
s = input()
# 出力
print("{} {}".format(a+b+c, s))

 

詳しい解説はこちらのページでしているので、見てみてください!

 

Product

この問題はこちらで解けます。

問題文

 

問題文
シカのAtCoDeerくんは二つの正整数 a, b を見つけました。a と b の積が偶数か奇数か判定してください。

制約
・1 ≤ a, b ≤ 10000
・a, b は整数

入力
入力は以下の形式で与えられる。

a b

出力
積が奇数なら ‘Odd’ と、偶数なら ‘Even’ と出力せよ。

ABC086A – Productより引用

 

解答例

a, b = map(int, input().split())
if (a * b) % 2 == 0:
  print('Even')
else:
  print('Odd')

 

 

Placing Marbles

この問題はこちらで解けます。

問題文

 

問題文
すむけ君は 1, 2, 3 の番号がついた3つのマスからなるマス目を持っています。各マスには ‘0’ か ‘1’ が書かれており、マス i には siが書かれています。
すぬけ君は ‘1’ が書かれたマスにビー玉を置きます。ビー玉が置かれるマスがいくつあるか求めてください。

制約
・s1, s2, s3 は ‘1’ あるいは’0′

入力
入力は以下の形式で標準入力から与えられる。

s1s2s3

出力
答えを出力せよ。

ABC081A – Placing Marblesより引用

 

解答例

print(input().count('1'))

 

 

Shift only

この問題はこちらで解けます。

問題文

 

問題文
黒板に N個の正の整数 A1, …, AN が書かれています。
すぬけ君は、黒板に書かれている整数がすべて偶数であるとき、次の操作を行うことができます。

・黒板に書かれている整数すべてを、2 で割ったものに置き換える。

すぬけ君は最大で何回操作を行うことができるか求めてください。

制約
・1 ≤ N ≤ 200
・1 ≤ Ai ≤ 109

入力
入力は以下の形式で標準入力から与えられる。

N
AA2 … AN

出力
すぬけ君は最大で何回操作を行うことができるかを出力せよ。

ABC081B – Shift onlyより引用

 

解答例

n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
  if [i for i in a if i % 2 == 1]:
    break
  a = [i/2 for i in a]
  ans += 1
print(ans)

 

 

Coins

この問題はこちらで解けます。

問題文

 

問題文
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。

同じ種類の硬貨どうしは区別できません。2 通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

制約
・0 ≤ A, B, C ≤ 50
・A + B + C ≥ 1
・50 ≤ X ≤ 20000
・A, B, C は整数である
・X は 50 の倍数である

入力
入力は以下の形式で標準入力から与えられる。

A
B
C
X

出力
硬貨を選ぶ方法の個数を出力せよ。

ABC087B – Coinsより引用

 

解答例

a, b, c, x = [int(input()) for _ in range(4)]
ans = 0
for i in range(a + 1):
  for j in range(b + 1):
    for k in range(c + 1):
      if i * 500 + j * 100 + k * 50 == x:
        ans += 1
print(ans)

 

 

Some Sums

この問題はこちらで解けます。

問題文

 

問題文
1 以上 N以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を求めてください。

制約
・1 ≤ N ≤ 104
・1 ≤ A ≤ B ≤ 36
・入力はすべて整数である

入力
入力は以下の形式で標準入力から与えられる。

N A B

出力
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。

ABC083B – Some Sumsより引用

 

解答例

n, a, b = map(int, input().split())
ans = 0
for i in range(n + 1):
  if a <= sum([int(x) for x in str(i)]) <= b:
    ans += i
print(ans)

 

 

Card Game for Two

この問題はこちらで解けます。

問題文

 

問題文
N 枚のカードがあります。i 枚目のカードには、aiという数が書かれています。
Alice と Bob は、これらのカードを使ってゲームを行います。ゲームでは、Alice と Bob が交互に 1 枚ずつカードを取っていきます。Alice が先にカードを取ります。
2 人がすべてのカードを取ったときゲームは終了し、取ったカードの数の合計がその人の得点になります。2人とも自分の得点を最大化するように最適な戦略を取った時、Alice は Bob より何点多く取るか求めてください。

制約
・N は 1 以上 100 以下の整数
・ai ( 1 ≤ i ≤ N ) は 1 以上 100 以下の整数

入力
入力は以下の形式で標準入力から与えられる。

N
a1 a2 a3 … aN

出力
両者が最適な戦略を取った時、Alice は Bob より何点多く取るかを出力してください。

ABC088B – Card Game for Twoより引用

 

解答例

n = input()
a = list(map(int, input().split()))
a.sort(reverse=True)
print(sum(a[::2]) - sum(a[1::2]))

 

 

Kagami Mochi

この問題はこちらで解けます。

問題文

 

問題文
X 段重ねの鏡餅  ( X ≥ 1 ) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい(一番下の餅を除く)もののことです。例えば、直径 10, 8, 6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は di センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

制約
・1 ≤ N ≤ 10
・1 ≤ di ≤ 100
・入力値はすべて整数である。

入力
入力は以下の形式で標準入力から与えられる。

N
d1
.
.
dN

出力
作ることのできる鏡餅の最大の段数を出力せよ。

ABC085B – Kagami Mochiより引用

 

解答例

d = [int(input()) for _ in range(int(input()))]
print(len(set(d)))

 

 

Otoshidama

この問題はこちらで解けます。

問題文

 

問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありえるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
・1 ≤ N ≤ 2000
・1000 ≤ Y ≤ 2 × 107
・N は整数である。
・Y は 1000 の倍数である。

入力
入力は以下の形式で標準入力から与えられる。

N Y

出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、’-1 -1 -1′ と出力せよ。

N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

ABC085C – Otoshidamaより引用

 

解答例

n, y = map(int, input().split())
for m10 in range(n + 1):
  for m5 in range(n + 1 - m10):
    m1 = n - m10 - m5
    if m10 * 10000 + m5 * 5000 + m1 * 1000 == y:
      print(m10, m5, m1)
      exit(0)
print('-1 -1 -1')

 

 

白昼夢 / Daydream

この問題はこちらで解けます。

問題文

 

問題文
英小文字からなる文字列 S が与えられます。T が空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S = T とすることができるか判定してください。

・T の末尾に ‘dream’ ‘dreamer’ ‘erase’ ‘eraser’ のいずれかを追加する。

制約
・1 ≤ |S| ≤ 105
・S は英小文字からなる。

入力
入力は以下の形式で標準入力から与えられる。

S

出力
S = T とすることができる場合 ‘YES’ を、そうでない場合 ‘NO’ を出力せよ。

ABC049C – 白昼夢 / Daydreamより引用

 

解答例

s = input()
s = s.replace('eraser', '')
s = s.replace('erase', '')
s = s.replace('dreamer', '')
s = s.replace('dream', '')
if s:
  print('NO')
else:
  print('YES')

 

 

Traveling

この問題はこちらで解けます。

問題文

 

問題文
シカの AtCoDeer くんは二次元平面上で旅行をしようとしています。AtCoDeer くんの旅行プランでは、時刻 0 に点 ( 0 , 0 ) を出発し、1 以上 N 以下の各 i に対し、時刻 ti に点 ( xi , yi ) を訪れる予定です。

AtCoDeer くんが時刻 t に点 ( x , y )  にいる時、時刻 t + 1 には点 ( x + 1 , y ) , ( x – 1 , y ) , ( x , y + 1 ) , ( x , y – 1 ) のうちいずれかに存在することができます。その場にとどまることは出来ないことに注意してください。AtCoDeer くんの旅行プランが実行可能かどうか判定してください。

制約
・1 ≤ N ≤ 105
・1 ≤ xi ≤ 105
・1 ≤ yi ≤ 105
・1 ≤ ti ≤ 105
・ti ≤ ti+1 ( 1 ≤ i ≤ N – 1 )
・入力は全て整数

入力
入力は以下の形式で標準入力から与えられる。

N
t1 x1 y1
t2 x2 y2
.
.
tN xN yN

出力
旅行プランが実行可能なら ‘Yes’ を、不可能なら ‘No’ を出力してください。

ABC086C – Travelingより引用

 

解答例


for _ in range(int(input())):
  t, x, y = map(int, input().split())
  if (x + y + t) % 2 or (x + y) > t:
    print('No')
    exit(0)
print('Yes')

 

 

まとめ

この10問を解けるようになったころには「Python の基礎は抑えられた」と言っても過言ではないでしょう。

 

分からないところや改善できるところがあればTwitterなどで教えてあげてください!

 

少しでも参考になれば嬉しいです!

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です