競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
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以上なら次の桁に繰り上げて、お釣りを受け取ったほうが効率がいいでしょう。
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枚減らすことができます。
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枚多く払う時」の二つを求めることで繰り上がりの計算に対応します。
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)
こんなシンプルに書けるとは。
この記事はここまでとします。