😸

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

2021/02/20に公開

Python

競技プログラミング

AtCoder

tech

所感

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$ なので，問題文通りに愚直に実装すればおｋ

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

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

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

参考

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

脚注

https://mathtrain.jp/tantyou ↩︎