1/30 日記
今日は体調は良くも悪くもなく普通。起きた時間は10時くらい。
高橋君が訪れる点はK個で、座標上の点をすべて管理するのは大変なので自然とsetで管理しようとなる（ここまではいつもの感じ）。
そこで、例えば右向きに移動するとき、そっちの方向に訪問済の頂点が連続していくつあるのかを高速に求められればいい。このとき、点(x, y)をそのまま set[x].insert(y) みたいにsetに組み込むと、探索に最悪O(K)かかってしまう。なので、点ではなくて区間をsetにpair ( 始点, 終点 ) の状態で組み込むことを考える。ある点を区間としてsetに組み込むとき、その点のすぐ前後に区間が存在するかに注意する必要がある。
このアルゴリズムはDancing Linksと呼ばれているそう。実装は重たい。
・寿司打
最初に挑戦したときは5.4 words/secだったのが、今日やったら5.8 words/secまで速くなってた。6.0 words/secまではいけそう。
・ABC
A、B、C…やる。Cを解き終えるまで手が震えていた。
D…初項をa+1, 項数をRとすると R(R+1+2*a)=2*N
という式が出てくるので、約数列挙。
F…k=0のときの転倒数を元にk=1~N-1も計算したくなる。
kが増えるごとに先頭の数akが後ろに行くが、このときの転倒数の変化は
(akより大きい数の個数)-(akより小さい数の個数）であることが分かる。
E…制約からbitDPじゃないかとは思ったけど、最小全域木というワードが頭から離れなくて困った。（これを見てた様々な全域木問題 (slideshare.net)）
結局AC出来ず。
コンテスト中のムーブはさほど悪くなかったような、、、
実はEは既出で、PASTの問題に出ていたらしい。
最近の黄diff精進は長い目で見て良い効果があると思っているけど、黄diffに限らず自分が解けなさそうな問題を探して精進、というのでやってみようかな。
ところで、PASTの問題をABCに出すのはPASTを受けるように誘導してる？笑
ぷらにゃ好きだよ、おやすみ
