AtCoder Beginners Selectionをやる！

AtCoder Beginners Selectionを，Python3で取り組みます．
注：問題文は意訳しています．

PracticeA - Welcome to AtCoder

問題

入力

\begin{aligned}
&a \\
&b~c \\
&s
\end{aligned}

（$a,b,c$は整数，$s$は文字列で，$1\leq a,b,c \leq 1,000$，$1\leq |s| \leq 100$）が与えられたときに，

\begin{aligned}
&a+b+c~s
\end{aligned}

を出力せよ．

各言語でサンプルが与えられています．入力の受け取り方がわかり，次問以降で使えます．

以下はPython3のコードです．

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

この問題で，「コードテスト」，「提出」，「提出結果」の確認方法がわかりました．

提出結果＞全ての提出から，実行時間が短い回答を見られるのは，後々使えそうです．

ABC086A - Product

問題

入力

\begin{aligned}
&a~b
\end{aligned}

（$a,b$は整数で，$1\leq a,b \leq 10,000$）が与えられたときに，

\begin{aligned}
\begin{cases}
\,\text{Odd} & (a\times b\text{\,が奇数の場合}) \\
\,\text{Even} & (a\times b\text{\,が偶数の場合})
\end{cases}
\end{aligned}

を出力せよ．

以前の問題を参考にすると，次で行けそうです．

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

無事，正解でした．

「提出結果＞全ての提出」で実行時間が短いものをみると，同じような回答でした．

コード長が短いものは，．．．ちょっとテクニカルなのでまだパスしておきます．

ABC081A - Placing Marbles

問題

入力

\begin{aligned}
&s_{1}s_{2}s_{3}
\end{aligned}

（$s_{1},s_{2},s_{3}$は，それぞれ$0,1$のいずれか）が与えられたときに，

\begin{aligned}
&s_{1}+s_{2}+s_{3}
\end{aligned}

を出力せよ．

これまでと入力方法が違う（スペースで区切られていない）ことがポイントのようです．ググるとlist()で行けるっぽい．というわけで，以下で正解でした．

s = map(int, list(input()))
print(sum(s))

ここで，

s = list(input())

とすると，リストの要素が文字列となるためsumをとるときにエラーが出ました（例えば，標準入力「101」に対して，sは「['1', '0', '1']」となります）．

実行時間が短い回答で参考になったのは以下です．なるほど．．．

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

ABC081B - Shift only

問題

入力

\begin{aligned}
&N \\
&A_{1}~A_{2}\cdots A_{N}
\end{aligned}

（$N,A_{i}$は正整数で，$1\leq N\leq 200$，$1\leq A_{i}\leq 10^{9}$）が与えられる．ここで，$A_{1}, A_{2},...,A_{N}$のそれぞれに対し，「2で割り切れる限り，繰り返し2で割る操作」を考える．$A_{1}, A_{2},...,A_{N}$で実行できる操作回数のうち，最小値を出力せよ．

とりあえず，動くものができました．キレイじゃないなぁ．．．

また，あとで気づきましたが，a_listはリストになっていません．リストにするにはこれにlist()を作用させる必要があります．

n = int(input())

ans = 1e9
a_list = map(int, input().split())

for a in a_list:
  i = 0
  while a % 2 == 0:
    a = a // 2
    i += 1
  if i < ans:
    ans = i
    
print(ans)

実行時間が短い回答例は，次が参考になります．

n = 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)

2進数に変換すれば，末尾のゼロの数＝2で割れる回数となることを利用しています．本質的には，同じことをやっていますが，ループさせるより組み込み関数を使ったほうが早いということですね．組み込み関数bin()と文字列メソッドstr.rfindについては次に説明があります．

• 組み込み関数 — Python 3.9.2 ドキュメント
• 組み込み型 — Python 3.9.2 ドキュメント

また，ansの初期値はなるべく大きい値にすれば良いので無限大になっています．これなら，入力される値の範囲が変わってもそのまま使える，ということですね．

ABC087B - Coins

問題

入力

\begin{aligned}
&A \\
&B \\
&C \\
&X
\end{aligned}

（$A,B,C$は整数で，$0\leq A,B,C \leq 50$，$A+B+C \geq 1$．$X$は$50$の倍数で，$50 \leq X \leq 20,000$．）が与えられたときに，

\begin{aligned}
&X = 500a + 100b + 50c \\
&(0\leq a \leq A, 0\leq b \leq B, 0\leq c \leq C)
\end{aligned}

