A - Poor

与えられた三つの数の内、二つ等しい数があるか答える問題です。

単純に比較で求めてもいいですが。この問題は「要素が二種類入っているか」を聞かれている、とも言いかえられるのでそっちを調べてみましょう。配列の重複要素を削除するにはset型オブジェクトを使用するのが便利なようです。

A = list(map(int, input().split()))
if len(set(A)) == 2:
  print('Yes')
else: print('No')

B - Papers, Please

与えられた配列の要素が「偶数なら3か5で割り切れる」という条件を満たしているか調べる問題です。

全ての要素を調べて、偶数なのにどちらでも割り切れなかったら拒否します。

N = int(input())
A = list(map(int, input().split()))

for a in A:
  if a%2 == 0 and not (a%3 == 0 or a%5 == 0):
    print('DENIED')
    break
else:
  print('APPROVED')

C - Poll

文字列がいくつか与えられるので、最も出現回数の多い文字列(同数なら辞書順で全て)を出力する問題です。

文字列を配列に格納。collections.Counterを用いて集計。max()で最大値を取って、出現回数が最大値である文字列だけを一つの配列へ。これをsorted()で並べなおして出力しました。

import collections
N = int(input())
S = [input() for _ in range(N)]
count = collections.Counter(S)
maxV = max(count.values())
c = [k for k, v in count.items() if v == maxV]
print('\n'.join(sorted(c)))

D - Pairs

与えられた配列から作られるペアの積を全て順番に並べた時、K番目に小さい値が何か答える問題です。

わかりません。諦めました。他の解答を参考にします。

ほとんど他の解答を参考に、自分がわかりやすいよう書いたのが以下のコードです。コメントで可能な限り解説を付けていますが、正直よくわかってない部分が多いです。コメントも正しいか自信がないです(特に?がついてる部分)。

import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
A = np.sort(A)

G = A[A > 0]
Z = A[A == 0]
L = A[A < 0]

l, r = 10**18, -10**18

while l-r > 1:
  # 「積がm以下になるペアの数」を調べる。
  m = (l+r) // 2

  # A[A > 0]内から条件を満たすものの数?
  Pk = np.searchsorted(A, m//G, side="right").sum()

  # A[A < 0]内から条件を満たすものの数?
  Nk = (N - np.searchsorted(A, (-m-1)//(-L), side="right")).sum()

  # A[0]内から条件を満たすものの数?
  Zk = 0
  if m >= 0:
    Zk += len(Z) * N

  # 同じ要素同士の積は選べないため、条件を満たしていたら減らす
  duplicate = np.count_nonzero(A*A <= m)

  # 条件を満たす要素の数を合わせる
  k = Pk + Nk + Zk - duplicate

  # 全要素が二重になっている。重複要素を削除
  k //= 2

  # 条件を満たす要素数kがK個以上ならmを低く、Kより少ないならmを高くする
  if k >= K:
    l = m
  else:
    r = m
#lとrが一致すればmが一意に定まる
print(l)

これで通りました。

以下の部分が全くわかってません。どうしてこれで条件を満たす個数がわかるのか...考えたんですけど諦めました。

  # A[A > 0]内から条件を満たすものの数?
  Pk = np.searchsorted(A, m//G, side="right").sum()

  # A[A < 0]内から条件を満たすものの数?
  Nk = (N - np.searchsorted(A, (-m-1)//(-L), side="right")).sum()

E - Payment

最も「出す枚数とお釣りの枚数の合計」が小さくなるようなお金の払い方を考える問題です。ただし、この世界の現金は$10^n$単位のお札しかありません。

下から順番に数えてみます。払う枚数が5以下ならそのまま払い、6以上なら次の桁に繰り上げて、お釣りを受け取ったほうが効率がいいでしょう。

だめなやつ.py

N = list(map(int, input()))
N = N[::-1] + [0]

count = 0

for i, n in enumerate(N):
  if n <= 5:
    count += n
  elif n > 5:
    count += 10 - n
    N[i+1] += 1

print(count)

これだとWAです。上のコードだと条件抜けがありまして、例えば$95$円払おうと思うと$100$円出してお釣りを受け取る方が(合計6枚)効率がいいです。このままでは$105$円払って合計7枚。

5が出た時だけ条件がさらに分岐します。一つ上の桁が5以上なら繰り上がることでお釣りを1枚減らすことができます。

通ったやつ.py

N = list(map(int, input()))
N = N[::-1] + [0]

count = 0

for i, n in enumerate(N):
  if n < 5:
    count += n
  elif n > 5:
    count += 10 - n
    N[i+1] += 1
  elif n == 5:
    if N[i+1] >= 5:
      N[i+1] += 1
    count += 5

print(count)

解説を見ると解き方が異なりました。

上から順番に金額の枚数を調べていきます。金額を「ピッタリ払う時」「1枚多く払う時」の二つを求めることで繰り上がりの計算に対応します。

解説の通りに書いてみる.py

N = list(map(int, input()))

m = 0 # 最小の枚数
m_ = 1 # 繰り上がり時の枚数、常にnが1枚多いと思って確保する

for n in N:
  m, m_ = min(m + n, m_ + 10-n), min(m + (n+1), m_ + 10-(n+1))
print(m)

こんなシンプルに書けるとは。

この記事はここまでとします。

AtCoder Beginner Contest 155の復習, E問まで(Python)

A - Poor

B - Papers, Please

C - Poll

D - Pairs

E - Payment