チーム練(ICPC 2019 Pacific Northwest Regional)

問題が解けるセットは　たのしいね

9完8ペナ あと一問通したかった
小さなミスが多すぎる

A (のん, 02:55 + 1)
B (番兵, 02:49 + 3)
C (Md, 00:32)
D (Md, 00:18 + 1)
E (番兵, 00:24)
G(Md, 04:37 + 2)
I (Md, 01:23)
L (のん, 03:33)
M (のん, 00:48 + 1)

解説

A
全方位木DP　ゆきのんががんばって遷移を生やしてくれた

B
数字ごとに一番うしろに現れる点を持っておいて、セグ木でがんばる

C
最短路を交互に塗るのが最適 dist(1, n) - 1が答え

D
ペナを生やしちゃ、だめだろ

E
気づいたら通ってた

G
移動する時間を考えなくていいように適当にずらしておく
始点と終点それぞれを表す区間和のセグ木beg, edをもつ（累積和で良かった）
列の各区間についてセグ木に始点と終点を登録する
行の各区間pについてactivateされない列の数はed.query(0, p.first+1) + beg.query(p.second, MAX)
なので足し合わせて n - 総和が答え

同じ線に複数回パルス波が流れると勘違いしててやばかった

I
二要素をswapして同じ文字列になるようなもの同士を辺でつないだグラフを作って、その上で最大独立集合を求めたい
このグラフは二部グラフになるので、n - 最大マッチングがこたえ

L
気づいたら通ってた

M
頂点数 + 連結成分の数 - 辺数