を満たす整数$(a,b,c)$が何通りあるか出力せよ．

単純に，全通り試す方法を考えました．

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

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

実行時間が短い回答は以下です．$A,B,C,X$が50の倍数なので，50で割った値で考えています．最小通貨が1円となり，わかりやすいですね．

処理は，大きい通貨から枚数を決めていき，途中で合計金額が$X$を超えた時点でループを抜けるようになっています．全パターンを考えない分早いということですね．

また，入力が複数ある場合，ループ処理できれいに書けることがわかりました．

A,B,C,X = [int(input()) for i in range(4)]
X //= 50
ans = 0
for i in range(A + 1):
    if 10*i > X: break
    rem = X - 10*i
    for j in range(B + 1):
        if 2*j > rem: break
        if rem - 2*j <= C:
            ans += 1
print(ans)

ABC083B - Some Sums

問題

入力

\begin{aligned}
&N~A~B
\end{aligned}

（$N,A,B$は整数で，$1\leq N \leq 10^{4}$，$1\leq A \leq B \leq 36$）が与えられたときに，『「$10$進法での各桁の和が$A$以上$B$以下である，$1$以上$N$以下の整数」の総和』を出力せよ．

これまでの知識を活かして（コピペして汗）できました．

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

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

この問題に関しては，実行時間を短くしようとすると，長いコードになるようです．．．

ABC088B - Card Game for Two

問題

入力

\begin{aligned}
&N \\
&a_{1}~a_{2}~a_{3}\cdots ~a_{N}
\end{aligned}

（$N,a_{i}$は整数で，$1\leq N,a_{i} \leq 100$）が与えられる．$i$のカードに$a_{i}$が書かれており，2人のプレーヤーが交互にカードを取り合い，手元のカードに書かれた値の和（得点）を最大化するゲームを行う．2 人とも自分の得点を最大化するように最適な戦略を取った時，先行が後攻より何点多くなるか，出力せよ．

素直に書きました．実行時間が短い他の回答も，中身は同じようなものでした．

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)

sum1 = 0
sum2 = 0
for i in range(n):
  if i%2 == 0:
    sum1 += a[i]
  else:
    sum2 += a[i]
print(sum1-sum2)

ABC085B - Kagami Mochi

問題

入力

\begin{aligned}
&N \\
&d_{1} \\
&\vdots \\
&d_{N}
\end{aligned}

（$N,d_{i}$は整数で，$1\leq N,d_{i} \leq 100$）が与えられる．集合$\{d_{i}\,|\, i=1,...,N\}$の要素を使って$a_{1} < a_{2} < \cdots < a_{M}$を満たす数列$\{a_{i}\}_{i}^{M}$をつくるとき，$M$として取りうる最大の値を出力せよ．

与えられたデータの重複をなくせば昇順/降順に並び替えられます．よって，集合$\{d_{i}\,|\, i=1,...,N\}$の要素数を答えればよいだけですね．set()でできるようです．

• 組み込み型 — Python 3.9.2 ドキュメント

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

他の回答も似た感じでした．

ABC085C - Otoshidama

問題

入力

\begin{aligned}
&N~Y
\end{aligned}

（$N$は整数，$Y$は$1000$の倍数で，$1\leq N \leq 2000$，$1000 \leq Y \leq 2\times 10^{7}$）が与えられたときに，

\begin{aligned}
\begin{cases}
\, Y=10000x + 5000y + 1000z \\
\, N=x+y+z
\end{cases}
\end{aligned}

を満たす非負整数の組$(x,y,z)$がある場合は「$x~y~z$」の例を1つ出力し，ない場合は「$-1~-1~-1$」を出力せよ．

2式から$z$を消去すると$Y/1000 - N=9x+4y$となります．$1\leq x+y\leq N$の範囲でこの式を満たす$(x,y)$があるか探せば良いですね．break処理は次を参考にしました：

• Pythonで多重ループ（ネストしたforループ）からbreak | note.nkmk.me

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

flag = False
for i in range(n+1):
  for j in range(n-i+1):
    if 0 == 9*i + 4*j + n - total/1000:
      flag = True
      print(str(i)+' '+str(j)+' '+str(n-i-j))
      break
  if flag:
    break

if flag == False:
  print('-1 -1 -1')

この問題の実行時間が短い回答では，次が参考になります．$z$を消去するところまでは同じですが，ループの数が1つ少なくて済んでいます．注目すべき点は以下です．

