ABC183
ついに全問正解した！しかもノーミス。
コンテスト中に全問終わるの初めてだったので、21分くらい残った時間を何に使ったら良いかわからなくて食器と浴槽を洗ってました(苦笑)
A
- max(0, x)とか考えた人もいるみたいだけど素朴にやりました 40sec python
x = 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$
- Sxから Gxへの変化を Sy:Gyに内分する
python
SX, SY, GX, GY = map(int, input().split())
dx = GX - SX
dy = GY + SY
ret = SY / dy * dx + SX
print(ret)
C
- 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
D
- 溜めておけないことに注意
- 溜めておけないので、各時点での需要量を調べて供給を超えないことが必要
- 開始と終了をリストに入れてソートしかけたが開始や終了が同じ点に重なってる時にバグらずにきちんと実装するのは面倒だなと考えて、改めて問題条件をみたら時間軸解像度が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")
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次元配列に入れる](/ja/%E5%9C%B0%E5%9B%B3%E3%82%921%E6%AC%A1%E5%85%83%E9%85%8D%E5%88%97%E3%81%AB%E5%85%A5%E3%82%8C%E3%82%8B)してる
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
F
- 考えたこと
- クラスの種類は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の実装で木の高さを圧縮するために「ランクの高い方に低い方をマージ」してることによって類似の効果が起きて間に合った
- 小さい方を大きい方にマージすれば、マージごとにサイズが2倍以上になるので最悪でもlogN回しかマージされないのでNlogN未満で収まる