ABC192
5問でした
F: 解説通りのDPしたけどPythonではTLEだったんだい(WAも残ってたのでそれどころではない
https://gyazo.com/f2e118fa49ab00fdb89fcf2c1c96746b
微増。精進しなければ伸びることはないか。
https://gyazo.com/c93bbfb428ebc5acd746c40f54c87fcd
B - uNrEaDaBlE sTrInG
code:python
def main():
S = input().strip().decode('ascii')
from string import ascii_uppercase, ascii_lowercase
if all(c in ascii_uppercase for c in S1::2) and all(c in ascii_lowercase for c in S::2):
print("Yes")
else:
print("No")
C - Kaprekar Number
https://gyazo.com/8097ec006474aceeb4c5dd630171199a
制約を眺めて、高々10桁で、10^5回だったら文字列を使ってOKと判断した
code:python
def main():
N, K = map(int, input().split())
for _i in range(K):
s = str(N)
g1 = int("".join(sorted(s, reverse=True)))
g2 = int("".join(sorted(s)))
N = g1 - g2
print(N)
D - Base n
https://gyazo.com/20de3e3b0cb898e05578754ebb60eea9
考えたこと
1桁の時、何進法でも値は変わらない、0か1通り
2桁以上の時、nを増やすと必ず値が増えるので、ようはM以下の条件を満たす最大のnを見つける問題
最悪ケースを考えると入力が10の時、最大で10^18進法になる
→線形探索はダメ
二分探索で良さそう
実装
intのbase指定を使おうとしたんだけど、36進法までしか対応してなかった
int(s, base)を自前で実装しようとしたが、何も正確に数を求めなくてもMを超えてるかどうかだけ知れれば良い、と考え直した
自前実装してたらTLEしてたと思う
二分探索チェックリストを見て実装
WA
チェックリスト見てたのに失敗パターン4の「rightの初期値が条件を満たしてる」をやってしまった
初期値をMにしてたけど入力が10の時Mは条件を満たしてる、M+1にすべき(# (1))
code:py
def lessEqual(s, base, limit):
ret = 0
for c in s:
ret *= base
ret += int(c)
if limit < ret:
return False
return True
def solve(X, M):
sX = str(X)
if len(sX) == 1:
if X <= M:
return 1
else:
return 0
d = max(int(c)for c in str(X))
v = int(sX, d + 1)
if M < v:
return 0
left = d + 1
start = left
right = M + 1 # (1)
while left < right - 1:
x = (left + right) // 2
if lessEqual(sX, x, M):
left = x
else:
right = x
return right - start
Twitterで見かけた案
Xがw+1桁で、baseがbの時、int(X, b)は$ x_1b^w + x_2b^{w-1} + \cdots \ge x_1b^w
$ M \ge x_1b^wを解いて $ \exp(\log(M / x_i) / w) \ge b、bを線形探索で見つければ良い、というもの
残念ながらこの問題条件の範囲だと倍精度浮動小数点数で精度が足りない
10 ** 18 - exp(log(10 ** 18)) == 1408.0
10 ** 18は64ビット弱あるが、倍制度浮動小数点数の仮数部は52ビット。
E - Train
https://gyazo.com/2ccd302fb095dbce2a184c8be4dcd279
考えたこと
距離があらかじめ決まってないダイクストラだね
ダイクストラ法ではある頂点にたどり着く最速の時間が決まってから他の頂点への時間を計算する
今回の問題では最初は距離が決まってないけど、到着時刻が決まれば隣の街にいつ着くのかは決まる
実装
TとKを取り違えたり、発車までの時間-currentTime % KをcurrentTime % Kにしてたりでデバッグに時間がかかった# (1)
code:py
def one_to_one(
start, goal, num_vertexes, edges,
INF=9223372036854775807, UNREACHABLE=-1):
distances = INF * num_vertexes
distancesstart = 0
queue = (0, start)
while queue:
d, frm = heappop(queue)
if distancesfrm < d:
# already know shorter path
continue
if frm == goal:
return d
for to, T, K in edgesfrm:
# distance depends on currentTime
currentTime = distancesfrm
dist = (-currentTime % K) + T # (1)
new_cost = currentTime + dist
if distancesto > new_cost:
# found shorter path
distancesto = new_cost
heappush(queue, (distancesto, to))
return UNREACHABLE
def main():
N, M, X, Y = map(int, input().split())
from collections import defaultdict
edges = defaultdict(list)
for _m in range(M):
A, B, T, K = map(int, input().split())
edgesA - 1.append((B - 1, T, K))
edgesB - 1.append((A - 1, T, K))
INF = 9223372036854775807
r = one_to_one(X - 1, Y - 1, N, edges, INF)
if r == INF:
r = -1
print(r)
F - Potion
https://gyazo.com/54e3cfc010ef6ef10274535dd6e407d5
考えたこと
最初「X以上」と勘違いしてた
しかしそれだと全部正なんだから全部入れるのが自明な解になる
おかしいとおもったら「ちょうどX」だった
k個選んでSとした時に$ \sum_{i\in S} A_i \equiv X \pmod{k}であることが必要
Aの部分集合全部について考えると2^50になって間に合わない
DPで状態を押しつぶす
今までに選んだ個数n、最終的に選ぶ個数k、今までの和Vとして(n, k, V % k) -> Vのテーブルを最大値で更新すれば良い
最大以外のものは答えに影響しないから
それぞれ1〜100なのでテーブルサイズ10^6、更新回数100、合わせて10^8かー、ギリギリだなぁ
実装
サンプルは通ったが6WA 14TLE
WAのまま高速化してもデバッグが面倒になるだけ
バグを直したが未だ9WA 11TLE、ここでタイムアウト
公式解説
方針は違わないな
ACの人と比較
あー、これ2回目の提出の時に「バグを直して、軽く高速化」ってやって、その高速化でバグを入れてるじゃん
複数の変更を一度にしてはいけない、ソフトウェア開発の基本だぞー
バグを直して15TLE
添え字をタプルから整数に直して11TLE
辞書をリストに直して…あ、そうかこれ更新の順番に気をつけないといけなくて、辞書を二つ使ってたのか、それは遅いな
整数にパックする順番を工夫して大きい方から更新すれば問題が起きないようにし、リストにした、AC
code:python
def solve(X, AS):
from collections import defaultdict
INF = 9223372036854775807
N = len(AS)
def to_key(mod, num, k):
return num * (N + 1) * (N + 1) + k * (N + 1) + mod
def from_key(key):
num, km = divmod(key, (N + 1) * (N + 1))
k, mod = divmod(km, N + 1)
return (mod, num, k)
SIZE = (N + 1) ** 3
table = -1 * SIZE
sumAS = sum(AS)
for k in range(1, N + 1):
tableto_key(0, 0, k) = 0
for a in AS:
for key in reversed(range(SIZE)):
if tablekey == -1:
continue
mod, num, k = from_key(key)
v = tablekey + a
num += 1
if num > k:
continue
mod = v % k
key = to_key(mod, num, k)
tablekey = max(tablekey, v)
ret = INF
for key in range(SIZE):
if tablekey == -1:
continue
mod, num, k = from_key(key)
if num == k and num > 0:
v = tablekey
if mod == X % k:
assert (X - v) % k == 0
s = (X - v) // k
ret = min(ret, s)
return ret
1942msか…際どいな
これで問題ならキーの変換関数をインライン展開するとかかな…
他の人のコードを読む
あーなるほど、kの大きい(つまり増加速度の速い)方からチェックしていって、全部取っても無理になったらbreakする手があるのか a2stnk
まずkごとに分けることで1238msまで減る
そして枝刈りを追加することでなんと331msに！
Pythonの中で3位の速さになった
この枝刈りがとてもよく効くということか