競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - ABC Swap
三つの箱の中身を決まった操作で入れ替える問題です。
最初から入れ替え操作の位置は決まっているので、x, y, zをz, x, yと順番を変えて出力するだけです。
x, y, z = map(int, input().split())
print(z, x, y)
B - Popular Vote
N種類の商品内に一定以上の投票数を得た商品がM個以上あるかを探す問題です。
与えられた得票数をソートし、M番目の商品が条件を満たしているか調べました。これで通りました。
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
if A[M-1] >= sum(A) / (4 * M):
print('Yes')
else: print('No')
C - Replacing Integer
与えられたNからKを引き続けると最小値はいくらになるか答える問題です。
与えられた数字から引き続けて最後に残る数字...というのは余剰項を求める計算に相当します。一個多く引いた場合、というのはその余剰項からKを引いた値(のマイナス)になります。
以下のコードで実装しました。
N, K = map(int, input().split())
print(min(N%K, K-N%K))
D - Lunlun Number
ルンルン数という条件を満たしているK番目の数字を求める問題です。
パッと見の条件は簡単そうに見えるのですが、K番目の数を効率よく求める方法が全くわからず諦めました。
解説を見ました。この問題では一度使った数の右端にもう一つ条件を満たす数字をつけていくことで高速で求めていくことができます。解説ではキューを使用することでこれを行っていました。
キューにまず1~9までの数字を入れる。左端を取り出し、その値を$x$とする。$x$の1の位を$r$とする。$r$が「0」なら$10x, 10x+1$を計算し、それぞれ再びキューに入れる。同様に$r$が「1~8」なら$10x+(r-1), 10x + r, 10x+(r+1)$、rが「9」なら$10x - 1, 10x$を計算し、再びキューへ。
これを繰り返して、k回目に取り出した値が求める数字です。
というのをそのまま実装してみました。
K = int(input())
Q = [i for i in range(1, 10)]
for _ in range(K):
x = Q.pop(0)
r = x%10
if r != 0: Q.append(x*10 + r - 1)
Q.append(x*10 + r)
if r != 9: Q.append(x*10 + r + 1)
print(x)
これだとTLE。pop()の速度が遅いようです。取り出す処理はいらないとみて、全て配列のまま保持してforで回してみます。
K = int(input())
Q = [i for i in range(1, 10)]
k = 0
for q in Q:
if k >= K:
break
r = q%10
if r != 0:
Q.append(q*10 + r - 1)
k += 1
Q.append(q*10 + r)
k += 1
if r != 9:
Q.append(q*10 + r + 1)
k += 1
print(Q[K-1])
これで通りました。
追記
コメントで指摘を受けました。キューを扱う時はちゃんとライブラリを使用しましょう。
pythonではcollections.deque()クラスを用いることで、キューを扱うことができます。append(), appendleft(), pop(), popleft()などの関数があります。
import collections
K = int(input())
Q = collections.deque([i for i in range(1, 10)])
for _ in range(K):
x = Q.popleft()
r = x%10
if r != 0: Q.append(x*10 + r - 1)
Q.append(x*10 + r)
if r != 9: Q.append(x*10 + r + 1)
print(x)
E - Yutori
一定のルールで働く日と働かない日を決めたとき、必ず働く日はどれか答える問題です。
諦めて解説を見ました。
まず、働くことができる日数がノルマに対して余裕ができる場合、もしくはノルマに足りない場合は無条件でアウトになります。
というわけでギリギリまで働く日数を埋めた場合を考えます。まず右端から順番に働ける日を数えた配列Rを作成。この配列には、「$x$回目に働く日は$R[x]$以前である」という情報が含まれます。同様に左端から順番に働く日を数えた配列Lの場合、「$x$回目に働く日は$L[x]$以降である」という情報が含まれます。よって$L[x]$と$R[x]$が一致する時が必ず働く日だといえます。
これを実装したのが以下のコード。これで通りました。
N, K, C = map(int, input().split())
S = input()
L = []
R = []
holiday = 0
for i in range(N):
if holiday:
holiday -= 1
elif S[i] == 'o':
L.append(i)
holiday = C
holiday = 0
for i in range(N-1, -1, -1):
if holiday:
holiday -= 1
elif S[i] == 'o':
R.append(i)
holiday = C
R = R[::-1]
if len(L) == K:
for l, r in zip(L, R):
if l == r: print(l+1)
この記事はここまでとします。