ABC183
ついに全問正解した！しかもノーミス。
コンテスト中に全問終わるの初めてだったので、21分くらい残った時間を何に使ったら良いかわからなくて食器と浴槽を洗ってました(苦笑)
Fは正解のつもりでなく「ダメだと思うけど速度だけが問題であって答えはあってるのかを確認しよう」と思って送信したら意外と時間内に収まったのでビックリした。つまり考察は間違っていたが「速度を実際より遅く見積もる」というミスだったのでダメ元送信で通った。
A
max(0, x)とか考えた人もいるみたいだけど素朴にやりました 40sec
pythonx = int(input())
if x > 0:
print(x)
else:
print(0)B
ビリヤードのボールの半径がゼロだったので驚いた
今回、僕の得意な数学問題が出なかったなーと思ってたけどもこの問題で30分溶かしたり二分探索したりした人もいるみたい
dxが負の時のことを少し心配して考えたがケアしなくて大丈夫 5min
公式解説
Sxから Gxへの変化を Sy:Gyに内分する
\frac{S_x G_y+G_x S_y}{S_y+G_y}
僕の解法
\frac{S_y (G_x - S_x)}{G_y + S_y} + S_x
pythonSX, SY, GX, GY = map(int, input().split())
dx = GX - SX
dy = GY + SY
ret = SY / dy * dx + SX
print(ret)C
8の階乗は40320です
全探索でOK
pythondef solve(N, K, dist):
from itertools import permutations
ret = 0
for order in permutations(range(1, N)):
d = 0
prev = 0
for x in order:
d += dist[prev][x]
prev = x
d += dist[prev][0]
if d == K:
ret += 1
return retD
溜めておけないことに注意
溜めておけないので、各時点での需要量を調べて供給を超えないことが必要
開始と終了をリストに入れてソートしかけたが開始や終了が同じ点に重なってる時にバグらずにきちんと実装するのは面倒だなと考えて、改めて問題条件をみたら時間軸解像度が10^5程度だったのでいもす法にしました
pythonN, W = map(int, input().split())
diff = [0] * 20_0010
for _i in range(N):
S, T, P = map(int, input().split())
diff[S] += P
diff[T] -= P
usage = 0
for v in diff:
usage += v
if usage > W:
print("No")
return
print("Yes")E
考えたこと
普通にDPすると、2000×2000×3×2000で間に合わなさそう
3方向の範囲和を累積和を使って定数オーダーにすれば2000×2000だから良さそう
まず素直なDPでサンプルケース通ることを確認し、それから累積和に変える 累積和しながらDP
こんな感じ
python# hvalue = 0
# p = pos
# while True:
# p -= 1
# if data[p] == 0:
# break
# hvalue += table[p]
# debug(divmod(pos, WIDTH), hvalue, msg=":pos")
hvalue = h_accum[pos - 1]
# debug(divmod(pos, WIDTH), hvalue, msg=":accum")horizontal, vertical, diagonalの3方向の累積和を扱う
壁を通れないことは壁のところで累積和をゼロにすれば良い
地図は地図を1次元配列に入れるしてる
pythondef solve(H, W, data):
MOD = 1_000_000_007
N = len(data)
table = [0] * N
h_accum = [0] * N
v_accum = [0] * N
d_accum = [0] * N
table[WIDTH + 1] = 1
h_accum[WIDTH + 1] = 1
v_accum[WIDTH + 1] = 1
d_accum[WIDTH + 1] = 1
for pos in allPosition():
if pos == WIDTH + 1:
continue
if data[pos] == 0:
table[pos] = 0
h_accum[pos] = 0
v_accum[pos] = 0
d_accum[pos] = 0
continue
h_value = h_accum[pos - 1]
v_value = v_accum[pos - WIDTH]
d_value = d_accum[pos - WIDTH - 1]
ret = h_value + v_value + d_value
ret %= MOD
table[pos] = ret
h_accum[pos] = (h_accum[pos - 1] + ret) % MOD
v_accum[pos] = (v_accum[pos - WIDTH] + ret) % MOD
d_accum[pos] = (d_accum[pos - WIDTH - 1] + ret) % MOD
return retF
考えたこと
クラスの種類は20万ありえる
UnionFindでできなさそう？
対数オーダーでできないか？
UnionFindでやる場合、代表元にクラスごとの個数を持たせる
「クラスxが何人」という値を素朴に配列で持つとO(N)
読み出しは定数オーダー
これを対数オーダーまで落として良いので、代わりにマージを高速にしたい
読み出しを対数オーダーにする→二分探索
ソート済み配列として持ったらどうなる？
マージは内容物の量の線形オーダー
内容物のオーダーでいいならハッシュテーブルで良いのでは
キーがないことがあるのでdefaultdict、いや、個数カウントだからCounterか
一旦それで送信してみて他のバグがないか確認してみよう→意外とあっさりAC
実装
UnionFindライブラリに手を入れてマージ時にCounterを更新する
pythondef unite(x, y):
x = find_root(x)
y = find_root(y)
if x == y:
return # already united
if rank[x] < rank[y]:
parent[x] = y
cls[y].update(cls[x]) # ***
else:
parent[y] = x
if rank[x] == rank[y]:
rank[x] += 1
cls[x].update(cls[y]) # ***本体
pythondef main():
global cls
from collections import Counter
N, Q = map(int, input().split())
init_unionfind(N)
CS = list(map(int, input().split()))
cls = [Counter([CS[i] - 1]) for i in range(N)]
for _q in range(Q):
typ, a, b = map(int, input().split())
if typ == 1:
unite(a - 1, b - 1)
else:
root = find_root(a - 1)
print(cls[root].get(b - 1, 0))公式解説
小さい方を大きい方にマージすれば、マージごとにサイズが2倍以上になるので最悪でもlogN回しかマージされないのでNlogN未満で収まる
小さい方から大きい方へ移すことで最悪計算量が改善される
この見積もりはできてなかった
最悪ケースでダメなことには気付いていたが解決策が思いついてなかった
しかしUnionFindの実装で木の高さを圧縮するために「ランクの高い方に低い方をマージ」してることによって類似の効果が起きて間に合った
Related Pages
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]