ABC183 - 西尾泰和の外部脳

ABC183

ついに全問正解した！しかもノーミス。

コンテスト中に全問終わるの初めてだったので、21分くらい残った時間を何に使ったら良いかわからなくて食器と浴槽を洗ってました(苦笑)

https://gyazo.com/c3a83f04dc6802c2d35d8b209448675b

Fは正解のつもりでなく「ダメだと思うけど速度だけが問題であって答えはあってるのかを確認しよう」と思って送信したら意外と時間内に収まったのでビックリした。つまり考察は間違っていたが「速度を実際より遅く見積もる」というミスだったのでダメ元送信で通った。

max(0, x)とか考えた人もいるみたいだけど素朴にやりました 40sec

code:python

x = int(input())

if x > 0:

print(x)

else:

print(0)

ビリヤードのボールの半径がゼロだったので驚いた

今回、僕の得意な数学問題が出なかったなーと思ってたけどもこの問題で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

code:python

SX, SY, GX, GY = map(int, input().split())

dx = GX - SX

dy = GY + SY

ret = SY / dy * dx + SX

print(ret)

8の階乗は40320です

全探索でOK

code:python

def 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 += distprevx

prev = x

d += distprev0

if d == K:

ret += 1

return ret

溜めておけないことに注意

溜めておけないので、各時点での需要量を調べて供給を超えないことが必要

開始と終了をリストに入れてソートしかけたが開始や終了が同じ点に重なってる時にバグらずにきちんと実装するのは面倒だなと考えて、改めて問題条件をみたら時間軸解像度が10^5程度だったのでいもす法にしました

code:python

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

diff = 0 * 20_0010

for _i in range(N):

S, T, P = map(int, input().split())

diffS += P

diffT -= P

usage = 0

for v in diff:

usage += v

if usage > W:

print("No")

return

print("Yes")

考えたこと

普通にDPすると、2000×2000×3×2000で間に合わなさそう

3方向の範囲和を累積和を使って定数オーダーにすれば2000×2000だから良さそう

まず素直なDPでサンプルケース通ることを確認し、それから累積和に変える累積和しながらDP

こんな感じ

code:python

# hvalue = 0

# p = pos

# while True:

# p -= 1

# if datap == 0:

# break

# hvalue += tablep

# debug(divmod(pos, WIDTH), hvalue, msg=":pos")

hvalue = h_accumpos - 1

# debug(divmod(pos, WIDTH), hvalue, msg=":accum")

horizontal, vertical, diagonalの3方向の累積和を扱う

壁を通れないことは壁のところで累積和をゼロにすれば良い

地図は地図を1次元配列に入れるしてる

code:python

def 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

tableWIDTH + 1 = 1

h_accumWIDTH + 1 = 1

v_accumWIDTH + 1 = 1

d_accumWIDTH + 1 = 1

for pos in allPosition():

if pos == WIDTH + 1:

continue

if datapos == 0:

tablepos = 0

h_accumpos = 0

v_accumpos = 0

d_accumpos = 0

continue

h_value = h_accumpos - 1

v_value = v_accumpos - WIDTH

d_value = d_accumpos - WIDTH - 1

ret = h_value + v_value + d_value

ret %= MOD

tablepos = ret

h_accumpos = (h_accumpos - 1 + ret) % MOD

v_accumpos = (v_accumpos - WIDTH + ret) % MOD

d_accumpos = (d_accumpos - WIDTH - 1 + ret) % MOD

return ret

考えたこと

クラスの種類は20万ありえる

UnionFindでできなさそう？

対数オーダーでできないか？

UnionFindでやる場合、代表元にクラスごとの個数を持たせる

「クラスxが何人」という値を素朴に配列で持つとO(N)

読み出しは定数オーダー

これを対数オーダーまで落として良いので、代わりにマージを高速にしたい

読み出しを対数オーダーにする→二分探索

ソート済み配列として持ったらどうなる？

マージは内容物の量の線形オーダー

内容物のオーダーでいいならハッシュテーブルで良いのでは

キーがないことがあるのでdefaultdict、いや、個数カウントだからCounterか

一旦それで送信してみて他のバグがないか確認してみよう→意外とあっさりAC

実装

UnionFindライブラリに手を入れてマージ時にCounterを更新する

code:python

def unite(x, y):

x = find_root(x)

y = find_root(y)

if x == y:

return # already united

if rankx < ranky:

parentx = y

clsy.update(clsx) # ***

else:

parenty = x

if rankx == ranky:

rankx += 1

clsx.update(clsy) # ***

本体

code:python

def main():

global cls

from collections import Counter

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

init_unionfind(N)

CS = list(map(int, input().split()))

cls = [Counter([CSi - 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(clsroot.get(b - 1, 0))

公式解説

小さい方を大きい方にマージすれば、マージごとにサイズが2倍以上になるので最悪でもlogN回しかマージされないのでNlogN未満で収まる

小さい方から大きい方へ移すことで最悪計算量が改善される

この見積もりはできてなかった

最悪ケースでダメなことには気付いていたが解決策が思いついてなかった

しかしUnionFindの実装で木の高さを圧縮するために「ランクの高い方に低い方をマージ」してることによって類似の効果が起きて間に合った