AtCoder Beginner Contest 192 (A,B,C,D,E) 感想

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest192)

ABC192の感想です。先に解きたい人は解いてから見てねー。（定型文）

atcoder.jp

A問題(Star)

これくらいなら40秒でちょいちょいですよ！！！

a = int(input())

print(100-a%100)

B問題(uNrEaDaBlE sTrInG)

タイトルは "unreadable string" です。
python のストリング型にはislowerというメソッドがあるのでそれを使えば簡単です！ここまで5分！

s = input()

for i in range(len(s)):
    if i %2 ==0:
        if not s[i].islower():
            print("No")
            exit()
    else:
        if s[i].islower():
            print("No")
            exit()
print("Yes")

C問題(Kaprekar Number)

カプレカ数というやつらしいです。愚直に実装すればよさそうですね。
関数を作ろうかなと思いましたが、速さを重視して適当に書いちゃいました。10分！

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

ans = [N]
for i in range(K):
    g1 = list(str(ans[-1]))
    g1.sort(reverse=True)
    g1 = "".join(g1)
    g1 = int(g1)
    g2 = list(str(ans[-1]))
    g2.sort()
    g2 = "".join(g2)
    g2 = int(g2)
    ans.append(g1-g2)
print(ans[-1])
    
    

D問題(Base n)

これに１時間かかってしまいました。難易度は水色です。
愚直にやると無理そうなのは X = 11, K = 10**18 とか考えると分かります。なのですこし考えなければなりません。
Xをn進数だと思って10進数に直した結果というのはnに関して狭義単調増加なんですよね。（これはちゃんとコンテスト中にも示した。）なのでKを超える境目を二分探索で探せばいいです。めぐる式二分探索で検索検索ぅ！！

最後は一桁の場合がコーナーケースで、そこさえ乗り越えればクリアです。私は二分探索までは10分で気づきましたがコーナーケースで50分溶かしました。

def is_ok(d):
    # 条件を満たすかどうか？問題ごとに定義
    res = 0
    for i in range(len(X)):
        res += int(X[i])*pow(d,len(X)-i-1)
    if res <= M:
        return True
    elif res:
        return False


def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

X = input()
M = int(input())

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


d = list(X)
d.sort()
d = int(d[-1])

# print(res)
ans = meguru_bisect(10**18+10,d) - d 

print(ans)

E問題(Train)

またもやE問題解けませんでした‥。（もはや定型文）
今回はD問題がE問題より難しいので実質E問題解けたというか溶けたというか...。

典型的なダイクストラの問題ですね。時間切れでコンテスト中には出来ませんでしたが、典型ダイクストラを貼っつけてコストの部分を本問に合うようにすれば終わりです。(INFを10**9とかにすると弱いので10**18にしておきます。また、コストが確定した点はcontinueで飛ばすようにしないとafter_contestで落ちます。)

from heapq import heappush, heappop
import math
INF = 10 ** 18
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        if seen[v] == True: continue
        seen[v] = True
        for to, cost, k in g[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and math.ceil(dist[v]/k)*k + cost < dist[to]:
                dist[to] = math.ceil(dist[v]/k)*k + cost
                heappush(hq, (dist[to], to))
    return dist

v, e, X, Y = map(int, input().split())
g = [[] for _ in range(v)]

for _ in range(e):
    a, b , t, k = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append([b,t,k])
    g[b].append([a,t,k])
# print(g)


ans = dijkstra(X-1,v)
# print(ans)
if ans[Y-1] != INF:
    print(ans[Y-1])    
else:
    print(-1)

感想

ABCD4完(パフォーマンス1093)でレートが50あがりました！うれぴよ。
最近は東京への引っ越しの費用を貯めるために一ヶ月くらいABCに参加できていなかったり、基本情報技術者試験やTOEIC、JavaScript ネットワーク docker AWS など色々勉強していて精進もまったくしていないのでレートが上がって一安心しました。毎週問題は見てますが、手を動かさないと忘れてしまいますね。

ARCは上位層にレートを吸収されるので出ません！（しかし面白いから出ちゃう。悔しい。）