第二回アルゴリズム実技検定バチャ解法メモ

Time 165:01

A
B $x$ なら $(-x+1)$ に, $x$ Fなら $x$ に置き換えて差を取る
B
数える
C
どこが山崩しかよく分かんない……になってとりあえず書かれたとおりにやる

D
再帰でTを列挙して調べる
E
全始点から調べる
F
優先度付キューに放り込む

G
dequeでランレングス圧縮状態で持つ
H
11×N×M頂点のグラフでBFSをしそうになったけど踏みとどまって
dpをする(2つのマス間の距離はマンハッタン距離なので)
I
深さNの再帰でやる

J
制約が小さいので愚直に
K
dp[i][j] i文字目まで見て'('が')'よりj個大きい状態の最小値
L
後ろすぎてK文字取れなくならない範囲の文字を(文字、位置)の組にして優先度付キューに入れる

M
最初に料理 $K_j$ のある日に至るまでをシミュレーション
$K_j$ に至ってからは前計算の結果を利用
(D日経つ間に行う食事の回数を求めておく)
N
これれふね……になって遅延セグ木使いながら平面走査
(取得が1点なので累積すればBITとかで十分だろうけど頭壊したくなかったため……)
https://atcoder.jp/contests/joisc2012/tasks/joisc2012_fortune_telling
O
最小全域木の $A_i,B_i$ 間の辺の $\max$ を引いて $C_i$ を足す
HL分解＆RMQ

感想

前回に比べて難しい……
HL分解とか出てきたし(多分いいやり方あるんだろうけど)