🐶

ABC235解説：本番でACできた問題＋1問（Python）

2022/01/30に公開

Python

A - Rotate

a.py

a, b, c = list(input())

abc = int(a + b + c)
bca = int(b + c + a)
cab = int(c + a + b)
print(abc + bca + cab)

入力の各桁の総和を111で掛けると答えが出るという天才解法もあるようです。

a.py

# https://atcoder.jp/contests/ABC235/editorial/3257
a, b, c = map(int, list(input()))
print((a + b + c) * 111)

B - Climbing Takahashi

慌てると配列外参照などのペナをする可能性のある問題です。
高橋君は右端に行く可能性があること、初期値は左端であることを意識します。

b.py

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

# 初期値は左端
ans = H[0]

# 右端(N)まで探索
for i in range(1, N):
    if H[i - 1] >= H[i]:
        break
    ans = H[i]

print(ans)

C - The Kth Time Query

defaultdictを用いて各値が何番目に現れるかを記録します。
xがdefaultdictの中に含まれており、かつkがxの要素数以下の場合にその値を出力し、それ以外を-1とします。

c.py

from collections import defaultdict

N, Q = list(map(int, input().split()))
a = list(map(int, input().split()))
xk = [tuple(map(int, input().split())) for _ in range(Q)]

d = defaultdict(list)

for i in range(N):
    d[a[i]].append(i + 1)

for x, k in xk:
    if x in d and k <= len(d[x]):
        print(d[x][k - 1])
    else:
        print(-1)

最後の条件分岐については、いっそのことtry-exceptで行ったほうが安心かもしれません。

for x, k in xk:
    try:
        print(d[x][k - 1])
    except:
        print(-1)

D - Multiply and Rotate

BFSを用いて部分和問題を解くといったイメージになります。

書かれている数をNに変化させるには最小で何回の操作が必要かという問いを書かれている数をNに変化させるまでの最短経路を求めよという問題に言い換えられるかが最大の山場になります。

最短経路問題といえばBFSを使って解くことになりそうです。

次に、回数を格納する配列（dist）の大きさを考えます。
この問題において考慮すべき値は最大で $999,999$ となります。
それ以上の大きな値は操作1,2をしても必ず $10^{6}$ 以上の値となってしまうので不適です。

例えば $1,000,003$ の場合、操作1、2のあとの値は以下のようになります。

操作1：1,000,006（a = 2のとき）
操作2：3,000,001

これは $N<10^{6}$ の条件を満たしません。
よって、回数を格納する配列には 999,999個の要素を用意すれば十分ということになります。

d.py

from collections import deque

a, N = map(int, input().split())

MAX = 10 ** 6

# dist[x]には値xを達成するのに必要な最小回数が格納されます
dist = [-1] * MAX
dist[1] = 0

que = deque()
que.append(1)
while que:
    now = que.popleft()
    dist_now = dist[now]
    # 操作1を行います
    op1 = a * now
    if op1 < MAX and dist[op1] == -1:
        dist[op1] = dist_now + 1
        que.append(op1)
    # 条件を満たせば、操作2を行います
    if now >= 10 and now % 10 != 0:
        s = str(now)
        op2 = int(s[-1] + s[:-1])
        if op2 < MAX and dist[op2] == -1:
            dist[op2] = dist_now + 1
            que.append(op2)

print(dist[N])

A - Rotate

B - Climbing Takahashi

C - The Kth Time Query

D - Multiply and Rotate

Discussion