AtCoder ABC 161

ABC3完緑パフォでした。以下振り返りと反省。

ABC Swap

問題のリンク

概要

• 箱に数字が入っている。
• との中身を入れ替える。
• との中身を入れ替える。
• 最終的な数字の中身は？

制約

• 
• 入力は全て整数

考察

勿論一発でprint(Z, X, Y)で行けるし、分かってるんだけど、凡ミスが怖くて謎にダラダラ書きました。（あとで振り返ると逆に間違いやすい気もしなくもない。）

コード

X, Y, Z = map(int, input().split())
X, Y, Z = Y, X, Z
X, Y, Z = Z, Y, X
print(X, Y, Z)

B - Popular Vote

問題のリンク

概要

• 種類の商品について人気投票をした。投票結果は数列
• 得票数が 以上の商品を選べる。
• 選べる商品数がM以上か否か。

制約

• 
• 
• は異なる
• 入力は全て整数

考察

普通に全探索した。ちなみにこの問題、出力結果を Yesではなく、YESにしてしまって1WAしてしまいました。C以下の問題で1ペナはきつい。。

コード

N, M = map(int, input().split())
A = list(map(int, input().split()))
to = sum(A)
cnt = 0
for a in A:
    if a>=(to * (1/(4*M))):
        cnt += 1

if cnt >= M:
    print('Yes')
else:
    print('No')

C - Replacing Integer

問題のリンク

概要

• 整数に対して、以下の操作を好きな回数だけ処理できる時、取り得る値の最小値を求めよ。
• 操作：をとの差の絶対値で置き換える。

制約

• 
• 
• 入力は全て整数

考察

• 制約を見るからに全探索はできない。
• 割り切れるだけ割り切った数。もしくはそこから更にを引いた数が0付近に集まるので、小さくなりそう。

コード

N, K = map(int, input().split())
mod = N%K
print(min(mod, K-mod))

D - Lunlun Number

問題のリンク

概要

• 隣あうどの2つの桁の値についても、差の絶対値が1以下の数をルンルン数と定義する。
• 1から数えて番目に小さな数を求めよ。

ここはどうやるのか、全然分からず本番中に手も足も出ませんでした。

制約

• 
• 入力は全て整数

考察

• 取り敢えず全探索がダメってとこで止まってしまった。
• 本番後の解説でキューを使うという文言を見て、色々試行錯誤した結果以下のようなコードに、実際に値を取り出してはいないものの、iをイテレータで回していることで、headを1つずつずらしてる。

コード

K = int(input())
Q = list(range(1, 10))
 
for i in range(K):
    x = Q[i]
    y = x%10
    if y != 0:
        Q.append(10*x + y-1)
    Q.append(10*x + y)
    if y != 9:
        Q.append(10*x + y+1)
 
print(Q[K-1])

• 連続した数字が3つ（もしくは2つ）規則的に出てきてるなってのは実際に数列を手書きしている中で気づいた。
• それをキューを使って実装しようという発想が本番中は全く出てこなかった。反省。

E - Yutori

問題のリンク

概要

• 日間のうち、日間働く。
• ある日働いたら、その直後の日間は働かない。
• のi文字目が x の時は働かない。

解説みて、どう実装すれば良いかはひとまず分かった。でもなぜその様に考えられるかは分かった様な分からない様な感じ。

制約

• 
• 
• 
• の長さは
• の各文字はx or o
• 問題文中の条件を満たすように働く日を選ぶことが可能

方針

スライド作ってみた。

コード

N, K, C = map(int, input().split())
S = list(input())
rS = S[::-1]
lcnt, rcnt = 0, 0
left, right = [0]*N, [0]*N
llimit, rlimit = -1, -1

for i in range(N):
    # 左から貪欲
    # llimit (数字がカウントされた日+C日)以降
    # 上記かつ、シフトに入れる日 ('o')であればシフトに入る。
    if S[i] == 'o' and llimit<i:
        lcnt += 1
        left[i] = lcnt
        llimit = i + C

    # 右から貪欲
    if rS[i] == 'o' and rlimit<i:
        rcnt += 1
        right[-(i + 1)] = K + 1 - rcnt
        rlimit = i + C

#print(left)
#print(right)

# leftとrightで同じ数字が入っている日にちを出力
for i in range(N):
    if left[i]==right[i] and left[i]>0:
        print(i + 1)