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

競プロ初心者の復習用記事です。

ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。

# [A - Poor](https://atcoder.jp/contests/abc155/tasks/abc155_a)

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

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

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

# [B - Papers, Please](https://atcoder.jp/contests/abc155/tasks/abc155_b)

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

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

```python
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](https://atcoder.jp/contests/abc155/tasks/abc155_c)

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

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

```python
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](https://atcoder.jp/contests/abc155/tasks/abc155_d)

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

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

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

```python
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)
```

これで通りました。

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

```python
  # 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](https://atcoder.jp/contests/abc155/tasks/abc155_e)

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

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

```python:だめなやつ.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枚減らすことができます。

```python:通ったやつ.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枚多く払う時」の二つを求めることで繰り上がりの計算に対応します。

```python:解説の通りに書いてみる.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)
```

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

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