WHAT'S UP?

New post every sometimes. Here's OKKAH NET.

AtCoder Beginners SelectionをPythonで解いてみた

AtCoderはオンラインで参加できるプログラミングコンテスト(競技プログラミング)のサイトです。
リアルタイムのコンテストで競い合ったり、約3000問のコンテストの過去問にいつでも挑戦することができます。

AtCoder Beginners Selectionとは

atcoder.jp

このコンテストは「AtCoderに登録したけど何をしていいか分からない...!」という人に向けて作られた初心者向け問題集です。
AtCoder に登録したら次にやること ~ これだけ解けば十分闘える!過去問精選 10 問 ~ - Qiitaの記事で選出された問題が使用されています。

今回はこのコンテストをPythonで解いてみました。

第0問 PracticeA - Welcome to AtCoder

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

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

【入力例】
1
2 3
test

【出力例】
6 test




【ポイント】
・1行/1列, 1行/C列の入力処理
・四則演算

【解法】

a = int(input())
b, c = map(int, input().split())
s = input()
print("{} {}".format(a+b+c, s))



第1問 ABC086A - Product

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

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

【入力例1】
3 4

【出力例1】
Even

【入力例2】
1 21

【出力例2】
Odd




【ポイント】
・倍数判定

【解法】

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



第2問 ABC081A - Placing Marbles

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

【制約】
・s1, s2, s3は'1'あるいは'0'

【入力例】
101

【出力例】
2




【ポイント】
・for文を使わないレベルの全探索
・string型

【解法】

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



第3問 ABC081B - Shift only

【問題文】
黒板に N 個の正の整数A1, … , ANが書かれています.
すぬけ君は,黒板に書かれている整数がすべて偶数であるとき,次の操作を行うことができます.
 ・黒板に書かれている整数すべてを,2で割ったものに置き換える.
すぬけ君は最大で何回操作を行うことができるかを求めてください.

【制約】
・1 ≤ N ≤ 200
・1 ≤ Ai ≤ 10^9

【入力例】
3
8 12 40

【出力例】
2




【ポイント】
・for文を用いた全探索
・シミュレーション

【解法1】

#「全て偶数である限り、全て2で割る」をシミュレート
n = int(input())
a = list(map(int, input().split()))
ans = 0
while all(i%2 == 0 for i in a):
  a = [i/2 for i in a]
  ans += 1
print(ans)

【解法2】

#最大で何回2で割れるかを求め、その最小値をとる
n = int(input())
a = list(map(int, input().split()))
ans = float('inf')
for i in a:
  ans = min(ans, len(bin(i)) - bin(i).rfind('1') - 1)
print(ans)



第4問 ABC087B - Coins

【問題文】
あなたは、500円玉をA枚、100円玉をB枚、50円玉をC枚持っています。これらの硬貨の中から何枚かを選び、合計金額をちょうどX円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。

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

【入力例】
2
2
2
100

【出力例】
2




【ポイント】
・R行/1列の入力処理
・二重三重for 文を用いた全探索

【解法】

a, b, c, x = [int(input()) for i 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)



第5問 ABC083B - Some Sums

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

【制約】
・1 ≤ N ≤ 10^4
・1 ≤ A ≤ B ≤ 36
・入力はすべて整数である

【入力例】
20 2 5

【出力例】
84

20以下の整数のうち、各桁の和が2以上5以下なのは、2, 3, 4, 5, 11, 12, 13, 14, 20です。これらの合計である84を出力します。




【ポイント】
・整数の10進法表記の扱い方

【解法】

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



第6問 ABC088B - 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以下の整数

【入力例】
2
3 1

【出力例】
2




【ポイント】
・ソート
・Greedyアルゴリズム

【解法】

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



第7問 ABC085B - Kagami Mochi

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

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

【入力例】
4
10
8
8
6

【出力例】
3

直径10、8、6センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、これが最大です。




【ポイント】
・集合 (set)

【解法】

n = int(input())
print(len(set([int(input()) for i in range(n)])))



第8問 ABC085C - Otoshidama

【問題文】
日本でよく使われる紙幣は、10000円札、5000円札、1000円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札がN枚入っていて、合計でY円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

【制約】
・1 ≤ N ≤ 2000
・1000 ≤ Y ≤ 2 × 10^7
・Nは整数である。
・Yは1000の倍数である。

【入力例】
9 45000

【出力例】
4 0 5

お年玉袋に10000円札4枚と1000円札5枚が入っていれば、合計枚数が9枚、合計金額が45000円になります。5000円札9枚という可能性も考えられるため、'0 9 0'も正しい出力です。




【ポイント】
・計算量を考慮した全探索

【解法】

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



第9問 ABC049C - 白昼夢 / Daydream

【問題文】
英小文字からなる文字列Sが与えられます。Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことでS=Tとすることができるか判定してください。
 ・Tの末尾に 'dream' 'dreamer' 'erase' 'eraser' のいずれかを追加する。

【制約】
・1 ≦ |S| ≦ 10^5
・Sは英小文字からなる。

【入力例1】
erasedream

【出力例1】
YES

【入力例2】
dreamerer

【出力例2】
NO




【ポイント】
・Greedyアルゴリズム
・prefix

【解法】

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



第10問 ABC086C - 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 ≤ 10^5
・0 ≤ xi ≤ 10^5
・0 ≤ yi ≤ 10^5
・1 ≤ ti ≤ 10^5
・ti < ti+1 (1 ≤ i ≤ N−1)
・入力は全て整数

【入力例1】
2
3 1 2
6 1 1

【出力例1】
Yes

例えば、(0, 0), (0, 1), (1, 1), (1, 2), (1, 1), (1, 0), (1, 1)と移動すればよいです。

【入力例2】
1
2 100 100

【出力例2】
No




【ポイント】
パリティ

【解法】

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