😸

AtCoder SOMPO HD プログラミングコンテスト2021 (ABC192) 個人的メモ

2021/02/20に公開

所感

abce4完
highest更新
やったぜ
abc192score

A - Star

コンテスト中に提出したコードは100の倍数を小さいほうから順に見ていく
forループの上限が10^{15}の理由は忘れた
解の最大値が10^5+100なので,10^6で十分

X = int(input())
limit = 10 ** 15
 
for i in range(limit):
    if X < 100 * i:
        print(100 * i - X)
        break

こっちはコンテスト後のもっと速いコード
-X\ mod\ 100を計算すれば,X以上の最も近い100の倍数との差が分かる
ただし,Xが100の倍数ちょうどの時は-X=0(mod\ 100)となるので注意

X = int(input())
separation = 100

if X % separation:
    print(-X % separation)
else:
    print(separation)

B - uNrEaDaBlE sTrInG

事前に英子文字の集合と英大文字の集合を作っておいて,奇数番目と偶数番目の文字がそれぞれ含まれるかを判定
公式解説でislower,isupper関数使ってたけど,知らなかった

S = input()

small = set([chr(i) for i in range(ord("a"), ord("z") + 1)])
big = set([chr(i) for i in range(ord("A"), ord("Z") + 1)])

for i in range(2):
    for s in S[i::2]:
        if (s in small and i == 0) or (s in big and i == 1):
            continue
        print("No")
        exit()

print("Yes")

C - Kaprekar Number

K\leqq 10^5なので,問題文通りに愚直に実装すればおk

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

for _ in range(K):
    big = "".join(sorted(str(N), reverse=True))
    small = "".join(sorted(str(N)))
    N = int(big) - int(small)

print(N)

D - Base n

分からんかった
文字列Xn進法表記の数とみなして得られる値をf(n)とする

  • Xが2文字以上から成る時
    f(n)は狭義単調増加となるので,二分探索で解を求められる
    (x_1<x_2f(x_1)<f(x_2)の時,その区間内でf(x)を狭義単調増加と言う)[1]
  • Xが1文字から成る時
    f(n)nに寄らず一定の値となる
    • X\leqq Mならば解は1
    • X> Mならば解は0

参考

https://atcoder.jp/contests/abc192/editorial/721
https://blog.hamayanhamayan.com/entry/2021/02/20/233715

def func(n):
    """n進法のXを返す"""
    return sum([n ** i * X[i] for i in range(len(X))])


X = list(map(int, list(input())))[::-1]
M = int(input())

if len(X) == 1:
    if X[0] <= M:
        print(1)
    else:
        print(0)
    exit()

left = max(X)
right = M + 1
while abs(left - right) > 1:
    mid = (left + right) // 2
    if func(mid) > M:
        right = mid
    else:
        left = mid

print(left - max(X))

E - Train

ダイクストラ法
名前以外忘れてたのでググった
この記事公式ドキュメント参考にした
記事の通りに実装してacしたので,典型問題だと思う

from heapq import heappush, heappop

N, M, X, Y = map(int, input().split())
train = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, t, k = map(int, input().split())
    train[a].append((b, t, k))
    train[b].append((a, t, k))
INF = 10 ** 18

# (現在時間,現在地)
queue = [(0, X)]
duration = [INF] * (N + 1)

while queue:
    time, station = heappop(queue)

    if duration[station] <= time:
        continue
    duration[station] = time

    if station == Y:
        break

    for next_station, riding, start in train[station]:
        cal = time + riding + -time % start
        heappush(queue, (cal, next_station))

if duration[Y] == INF:
    print(-1)
else:
    print(duration[Y])

脚注
  1. https://mathtrain.jp/tantyou ↩︎

Discussion