第二回 アルゴリズム実技検定 バチャ 解法メモ
Time 165:01
A
Bならに, Fならに置き換えて差を取る
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
最初に料理のある日に至るまでをシミュレーション
に至ってからは前計算の結果を利用
(D日経つ間に行う食事の回数を求めておく)
N
これれふね……になって遅延セグ木使いながら平面走査
(取得が1点なので累積すればBITとかで十分だろうけど頭壊したくなかったため……)
https://atcoder.jp/contests/joisc2012/tasks/joisc2012_fortune_telling
O
最小全域木の間の辺のを引いてを足す
HL分解&RMQ
感想
前回に比べて難しい……
HL分解とか出てきたし(多分いいやり方あるんだろうけど)