ABC193
5問しか解けなかったけど自己ベスト更新でした。
https://gyazo.com/66fbb4cdf9248927491c87940c0e16c1
https://gyazo.com/295a6fe07a61e4df1c3dbe6ce0e03dc6
C - Unexpressed
https://gyazo.com/cb635c05c6816e60ce37299f58bd2f2c
表せる数が大した個数ない
多くても$ \sum \log_i N [2 \le i \le \sqrt{n}]
なので全部数えれば良い
一番多いa=2の時で高々30ちょいで、aは最大で10^5までしかいかないので余裕だと判断できる
追記: 実際に数えた結果102230だった
code:py
def main():
N = int(input())
from math import sqrt, floor
ok = set()
MAX_A = floor(sqrt(N))
for a in range(2, MAX_A + 1):
x = a * a
while x <= N:
ok.add(x)
x *= a
print(N - len(ok))
D - Poker
https://gyazo.com/407827a9676a567be92cd4e082d29d83
手札は高々81通りしかないので全部試せば良い
code:py
def main():
K = int(input())
S = input().strip().decode('ascii')
T = input().strip().decode('ascii')
scount = 0 * 9
tcount = 0 * 9
rest = K * 9
for i in range(4):
s = int(Si) - 1
t = int(Ti) - 1
scounts += 1
tcountt += 1
rests -= 1
restt -= 1
def calcScore(xs):
ret = 0
for i in range(9):
ret += (i + 1) * (10 ** xsi)
return ret
ret = 0
for a in range(9):
if resta == 0:
continue
pa = resta
resta -= 1
scounta += 1
for b in range(9):
if restb == 0:
continue
pb = restb
tcountb += 1
if calcScore(scount) > calcScore(tcount):
ret += pa * pb
tcountb -= 1
resta += 1
scounta -= 1
ret /= (9 * K - 8) * (9 * K - 9)
print(ret)
E - Oversleeping
問題文が長くてスクリーンショットに収まらないので割愛
要するに周期Nのうちのある範囲でONになるものと、周期Mのうちのある範囲でONになるものがあるときに、両方ONになるもっとも早い時刻を求めよという問題
NとMは10^9オーダーなので実際に各周期を試すのは無理
しかし、その周期の中でONになってる期間は最大500と小さく制限してある
中国剰余定理で「Nで割ってあまりa, Mで割ってあまりb」となる最小の値を対数オーダーで求めることができる
500×500の組み合わせ全部について中国剰余定理して、全体での最小を答えれば良い
自分のライブラリ実装はN,Mが互いに素である仮定のものだったけど、今回はそうとは限らないので急いで修正
code:python
def crt(a, m, b, n):
"""
Find x s.t. x % m == a and x % n == b
>> crt(2, 3, 1, 5)
11
>> crt(1, 4, 3, 6)
9
"""
x, y, g = extended_euclidean(m, n)
if g == 1:
return (b * m * x + a * n * y) % (m * n)
s = (b - a) // g
return (a + s * m * x) % (m * n // g)
def main():
from math import gcd
T = int(input())
for _t in range(T):
X, Y, P, Q = map(int, input().split())
m = 2 * X + 2 * Y
n = P + Q
ret = INF = 9223372036854775807
g = gcd(n, m)
for a in range(X, X+Y):
for b in range(P, P + Q):
if a % g == b % g:
x = crt(a, m, b, n)
ret = min(ret, x)
if ret == INF:
print("infinity")
else:
print(ret)
✅ABC193F
前回 ARC113