PythonでAtCoder Beginners Selectionを解いてみた

AtCoderのAtCoder Beginners Selectionをpythonで解いてみました。

ABC086A – Product

自分の回答

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

if a * b % 2 == 0:
  print("Even")
else:
  print("Odd")

2で割った時のあまりが0の時は偶数になるので”Even”、そうでない時は”Odd”を出力すればいいですね。

if文
pythonでのif文は以下のようになります。pythonはインデントされたものをひとまとめと考えるので、インデントの管理はしっかりしましょう。
他の言語に比べて、カッコはいらないし、endもいらないのでとても簡単に書けますね。

if 条件式:
  処理内容
elif 条件式:
  処理内容
else:
  処理内容

ABC081A – Placing Marbles

自分の回答

s = input()
print(s.count("1"))

二行だと、、、。普段はC++で解いているので、比べるとpythonの簡潔なコードには感動します。ただし、実行時間はとても長いです。C++だと、1msですが、pythonだと17msです。
下にC++で解いた時のコードを置いときます。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string a;
  cin >> a;
  cout << count(a.begin(), a.end(), '1');
}

ABC081B – Shift only

自分の回答

n = int(input())
a = list(map(int, input().split()))
count = 0
counts = list()

for i in a:
  while i % 2 == 0:
    i = i / 2
    count += 1 
  counts.append(count)
  count = 0
  
print(min(counts))

問題文だと、一度に全ての数を2で割っていますが、そうではなくて、一つ一つ値を取り出して割っていき、何回2で割ったかをカウントした方がわかりやすいです。
まず、入力された値を変数nとリストaに格納します。変数countは2で割った回数をカウントするもので、そのカウントした値をcountsというリストに格納していきます。格納した後に、count=0として、リセットすることを忘れずにしましょう。出ないと、ずっとcountに1を足されてしまいます。
最後に、countsの中の最小値を出力すれば、答えとなります。

ABC087B – Coins

自分の回答

a = int(input())
b = int(input())
c = int(input())
x = int(input())
count = 0

for i in range(a + 1):
  for j in range(b + 1):
    for k in range(c + 1):
      if 500 * i + 100 * j + 50 * k == x:
        count += 1

print(count)

for文で繰り返せばいいですね。

ABC083B – Some Sums

自分の回答

n, a, b = map(int, input().split())
ans = 0

for i in range(n + 1):
  # 文字列に変換
  s = str(i)
  # 一文字ずつ取り出して、リストに格納
  sums = list(map(int, s))
  # sum関数でリスト内の合計値を求めて、条件を満たせば、ansに足し合わせる
  if a <= sum(sums) <= b:
    ans += i

print(ans)

pythonだと各桁の合計は簡単に求めることができます。
まず、最初に文字列に変換します。
次に一文字ずつ取り出して、リストに格納します。この時、整数型に変換し直しています。
最後に、リスト内の合計値を求めて、条件(a <= sumsの合計値 <= b)を満たせば、変数ansに足し合わせていきます。
以下の記事を参考にしました。

https://www.suzu6.net/posts/30/

www.suzu6.net

ABC085B – Kagami Mochi

自分の回答

n = int(input())
mochi = list()

for i in range(n):
  d = int(input())
  mochi.append(d)

# 重複する数字を削除
mochi_unique = list(set(mochi))

# リストの大きさを出力
print(len(mochi_unique))

リストの重複する要素を削除する問題ですね。
入力された餅の大きさをリストmochiに格納していきます。
次に、set関数を使って、mochiリストの中の重複する要素を削除します。
最後にlen関数を使って、重複を削除した後のリストの大きさを出力すれば、答えとなります。

set関数
リストや文字列の重複を削除します

len関数
リストの大きさを返します。

ABC085C – Otoshidama

自分の回答

n, y = map(int, input().split())

for i in range(n + 1):
  for j in range(n + 1 - i):
    k = n - i - j
    if 10000 * i + 5000 * j + 1000 * k == y:
      print(i, j, k)
      exit()

print("-1 -1 -1")

for文の中のiが10000円札の枚数、jが5000円札の枚数、kが1000円札の枚数になります。
やりがちなのが、forを三重にして求めようとすることです。for文を三重にしてしまうと、nやyの値が大きくなった時に、計算に時間がかかすぎてタイムアウトになってしまいます。そこで、工夫するのは、kの値の求め方です。
三種類のお札のうち、二種類のお札の枚数が決まれば、残り一つのお札の枚数は自動的に決まります。何故なら、全体のお札の枚数nが決まっているからです。全体のお札の枚数(n)から、二種類のお札の枚数(i,j)を引けば、残り一つのお札の枚数(k)が求まります。コードだと、k = n – i – jとして求めています。すると、for文が一つ減り、実行時間が短縮されるため、正解となります。
このfor文を減らすテクニックは、よく出てくるので覚えておきましょう。

ABC049C – 白昼夢

自分の回答

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

問題の内容が難しいですが、考え方としては、とりあえず、与えられた文字列sにdream dreamer erase eraserが含まれていたら、取り除いていき、文字列sからきれいに全て取り除けたら”YES”を出力すればいいです。

問題なのは、単語の取り除く順番です。”dreamer”という単語の中に”er”という部分が入っているので、先に”dreamer”を排除してしまうと、本来”erase”として抜き出せるのに、”ase”となって抜き出せなくなってしまいます。なので、”eraser”、”erase”から抜き出します。

例
dreameraser
=> dreamerを取り除くとaserとなり、答えはNOとなるが、これは不正解

dreameraser
=> eraserを取り除くとdreamerが残り、dreamerを取り除いて、答えはYESとなる

ABC086C – Traveling

自分の回答

N = int(input())
P = [list(map(int,input().split())) for i in range(N)]
# 出発点の定義
t1,x1,y1 = 0, 0, 0

for i in P:
  t2, x2, y2 = i
  # 時刻t
  t = t2 - t1
  # 次の点への距離d
  d = abs(x2 - x1) + abs(y2 - y1)

  if d > t or (t - d)%2 != 0:
    print("No")
    exit()
  else:
    # 次点の計算の為に代入
    t1,x1,y1 = t2, x2, y2

print("Yes")

Noとなる条件は二つあります。”目的地までの移動回数より、移動可能回数が少ない時”と”目的地に到達した時点で残り移動可能回数が奇数の時”です。この二つの場合を除けばいいのです。わかりづらいので、詳しく説明したいと思います。

1.目的地までの移動回数より、移動可能回数が少ない時
これは単純で、例えば、(0,0)から(100,0)に行くには100回移動しなくてはいけません。それに対して、移動可能回数t、この例であれば時刻tの数が100より小さい時はたどり着けないので、答えは”No”となります。
コードで言うと、目的地への移動回数がdとなり、移動可能回数はtとなります。d > tの部分で比較して、必要な移動回数dが移動可能回数tより大きい時は”No”となります。

2.目的地に到達した時点で残り移動可能回数が奇数の時
この問題は、最短距離で目的地まで行き、残り移動可能回数が偶数であればYesとなります。途中の移動の仕方などは考慮しなくても大丈夫です。
目的地に着いた時点で、残り移動可能回数が偶数であれば一歩進んで一歩戻るを繰り返せばいいのです。しかし、奇数だった場合、一歩余ってしまいます。なので、残り移動可能回数が奇数の時は失敗となるので、”No”を出力します。コードで言うと、(t – d)%2 != 0になります。

どちらの条件にも引っかからなかった場合、計算が続くので、次の計算のために、t1,x1,y1にt2, x2, y2を代入し直しています。そして、for文の最初でt2, x2, y2に次の点の値が新たに代入されます。