2015-10-01するめも
雑に書いていく
SRM 673 Div1 Med BearPermutations
dp1[N][cost+center] と dp2[N][cost] の二つを同時に計算する
挿入DPだが、端に挿入する時は dp1 を使って、中に挿入する時は dp2 を使って計算する。
中に挿入するときのコストは (左部分木の cost+center) + (右部分木の cost+center) + 2 になる。
SRM 594 Div1 Med FoxAndGo3
'o' と '.' に置く/置かないで最小カット
教育的
2部グラフの最大独立集合でも解けるらしい
SRM 593 Div1 Med MayTheBestPetWin
max(B(S) - A(T), B(T) - A(S)) を最小化してやればよい
1アイテムを移動させた時に差は A[i]+B[i] だけ変わるので、まずA[i]+B[i]でナップサックして作れる数字を列挙してやる
それを使って max(abs(Asum - X), abs(Bsum - X)) の最小値を探せばよい
SRM 592 Div1 Med LittleElephantAndPermutationDiv1
dp[iまでの数字で][合計がj][max側にならなかった数字がk個]=個数でDP
O(n^4)
MLEに注意
典型？DP
SRM 591 Div1 Med PyramidSequences
こういうの超苦手
とりあえず二次元グリッドに射影してみる
gcdが1の場合とそれ以外の場合で分けて考えてみる
頑張って数える
以上
SRM 590 Div1 Med XorCards
0/1 行列と見てとりあえず掃き出して上三角にする
あとはbitを上から見ていって足していく
教育的
SRM 589 Div1 Med GearsDiv1
Rが時計回り GとB が反時計回りだと仮定すると、G-B間に辺が張られないようにすればよい → 二部グラフの最大独立集合
(R, G+B), (G, R+B), (B, R+G) の3通りでチェック
SRM 588 Div1 Med KeyDungeonDiv1
開けた扉の組み合わせを固定した時、
- 手元にある鍵の総数は固定
- 白鍵は多いほどよい
- 赤と緑をどう持っておけばよいかは未確定
なので dp[開けたドア2^n][持ってる赤い鍵] = 白い鍵の最大化 でDP
SRM 587 Div1 Med TriangleXor
図を眺めると、高さが y_i の三角形が i 個あって包除されたそうな配置になっているので包除する
SRM 585 Div1 LISNumber
同じ数を区別つくものとして計算して最後に順列で割っていく
dp[i番目までの数字を並べて][非増加な部分の数がj個] の数え上げDP
新しい数を非増加でない部分に入れると、非増加な部分が増える
遷移時に何倍になるかがちょっとややこしい
典型DP…？
SRM 584 Div1 Excavation
深さ d の not found なアイテムについて、
- それを採用
- d 未満のnot foundなアイテムは採用
- d 未満のfoundなアイテムを最低1つ以上ずつ取る
- 残りをd以上のものから適当に取る
という条件を満たすものを数え上げていく
SRM 583 Div1 TurnOnLamps
フローの押し戻しのように考えると、パスは伸ばせるところまで伸ばせば良いと分かる
SRM 524 Div1 LongestSequence
累積和を取ると不等号制約になるので、ループ （a[i]<a[i]）が存在しない最大の長さをにぶたんで求める</ppp>
（にぶたんしなくても求められる）
2015-06-26ICPC2015 国内予選参加記
ICPC2015 国内予選に参加しました
メンバーは @zerokugi @yuscarlet @Gyuuto の3人です
結果は ABCDE の5完で全体5位、大学別順位3位でした
分担は
A @Gyuuto
B @Gyuuto @yuscarlet
C @Gyuuto @yuscarlet
D @zerokugi @yuscarlet
E @zerokugi
以下、各問題について考えたこと/相談したことを書いていきます
コンテスト開始
問題刷って画面の左半分にA問題を表示してGyuuto君に読んでもらいながらテンプレを打つ
A問題 AC (0:08)
とくに問題なく通る
B問題 AC (0:15)
とくに問題なく通る
D問題 WA (0:42)
読んだ感じではとりあえず瞬殺できそうではなかった
愚直にやると、各硬貨の枚数を持ってDPする感じだけど、硬貨系だし多分そこらへんは貪欲で消せるんだろう
持つ小銭の数は常に500円未満になるようにしておくだけでよい？
ってところまで考えた時点でBが通った
Cがまだらしいのでとりあえず書いてみる
持ってる小銭の額を記憶して、支払う額をp[i]～p[i]+499円まで試すDPを書いたがサンプルが通らない
テストケース(250, 250, 1000)で落ちる
所持金500円までじゃないじゃん・・・
500円以上溜まってる時は次の買い物の時に500円に錬成できるから1000円未満で良い？
書き換えるとサンプルが通ったものの投げてみるとWA
C問題 AC (1:05)
考えなおしてたら通っていた
普通の式に書き直してから構文解析ライブラリに投げる感じで解いたらしい
D問題 AC (1:21)
もう一度考察をしなおしてみる
ある店で500円をもらう為には [(p[i]+500) % 1000, (p[i]+500) % 1000 + 500)円の小銭を払わないといけない
区間が500円分なので、小銭の内訳を気にする必要が無い
そうすると、小銭は多ければ多いほど良いので、500円を得られない場合は1000円札のみで支払えばよい
これで遷移がO(1)になったので持っている小銭の量を(100*500)円まで持てるから計算量は n*n*500 で間に合う
すごい不安だったけど投げてみたら通った
E問題 AC (2:01)
EとFの概要を聞く
Fを15分ぐらい考えるも解けそうにないのでEを考える
とりあえず各スレッドごとに任意のuの位置まで薦められるので、uで区切られた区間で分割してそのうち任意の命令列を10スレッドで動かす(重複有り)感じになるなと考える
そうするとアンロックが消えるので、ある二つの命令について、今ロックしているリソース（＝命令列の今いる位置以前にあるリソース）の共通要素が空であるような位置のみ取りうるということが分かる
dp[i][j] = dp[ロック中のリソースの集合][次に取りたいリソース] = true or false;
とした時に、
if( (i & k) == 0 && (k & (1<<j) ) dp[i|k][l] |= dp[i][j] & dp[k][l];</ppp>
という感じで、二つの状態から新しい状態を生成できる
最終的に、jがiに含まれているような状態が作れた場合デッドロックを起こすことができる
2^10*10 の状態数に対して 2^10*10 の遷移を行うDPで解ける
(i & k) == 0 の条件があるので 3^10 * 10^2 にできるけど、まあicpcなので
F問題 no submit
全くとっかかりがつかなかった
以下考えたこと
・mが600までなの怪しくない？
・クラスカルベース、プリムベース両方考えたけど思いつかない
・そもそも可能か判定する方法すら分からない
・ある条件を決め打ちして最小全域木を作ることを何通りか試すみたいなことを考えるもダメ
・答えや使う辺のコストの上限を固定してやったりしてもいけそうにない
・片方の最小全域木を作る際に辺を使うか使わないかで分岐しながらスルーした本数でDP・・・連結状態を持てないのでダメ
・一本入れ替えても改善しないような全域木を考える→ごっそり入れ替えたら改善するケースが出てきそうでダメ
降参
G問題 no submit
残り1時間、Fが無理そうでHはヤバいんだろうなぁという感じだったのでGを頑張ることに
とりあえずGyuuto君に幾何ライブラリの写経をお願いしつつ解法を考える
二頂点の組み合わせを全列挙して二等分線で折って頂点数と周長を計算してmaxを取れば良いことは分かる
二等分線で多角形のカットして片方反射してやると二つの凸多角形（A, Bとする）の合成になることも分かる
頂点の数は (n + 2 - 折った後に一致する頂点数 - 多角形に内包される頂点数) になる （←これは嘘であることにあとで気づく）
AとBの共通部分（Cとする）も凸カットで求められて、それも凸多角形になる
Cに現れる辺は、「内部に隠れる」「A、B両方の辺に現れる」のどちらかなので、Aの周長+Bの周長-Cの周長で周長は求められる（多分本当）
ということで凸カットさえあれば通せそうなので書き始める（この時点で残り40分）
書き終わってあらかたバグもなくなったけどサンプルが通らない
確認してみると、折った後の頂点が重なった上で平行に辺が両側に伸びていくケース（サンプル5）で死んでいることが分かる
（丁寧に図まであるし見ておくべきだった…）
その他のケースが大丈夫かどうかは確認できていない
残り5分で書けそうな解決方法も思い浮かばず時間切れ
H問題 no submit
読めていない
2015-06-11線分アレンジメントでよく踏むバグ
2015-03-21CodeChef March Challenge 2015
苦労したので備忘録として書いておく 読む価値はあんまり無いかもしれない
Count Substrings
永続遅延Segtree（区間加算、区間和）で殴ると簡単に書ける
各iについて左端毎に「右端がi以下である有向な区間の数」をセットした Segtreeをn個作ると seg[r].query(l, r) が答えになる
（ソース見たほうが分かりやすい）
ちなみにクエリ先読みすれば永続化はいらなくなる
http://www.codechef.com/viewsolution/6453408
int T, n, k, q; char s[100005]; int main(int argc, char *argv[]){ ios::sync_with_stdio(false); scanf("%d", &T); while(T--){ scanf("%d%d%d %s", &n, &k, &q, s); vi c(2); SegTreeDynamicLazy<handler> seg(n); vector<SegTreeDynamicLazy<handler>::Node*> roots; roots.pb(seg.root); int l = 0; REP(i, n){ c[s[i]-'0'] ++; while(c[0] > k || c[1] > k) c[s[l++]-'0'] --; roots.pb(seg.update(l, i+1, 1, roots[i], 1)); } REP(i, q){ int l, r; scanf("%d%d", &l, &r); l--; printf("%lld\n", seg.query(l, r, roots[r], 1)); } SegTreeDynamicLazy<handler>::Node::allClear(); } return 0; }
Sereja and Random Array
線形合同法の方はよく見るとseedの下位16bitしか答えに影響しないので全部調べる
クエリ全部Trieに突っ込んで一気に判定するとよい
i文字目までたまたま一致する確率は 2^(-i) なので ハズレseed1個あたりの期待計算量は O(1) になる
http://www.codechef.com/viewsolution/6450115
Chef and Problems
Aiに出てくる回数が多い数字と少ない数字に分けて処理する平方分割
多い数字についてはクエリ毎に全部の数字について区間内の最左最右を調べる
少ない数字についてはクエリ先読み＋数列を左からなめながら Segtree を構築していく
http://www.codechef.com/viewsolution/6415128
Counting on a Tree
とりあえずこの問題では辺の重みを素因数分解した時に指数が2以上のものは1にしてしまっても問題ない
と、すると素因数の数は最大7個 (2*3*5*7*11*13*17=510510) になるので約数の数は最大2^7個
初期値（部分点）
各辺を重みの全ての約数の辺に拡大してやり，同じ値を持つ辺からなるグラフを作る
（辺の総数は最大 2^7*100000 個）
この時各重み毎にグラフ上の到達可能な点対数を求めて（dfsでO(E)）素因数の数の偶奇で包除すると答えの初期値が求まる
クエリによる値の更新
ある辺 e=(u, v) を a → b に変更する場合を考える
eを境にして両側へ伸びる部分木UとVに対して，dfsでuからの（vからの）全パスのgcdを求める
U×Vのペアについてgcdを取った値が
- a, bともに共通の素因数を持つ → クエリ前後ともにパスが存在する
- a のみと共通の素因数を持つ → クエリによってパスはなくなる
- b のみと共通の素因数を持つ → クエリによってパスが新しく増える
- a, bともに共通の素因数を持たない → パスは存在しないまま
なので，２個目と３個目にあたる組み合わせ数をそれぞれ求めて足して引けばクエリによる差分が求まる
（ただし Q*N 回 gcd 取るとTLEするので素因数のリストで値を管理してビット演算で gcd を取ったりして頑張って速くしないと通らなかった）
http://www.codechef.com/viewsolution/6439242
Random Number Generator
10点はkitamasa法
満点は多項式の除算とFFTを使って解くらしい
（ここからは非想定解であまり頭のよくない方法だけど，一応無理やり満点取れたので記しておく）
kitamasa法を FFT を使って速くする（※まちがい）ことを考えた結果
- 序盤の a(2m)をa(0)からa(2n-2) で表すフェイズは畳み込みするだけ
- 後半のanからa(2n-2)をa0からa(n-1)に押し戻すフェイズは畳み込み適用不可能
ここで後半部分を
- a(n+k)からa(n+2*k)をa(k)からa(n+k)に押し戻す
という処理をダブリングっぽく適用していくと log n 回の畳み込みで押し戻せる O(n^2) → O(n logn logn)
ただし，これを行うためにはa(k)をa(0)～a(n)で表したものが必要 → 前処理に O(n^2) 必要…
k = sqrt(n) として平方分割っぽく押し戻していくと O(n^1.5 logn) になるけど前処理が O(n^1.5) になる
あとは定数倍がんばったら通った（kのパラメータ職人とか、2とか4進める時はダブリングせずに1個ずつ進めるとか、 FFT の使いまわせる計算を先にやっとくとか、限界までMODは取らないとか…）
多分最終的にオーダーは O(k^1.5 logk logn) になってるはず…
2015-01-11AOJ 2559 - Minimum Spanning Tree
題意
n<=100000 頂点，m<=200000 辺のグラフが与えられる
全ての辺について、その辺を除いた時の最小全域木のコストを求めよ
解法(非想定解)
とりあえず最小全域木を求める。この時使われなかった辺(未使用辺)は答えがその最小全域木のコストになる。
次に未使用辺(u, v)を最小全域木に追加することを考えると，代わりに取り除くことができる辺は木のu-vパス上にある辺のみであることが分かる。
なので，最小全域木に使われた各辺の答えは，その辺を通るパスを繋ぐ未使用辺の中でコストが最小のものを代替とした時のコストになる。（元の最小全域木から2本以上の辺が入れ替わることはない）
これは，木に対してパスu-vに範囲更新（x = min(x, y)）ができればよいので，HL分解してSegTreeを乗せてやれば O( (n+m)log^2(n) )ぐらい（適当）で解ける
コード
※子供側の頂点が各辺に対応しており、パスu-vの更新時にLCA(u, v)を除いて更新することで辺に対するクエリを処理している
// spaghetti source struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; struct HLDecomp{ struct NodeInfo{ int idx, pos, cnt, par, heavy, depth; }; int n; vector<NodeInfo> V; vector<vi> e; HLDecomp(const vector<vi> &g, int root = 0):n(g.size()), V(n){ stack<int> st; st.push(root); V[root].depth = 0; V[root].par = -1; while(!st.empty()){ int v = st.top(); st.pop(); if(v<0){ v = ~v; if(v != root) V[V[v].par].cnt += V[v].cnt; V[v].heavy = -1; int mc = 0; FOR(u, g[v])if(*u!=V[v].par && chmax(mc, V[*u].cnt)) V[v].heavy = *u; }else{ V[v].cnt = 1; st.push(~v); FOR(u, g[v])if(*u!=V[v].par){ V[*u].par = v; V[*u].depth = V[v].depth+1; st.push(*u); } } } st.push(root); while(!st.empty()){ vi d; int v = st.top();st.pop(); int p = V[v].par; for(;v>=0;v=V[v].heavy){ FOR(u, g[v])if(*u!=V[v].par && *u!=V[v].heavy) st.push(*u); V[v].idx = e.size(); V[v].pos = d.size(); V[v].par = p; d.pb(v); } e.pb(d); } } size_t size(){return e.size();} const vi &operator[](int i) const{return e[i];} pii getPos(int v){return pii(V[v].idx, V[v].pos);} struct Path{ int idx, s, t; Path(int idx, int s, int t):idx(idx), s(s), t(t){} }; vector<tuple<int, int, int>> path(int u, int v, int onlyEdge=0){ vector<tuple<int, int, int>> res, rev; while(V[u].idx!=V[v].idx){ int pu = V[u].par; int pv = V[v].par; if((pu==-1 ? -1 : V[pu].depth) > (pv == -1 ? -1 : V[pv].depth)){ res.eb(V[u].idx, V[u].pos, 0); u = V[u].par; }else{ rev.eb(V[v].idx ,0 ,V[v].pos); v = V[v].par; } } int c = abs(V[u].pos - V[v].pos); if(!onlyEdge) res.eb(V[u].idx, V[u].pos, V[v].pos); else if(V[u].depth > V[v].depth) res.eb(V[u].idx, V[u].pos, V[v].pos + (V[v].pos < V[u].pos ? 1 : -1)); else if(V[u].depth < V[v].depth) res.eb(V[u].idx, V[u].pos + (V[u].pos < V[v].pos ? 1 : -1), V[v].pos); res.insert(res.end(), RALL(rev)); return res; } int getDepth(int v){ return V[v].depth; } }; struct handler{ typedef int val_t; handler(){} val_t def_val(){ return INF; } static val_t update(const val_t &l, const val_t &r){ return min(l, r); } static val_t update_overwrite(const val_t &l, const val_t &r){ return min(l, r); } static val_t merge(const val_t &l, const val_t &r){ return min(l, r); } }; template<typename Handler> struct SegTreeRQ{ typedef typename Handler::val_t val_t; vector<val_t> val; Handler hdl; int n; SegTreeRQ(int size):hdl(){ n=1; while(n<size) n<<=1; val=vector<val_t>(2*n, hdl.def_val()); } SegTreeRQ(const vector<val_t> &in):hdl(){ n=1; while(n<in.size()) n<<=1; val=vector<val_t>(2*n, hdl.def_val()); for(int i=n-1 + in.size()-1;i>=0;i--){ if(n-1 <= i) val[i] = in[i - (n-1)]; else val[i] = hdl.merge(val[i*2+1],val[i*2+2]); } } val_t query(int i){ i += n-1; val_t res = val[i]; while(i > 0){ i = (i-1)/2; res = hdl.merge(res, val[i]); } return res; } void update(int a,int b, val_t x,int k,int l,int r){ if(r<=a||b<=l) return; if(a<=l&&r<=b) val[k] = Handler::update(val[k], x); else{ update(a, b, x, k*2+1, l, (l+r)/2); update(a, b, x, k*2+2, (l+r)/2, r); } } void update(int a, int b, val_t x){update(a, b, x, 0, 0, n);} val_t operator[](size_t i){return query(i);} friend ostream& operator<<(ostream &os, SegTreeRQ<Handler> &t){ REP(i, t.n) os << (i ? ", " : "[") << t.query(i, i+1); return os << "]"; } }; template<class H, class S> struct SegTreeOnHLDecomp{ typedef typename H::val_t val_t; vector<S> seg; HLDecomp hld; SegTreeOnHLDecomp(const vector<vi> &g, const vector<val_t> &val, int root=0) :hld(g, root){ REP(i, hld.size()){ vector<val_t> d; const vi& nodes = hld[i]; FOR(v, nodes) d.pb(val[*v]); seg.eb(d); reverse(ALL(d)); seg.eb(d); } } void update(int u, int v, const val_t &x, int onlyEdge=1){ auto paths = hld.path(u, v, onlyEdge); FOR(p, paths){ int i, s, t;tie(i, s, t) = *p; if(s > t) swap(s, t); seg[2*i].update(s, t+1, x); seg[2*i+1].update(hld[i].size() - t - 1, hld[i].size() - s, x); } } val_t query(int v){ auto t = hld.getPos(v); return seg[2*t.first].query(t.second); } friend ostream& operator<<(ostream &os, SegTreeOnHLDecomp<H, S> &shld){ REP(i, shld.hld.n) os << (i ? ", " : "[") << shld.query(i, i); return os << "]"; } }; int n, m; int main(int argc, char *argv[]){ scanf("%d%d", &n, &m); vector<pair<pii, pii>> e; REP(i, m){ int u, v, w; scanf("%d%d%d", &u, &v, &w); u--, v--; e.eb(pii(w, i), pii(u, v)); } sort(ALL(e)); vector<vi> g(n); UnionFind uf(n); vi used(m); ll base = 0; REP(i, m){ const int u = e[i].second.first; const int v = e[i].second.second; const int w = e[i].first.first; if(used[i] = uf.unionSet(u, v)){ g[u].pb(v); g[v].pb(u); base += w; } } vector<ll> ans(m, 1ll<<55); SegTreeOnHLDecomp<handler, SegTreeRQ<handler>> treeseg(g, vi(n, INF)); REP(i, m)if(!used[i]){ const int u = e[i].second.first; const int v = e[i].second.second; const int w = e[i].first.first; ans[e[i].first.second] = base; treeseg.update(u, v, w, 1); } REP(i, m)if(used[i]){ const int u = e[i].second.first; const int v = e[i].second.second; const int w = e[i].first.first; int t = (treeseg.hld.getDepth(u) < treeseg.hld.getDepth(v)) ? v : u; t = treeseg.query(t); ans[e[i].first.second] = (t == INF) ? -1 : base - w + t; } if(accumulate(ALL(used), 1) < n) fill(ALL(ans), -1ll); REP(i, m) printf("%lld\n", ans[i]); return 0; }