• $x=(Y/1000-N-4y)/9$は整数だから，$(Y/1000-N-4y)$は$9$で割り切れる必要がある．
• 上の関係式から$(x,y)$の組が定まるが，複数候補があるなら，最も小さいものが$z=N-x-y \geq 0 $という制約条件を満たす可能性がある．よって，for b in range(9)で十分（bが小さい方から探索すれば同じこと）．

def solve(N, Y):
    # 10000 * a + 5000 * b + 1000 * c = Y
    # a + b + c = N
    # 0 <= a, b, c

    # 10000 * a + 5000 * b + 1000 * (N - a - b) = Y
    # 9000 * a + 4000 * b = Y - 1000 * N
    # 9 * a + 4 * b = Y / 1000 - N

    # a = ((Y / 1000 - N) - 4 * b) / 9

    t = Y // 1000 - N
    for b in range(9):
        if (t - 4 * b) % 9 == 0:
            a = (t - 4 * b) // 9
            c = N - a - b
            if a < 0 or b < 0 or c < 0:
                return -1, -1, -1
            return a, b, c

N, Y = [int(x) for x in input().split()]

print(*solve(N, Y))

ABC049C - 白昼夢

問題

入力

\begin{aligned}
&S
\end{aligned}

（$S$は英小文字からなる文字列で，$1\leq |S| \leq 10^{5}$）が与えられる．空文字列$T$の末尾にdream dreamer erase eraser のいずれかを追加する操作を繰り返して$S=T$となる場合は「YES」を出力し，そうでない場合は「NO」出力をせよ．

文字列$S$の端から，該当する文字列を削除していき，すべての文字が消えるかどうかを判定しました．スライスの方法が不慣れで苦労しました．．．

s = input()
list = ['dream', 'dreamer', 'erase', 'eraser']

while True:
  s_prev = s
  for c in list:
    if s[-len(c):] == c:
      s = s[:len(s)-len(c)]
  if s == s_prev:
    break

if len(s) == 0:
  print('YES')
else:
  print('NO')

実行時間が短い回答は以下です．どわー，なるほど，これで済むのか．

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

len(s)==0ではなく，s==""で判定している回答もありました．

ABC086C - Traveling

問題

入力

\begin{aligned}
&N \\
&t_{1}~x_{1}~y_{1} \\
&t_{2}~x_{2}~y_{2} \\
&\vdots \\
&t_{N}~x_{N}~y_{N}
\end{aligned}

（$N,t_{i},x_{i},y_{i}$は整数で，$0\leq x_{i},y_{i} \leq 10^{5}$，$1\leq N, t_{i} \leq 10^{5}$，$t_{i} < t_{i+1}$）が与えられる．各行は，時刻$t$と点$(x(t),y(t))$の組を表す．このとき，入力データ$\{(t_{i},x_{i},y_{i})\}_{i=1}^{N}$に$(0,0,0)$を加えたデータが

\begin{aligned}
&\bigl(t+1, x(t+1), y(t+1)\bigr) \\
&=
\begin{cases}
\, \bigl(t, x(t)\pm 1,y(t)\bigr) \\
\, \bigl(t, x(t),y(t)\pm 1\bigr)
\end{cases}
\end{aligned}

のいずれかを満たし得る場合は「YES」を出力し，そうでない場合は「NO」出力をせよ．

苦労しました．．．次のように考えました．

• 時間ステップ差が偶数なら，偶数回移動する．よって，$x$方向と$y$方向の移動距離を足すと偶数になる．
• 同様に，時間ステップ差が奇数なら，$x$方向と$y$方向の移動距離を足すと奇数．
• 最大で移動できる距離＝時間ステップ差．これより短い点は，到達後に他の点を行ったり来たりすれば到達できる（時間ステップと移動距離の偶奇性を満たす限り）．

n = int(input())

start = [0, 0, 0]
flag = False
for _ in range(n):
  end = list(map(int, input().split()))
  diff = [end[i]-start[i] for i in range(3)]
  dist = abs(diff[1]) + abs(diff[2])
  if diff[0]%2 == dist%2:
    if dist <= diff[0]:
      start = end
    else:
      flag = True
      break
  else:
    flag = True
    break
    
if flag == True:
  print('No')
else:
  print('Yes')

終わりに

全ての提出で「正解」のものから，参考になるコードを引っ張ってきましたが，そのコードを提出すると，追加ケースで不正解になる場合があるようです．

コードを参考にする際は注意が必要ですね．