はまやんはまやんはまやん

hamayanhamayan's blog

雪の足跡 [yukicoder 340]

競技プログラミング

問題

https://yukicoder.me/problems/no/340

W×Hの盤面があり、N人の人がそこを通る。
i番目の人はM[i]回移動していて、移動先はB[i][j]->B[i][j + 1]である。
移動元と移動先はw + h * Wで表記されていて、距離が1とは限らない。

その移動後に(0,0)から(W - 1, H - 1)へN人が移動した方向と同じ方向に移れるとしたときの最短距離を求めよ。

1 <= W, H <= 10^3
0 <= N, M[i] <= 10^3
0 <= B[i][j] < W * H

続きを読む

競技プログラミングにおける2-SAT問題まとめ

競技プログラミング

2-SATとは

  • 「x ∧ y」の選言の充足判定をする 解説 コドフォ記事
  • 2-SATはSCCで解ける
  • ダメな組合せが見つかったときに制約を作る

問題

競技プログラミングにおけるマージテク問題まとめ

競技プログラミング

マージテク

  • 正式名称、データ構造をマージする一般的なテク
  • 集合をまとめる時に大きい方に小さい方を移動させることでマージさせると計算量がならしO(logN)
  • 発祥の地
  • 併合(マージ)可能なheapをmeldable heapといい、実装の1つとしてマージテクを使うものがある(O(log^2N),Skew HeapだとO(logN))
  • 複数配列を全部FFTで畳み込む時にマージテクっぽい技を使うときがある こっちに書いた

問題

木DPっぽいやつをマージテクで高速化

  • CSAcademy Uniform Trees
  • ECR2 Lomsat gelral 解説1 解説2 解説3
  • ARC086 Smuggling Marbles （木のマージテクだけどO(N)になる）
  • CF221 Tree and Queries 解説1 解説2
    • ある色の頂点数がx以上の色の数を数えるdpのマージが、一見、マージテクになっていないように見えるが、ある色に対してマージ元にi個、マージ先にj個あった場合に[i+1,i+j]に+1をしていくのだが、この個数を全て足すとマージ先の頂点数と等しくなる
    • その為、マージ先の頂点数を別途数えて、その数を見てマージテクをやろう

まだ解いてない

【発展的話題】Sack (dsu on tree)

競技プログラミングにおける全方位木DP問題まとめ

競技プログラミング

全方位木DP

問題

違うけど方針が似ている問題

競技プログラミングにおける木の同型判定問題まとめ

競技プログラミング

木の同型判定問題

問題

続きを読む