2/3 日記
眠すぎる
応用情報の締め切りは来週までか～
詰め切るのが難しかった。
メニューの周期はDであることと、好みの料理を食べる回数⇔食堂の利用回数の関係を利用したいので、ダブリングが有効であると考えられる（i日目とj日目のメニューがCi=Cjであり、i ~ j の間にそのようなメニューが無いとき、L日間がiとjの間にいくつ入るかは( i - j -1 ) / Lで求めることができる。これから、
sum[now][j]=sum[now][j-1]+sum[nxt][j-1]の要領で、2^k回好みの料理を食べたとき、好みの料理以外を食べた回数が高速に求められる）。
i 番目の人につき、FiからスタートしてメニューがKiである日まで移動する（これは二分探索等を使う）。そこからは桁DPのようにやればいい（具体的には、
Ti≧2^p + sum[now][p]のときに、Ti-=2^p+sum[now][p], now=pos[now][p]
といった更新を行えばいい。
ところでこれ、Wavelet Matrixで解けないかな。
括弧が絡む問題は、スタックに見立てると上手くいくことが多いのかな。
今回はそれで上手くいく。( が来たらscoreを+1, )が来たらscoreを-1することを考える。dp[i][score]:=i番目までみて合計がscoreであるときにかかる費用の最小値 とすると解ける。scoreが負にならないようにし、i 番目の文字に対する操作をもとに遷移を考えればいい。
考え中。
2/2 日記
今日はめちゃんこおねむにゃん
ぷらにゃをぷにゃぷにゃ
結局、並列二分探索で解けた。
最小全域木を最初に構成し、そこにi番目の辺(u, v)を加えることを考える。
すると、もともと最小全域木に含まれていたu - vパス上の辺のどれか一つを取り除くことができると分かる（図を描くと分かりやすい）。
そのような辺のうち、もっともコストが大きいものを除いたものがクエリ k = i の答えとなる。これをどのようにやるかが問題となるが、最小全域木の構成方法は
「残った辺のうち、連結でない2点を結ぶようなものをコストが小さい順に貪欲に追加していく」どいうものであり、これを利用する。
最小全域木を構成する過程で u と v が連結になったとすると、そのとき加えた辺が取り除くべき辺であることが分かる（追加した辺のうち最もコストが大きく、かつu - v パス上の辺である）。
これをM個やっていては間に合わないため、並列二分探索をする。毎回の操作では最小全域木を構成しながら、途中の段階で u と v が連結であるか判定すればよい。
二次元平面なので、敷地領域の角の座標とビルの建設予定地点を合わせてしまい、x座標でソートして小さい順に見ていけば、あとはy軸方向だけに着目すればよくなる。y~y+DにCを足す（または引く）という操作をしたいので、遅延セグ木を使う。また、座標が-10^9~10^9なので座標圧縮しておく。
i-1番目の項がnowであるとすると、i番目の項の存在範囲が
[ now+1, N-D*(K-i) ] であることが分かる。この範囲で最小値を取る項のうち、最も左に存在するものを選んでいけばいい。最小値はセグ木で求め、後はその値の項が現れるまで順にシミュレートしていけばいい。
考え中。
明日バチャ参加しようかな～
2/1 日記
ねむねむにゃんこ
PASTを進めていました
単純に親を辿ることを考えると、子が1つの頂点が連なっていた場合にO(N^2)とかになって難しいことが分かる。aとbのLCAがbであればいいので、これで解ける。
時間かかってしまって反省。
グリッドの左下をP, 右下をQ, 右上をRとし、グリッド上のある点Ｘに対し、
D(X) = PX + QX + RXを考える。D(X)の最小値が求める値であることが分かる ( XからP, Q, R への道がX以外で交わっているとすると、その点をYとしたときにXからYへの道が2つ以上存在することになり、どちらかの道を整備しなくても条件を満たすことから、最小性に反することが証明できる）。
なので、グリッド上の点Xを全探索し、この点からbfsによってD(X)を求めていけばいい。
考え中。これみたいにk=1~Mについて求めよという問題は①こないだのABC-F - Shift and Inversions (atcoder.jp)みたいに、k=1の値（または以前に求めた値）を元に順々に求めていけるやつ、➁クエリを何かでソートしていい感じになるやつ③並列二分探索
くらいをまず考えたくて、これは③ではないかと思ってる（並列二分探索とUnion-Findは相性がいい気がしている）。
でも単純にUFを使おうとすると、使わなければいけない辺が異なるためにUFをM個用意するはめになって困る。なので、辺を重みでソートして小さい順に使っていき、ok or ngの判定をするときにa と bを辺でつないで、判定が終わったら辺を切るというのでどうかと考えている。
実装する気力はないので明日かな。
おやすみなさい。
1/31 日記
もう1月も終わるのか、はやいなあ
エキサイティングな毎日を送りたい。。。
・E - Magical Ornament (atcoder.jp)
昨日解けなかった問題。TSPであることが分かれば考察要素はほぼない（bfsを使うとCiどうしの距離がスマートに求められる）。
なんで解けなかったのか、TSPの理解が不十分だったのかも（最初に最小全域木と勘違いしてしまった後、TSPが頭の中に介入してこなかった。制約をきちんと観察することと、考察の第一手を間違えたときにどう仕切り直すかを考えたい。）
これはほぼ一緒の問題。
少し手こずった。期待値の問題。
サイコロの目の数は6*N個で、普通に再帰をするとO(N^2)で定数倍が重くてTLEする。
ここで、今出た目をNumとしたとき、どのサイコロを振るのが一番期待値が高いのかを高速に求めたいと考える（普通にやれば6*N通り試す必要がある）。各サイコロについて、次に有効になるサイコロの目はNumより大きいので、Numより大きい目の期待値の累積和を取り、それらをsetで管理するとO(logN)で次に振るべきサイコロとその期待値を求めることができる。
制約がちょっと謎だった。W=10^9は実行時間制限が4 secだからなんとか間に合う。
ただ、imos法をやろうとするとメモリが足りなくなる。よって、各石の（位置、コスト）の情報を配列に保持し、その石の位置に来た時に処理すればいい。
平均最大化の問題（蟻本にもある）。問題として解くのは初めてかも。
ある平均値xが達成可能であるとしたとき、選択したモンスターの集合をSとして
( ∑( i ∈ S) Bi ) / ( ∑ (i ∈ S ) Ai ) ≧ x が成り立ち、
∑ ( i ∈ S ) ( Bi - Ai * x ) ≧ 0 が成り立つ。
よって、Bi - Ai * x でソートし、大きい方から5個取ったときの総和が0以上ならok、0未満なら ng 、という感じに x を二分探索していけばいい。
推しは偉大。
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を受けるように誘導してる？笑
ぷらにゃ好きだよ、おやすみ
1/29 日記
今日は眠いので寝る
明日起きたらコドフォバチャしようかな
・F - Fork in the Road (atcoder.jp)
いつもの、という感じの問題だった。
メモ化再帰をするけど、削除する辺を全探索するとO(M^2)とかになって厳しいので、
削除する辺の始点を全探索すればよく、O(NM)になる。
解説にはO(M)もあった（期待値と一緒に確率もメモしていくやり方。普通の式変形で解けるからそこまで難易度は高くない気もする）。
最近は睡眠欲とぎゅー欲がすごい。
欲望に忠実に生きる。
1/28 日記
今日は読みたい本があるので、精進は早めに切り上げた。
・C - Permutation City (atcoder.jp)
dfsを使う。
葉から順番に決めていくのはすぐに思いつくけど、子が複数ある場合や根の相手側がなくなった場合を丁寧に考える必要がある。
・サイクル基底
面白そうだったので読んだ。
サイクル基底・サイクルの個数について - 競プロ練習記録 (hatenablog.com)
