ABC183

ついに全問正解した！しかもノーミス。コンテスト中に全問終わるの初めてだったので、21分くらい残った時間を何に使ったら良いかわからなくて食器と浴槽を洗ってました(苦笑) Fは正解のつもりでなく「ダメだと思うけど速度だけが問題であって答えはあってるのかを確認しよう」と思って送信したら意外と時間内に収まったのでビックリした。つまり考察は間違っていたが「速度を実際より遅く見積もる」というミスだったのでダメ元送信で通った。

max(0, x)とか考えた人もいるみたいだけど素朴にやりました 40sec 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}$ 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 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 += dist[prev][x]
            prev = x
        d += dist[prev][0]
        if d == K:
            ret += 1
    return ret

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

N, 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")

考えたこと
- 普通に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次元配列に入れる]]してる

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

    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 ret

考えたこと
- クラスの種類は20万ありえる
- UnionFindでできなさそう？
  - 対数オーダーでできないか？
- UnionFindでやる場合、代表元にクラスごとの個数を持たせる
  - 「クラスxが何人」という値を素朴に配列で持つとO(N)
  - 読み出しは定数オーダー
    - これを対数オーダーまで落として良いので、代わりにマージを高速にしたい
  - 読み出しを対数オーダーにする→二分探索
    - ソート済み配列として持ったらどうなる？
    - マージは内容物の量の線形オーダー
  - 内容物のオーダーでいいならハッシュテーブルで良いのでは
    - キーがないことがあるのでdefaultdict、いや、個数カウントだからCounterか
  - 一旦それで送信してみて他のバグがないか確認してみよう→意外とあっさりAC
実装
- UnionFindライブラリに手を入れてマージ時にCounterを更新する python

def 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])  # ***

- 本体

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([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の実装で木の高さを圧縮するために「ランクの高い方に低い方をマージ」してることによって類似の効果が起きて間に合った

🪴 Quartz 4.0

ABC183

Graph View

Backlinks