Link Cut Tree の get_root ヤバかった
Link Cut Treeを書いてみた
色んな人のプログラムをみて「へー」とか「ほー」とか言いながらつぎはぎして書いたらヤバイことが起きた
対象プログラム pic.twitter.com/JMz5AC88vL
— むげーーーーーん (@mugen_1337) 2021年4月24日
get_rootした後splay(root)しない
— むげーーーーーん (@mugen_1337) 2021年4月24日
(昨日みさわさんにヤバイと教えてもらった方) pic.twitter.com/YCNdSHlFX8
splay(root)をします pic.twitter.com/mCJuaP7WxR
— むげーーーーーん (@mugen_1337) 2021年4月24日
これ,それはそうだった.
頑張ってSplay木を深くまで潜ってrootを引っ張ってきたとき,splay木の形が一切変わらずに,もっかい同じクエリが来るとヤバイ!
それはそう
rootを見つけてきて,splay(root)をするとよくて,こうなると,splay木の形がイイ感じになるので,もっかい同じクエリが来ても,イイ感じの木を探索するので,大丈夫になる.
1つ気づいたこととして,布団の中でLink Cut Treeについて想いを馳せると,木のrootとsplay木のrootを混同して死ぬ.
起きて紙でしっかり考える
数え上げ memo
大事なこと
- 主客転倒(数え上げる対象を逆転してみる)
- まずはnaiveなDPを考える
考え中
包除を考える場合,ある状態の最大がhogehoge以上,とかいう包除はキツいことが多そう.管理しずらいので
E - LEQ and NEQ
これは連続する2つの値が同一にならないような列の数え上げだが,となる部分の個数の偶奇で数え上げて最後に包除している
数式記述メモ
できることのメモ
から個選ぶ,1個以上は連続を含む
選ばれなかったものの集合を考える.
間隔が以上の空間がある.この個数Xで包除
とする(選ばないもの)
->
->
...
->
掛け合わせている1つ目はどこの隙間を間隔k以上にするか
2つ目はその隙間を確保した上で,どう塗るか
これを包除してあげると解ける
No.1414 東大文系数学2021第2問改 - yukicoder
https://yukicoder.me/submissions/635358
間隔をK以上開けて配置するパターン数
https://atcoder.jp/contests/typical90/tasks/typical90_o
物をT個置く -> 物の間にK以上追加でそれぞれ何個置くかをcombinationでやってやる
カタラン数関連
下のsnukeさんの記事の斜め線がどこに置いてあっても折り返しを考えれば解ける snuke.hatenablog.com
https://yukicoder.me/submissions/635379
となる非負整数組の数え上げ
係数の総和をKとしたとき,O(K3 log S)
// coef_0 * x_0 + coef_1 * x_1 ... =s // をみたす非負整数(x_0, ...)の組の数を求める // sum(coef)の行列を累乗する. mint myfunc(vector<int> coef,ll S){ if(S<0) return mint(0); int n=(int)coef.size(); int cs=0; for(auto &x:coef){ assert(x>0); cs+=x; } assert(cs<=1000);// 多分1000でも耐えない vector<mint> A(cs+1,0); for(int bit=1;bit<(1<<n);bit++){ int t=0; for(int i=0;i<n;i++)if((bit>>i)&1) t+=coef[i]; if(__builtin_parity(bit)) A[t]+=1; else A[t]-=1; } Matrix<mint> M(cs); rep(i,cs) M[0][i]=A[i+1]; for(int i=1;i<cs;i++) M[i][i-1]=1; M=M.pow(S); return M[0][0]; }
Editorial - AtCoder Beginner Contest 198
この問題では条件にx_1 < x_2...みたいな条件が付くが,差分を考えて変形することで項同士の関係を外してそれぞれの項が非負である条件のみを考えればよくなる
UTPC 2020参加記
コンテスト前
リアルで集まって出たい!
ICPCチームメイツに声をかけるぜ!
1人欠けるから1人集めるぜ!
仮の人さんよろしくやで!
じゃあ当日集まってコンテストね!
仙台緊急事態宣言「ダメやで」
は?
コンテスト
開始前作戦
Aは仮の人さん
僕はBから見る
sota君は後ろから見る
得意分野を相談した結果↓
DPっぽい何か,僕
— むげんちゃん (@mugen_1337) 2021年3月27日
グラフ,sotaくん
数学,仮の人さん
仮の人さんがAを通す.
sota君がHを通す.
僕がDの部分点をとりあえず通す.
sota君がGを通す.
Dの部分点からの高速化ができないのでsota君を呼んで一緒に考えるがわからない
sota君&仮の人さんがJにかかることに
僕は分岐してDの考察とEの部分点にかかる
僕がEの部分点を通す
sota君がJを実装して通す
僕はD, Eの満点を考えるけどわからない
終了
D,解けなきゃダメじゃん.すまん...
感想
D, E復習します
パズルに屈しない
屈した
D - 101 to 010
結局,1011111みたいなのと1111101みたいなのを取るしかない.
それらを組み合わせて元の文字列を作ることを考える.
実験しても気づくか微妙
naive解は作れるので方針乱打してnaiveと合うか,その方針は何がダメかの確認は手元でできたが,あまりに効率が悪いと思う
数列,2項以外全部1にして解ける? -> 方程式が解ける形に落ちた. カス
TODO
溜まってきたらなんかいい感じにまとめる
卒業研究 参加記
大変でした
yukicoder 旅行のツアーの問題
問題概要
各街に対し
- その街に行きツアーに参加
- その街に行きツアーに参加しない
- その街にそもそも行かない
が選べる.
上2個の選択には満足度が割り当てられており,得られる.
街に行かないなら満足度はその街からは得られない.
m個条件が与えられる.
x->yという条件(x<y)
xの街でツアーに参加するならyの街でもツアーに参加しないといけない
解答
燃やす埋める.
しかし,選択肢が3つあるのでうまく3つ目を組み込む.
街に行かない辺を切ると,その街に関わる条件をガン無視できることを意識すると以下のような辺の生やし方ができる.これはサンプル3
i->i'の辺を切ると,その街にそもそも行かないということ
提出
感想
最高におもしろい. 燃やす埋めるの中身を理解してないと解けなさそうなので非常に良い. 生きていてよかった
忘れたくない
はじめに
人間は,忘れる.
どうせいっぱい文字書いて詳細を書いても忘れる.
忘れるので
めもたち
Reverse Sort
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2443&lang=jp
1stepで状態がめっちゃ増える.指数的に増えるような時はスタートから何stepかだけ探索,ゴールから何stepかだけ探索して真ん中ですり合わせる.
魔法使い高橋君タイプの貪欲
沈んで上がる,だけのギザギザ線をいっぱいならべる.高く保つためには?みたいなやつ. カッコ並べるときに頻出.
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2681
期待値の線形性
一連の操作をしたとき、各操作それぞれが独立に一連の操作の中で行われる確率が求まるなら一連の操作の操作回数の期待値は各操作の確率の和
https://atcoder.jp/contests/arc114/tasks/arc114_e
木を細切れにする,直径最大値がK以下, 数え上げ
木DPで十分, dp[cur]とするときに,curを端点とする最長パスだけ持ってればよい.それ以下の部分木の別のパス持っててももうそれは今後伸びないから考えても仕方ない.
String hash
文字列の同型判定
RollingHashをセグメント木でとる. 文字に対するハッシュ値はクエリごとに計算するので,セグメント木に乗せる
https://codeforces.com/contest/985/problem/F
差が一定やつ,畳み込み
普通の畳み込み,添え字の和が一定なものを集める.
つまり一方を反転すれば差が一定なものを集めれる
包除をDP
dp[i][j] : i番目まで見てj個ほげほげ jの偶奇で最後包除.みたいな時,jの偶奇しかいらないのでjを0~kとかにする必要がない場合があって,O(NK) じゃなくてO(N)になる場合があるかもしれないしないかもしれない
任意位置のものを端に置く
問題他にもあった気がする
F - Insertion Sort
↑の問題は任意位置を左端,右端,自由位置へ移動させることが出来て,それぞれコストが定まっている.
この場合は,1, 2, ...のどこまでを左端へ,自由位置への操作で殺すかをdpで処理できるので終わる
Connect, (2N) * (2N)のDPをしなくてもよい
多分俺が見たことあまりないだけで典型 (2N)(2N)のDPをN(2N)に落とす
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2449
直線状を歩いてぶつかったら向きを変えてまた歩く
No.1608 Yet Another Ants Problem - yukicoder
ブルーフカ法
真面目に辺をはると,O(ElogV)である,最小全域木アルゴリズム. 各連結成分から最小のコストの辺を求めて辺を張ることを繰り返すとlogN回の繰り返しで求まる. 毎度頂点を全部舐めて,辺を全部舐めないで最小辺を求めれるような状況ならこれをやればよい.
xyに平行な線のみからなる多角形と点の包含判定
右側をみて,縦棒が奇数本あればin
下の問題は多角形が複数あって,何個にinしているかをクエリで答える. これはy軸小さい方からみていってセグメント木で縦棒を管理して平面操作で解ける. atcoder.jp
ソート,swap数
差が1の値同士しかswapできません -> invP[P[i]] = iを考えると,ただの転倒数
自由にswapできる -> cycleを考える
他重要かもしれない考察のとっかかり - 1回のswapを使って2つのcycleを1つにまとめれる(https://atcoder.jp/contests/arc124/submissions/24550202)