🐶

ABC235解説:本番でACできた問題+1問(Python)

2022/01/30に公開約2,500字

A - Rotate

https://atcoder.jp/contests/ABC235/tasks/abc235_a
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

https://atcoder.jp/contests/ABC235/tasks/abc235_b

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

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

https://atcoder.jp/contests/ABC235/tasks/abc235_c

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

https://atcoder.jp/contests/ABC235/tasks/abc235_d

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])

Discussion

ログインするとコメントできます