AGC002
ほんとうに最下位だった
A:OK
B:OK
C:最後の一個が出来る二本があるならできるし,そうでないならできない.
D:永続UFかと思ったけど,クエリを同時ににぶたんするのにlog幅回走査する方法がある.知らなかった.
E:終了20sec後とかに通った.図形まではすぐに落とせたけどそっからがadhocすぎる・・・(あとななめが一緒って気づいてからも結構実装に戸惑った)
F:dp[i][j]=0をi個おいて,j色使った という状態に関してj色目までをどこに置くかは全て決めておいたとして全部で何通りか
挿入ではなくて,先にどこに置くか決める というタイプ始めてみた気がする(こうやって置けるものがどんどん増えていくパターンだと挿入が,"これまででこの種類はここまでに置いた"みたいな情報が必要になるので無理で,そうするとこういう発想になるしか無いっぽい)
良セットだった・・・sugimすごすぎむ
天下一プログラマーコンテスト2016 予選A
14位だけどqualifiedの中では10位以内っぽいのでギリギリセーフだった.
A:fizzbuzz
B:できるだけ上に回したほうがいいのでminにあわせる 簡単で綺麗なDPですき.
C:文字列同士を見てはじめに異なる文字しか関係ないのでそこで文字の情報にしてaよりbがはやい みたいな条件を全部持つ あとは取れるやつから貪欲に取るのでOK.(topological順序を求めるアルゴリズムにおいて,次数が0⇔取って良い なのでgreedyでいける)
D:無限に広ければ適当なdfsで根に近い方の辺の長さをクソでかくすれば出来る. あとは座標圧縮すればOK. 基本的に座標圧縮って補助的に使われるアルゴリズムだと認識していたので,こういう使い方ができるのはじめて知って面白いなあって思った.良問だと思う(さすがchokudai(作問者)).
あと普通にdfsで行か列を挿入していく方法があって,こっちは普通だけど思いつかなかったなあ(挿入順がpreorderなので,いつも(postorder)と気持ちが違って難しい)
E:まずN頂点のグラフに辺をはったと思うと,そこでの連結成分ごとに考えれば良い. 無限グラフ上で適当な頂点からdfsをする.同じ行(つまりmodNで等しい)点についたら,その周期でその連結成分(N頂点の方の)は連結になる.これを全サイクルでやればいいが,サイクル基底的な話からこれは適当なdfsで見た全ての周期のgcdを取れば良い.
コンテスト中は明示的にはサイクル基底みたいなの考えてなくて(同じことはしてたけど),無限グラフ上での連結成分(ただし,同じ行の頂点は一つしか現れない)を一個取ってくると,与えられた辺たちで横に何個ずれた連結成分を取ってるかわかるから,それのgcdをとればOK と思った.
N頂点グラフに落とせないのはダメ.
D:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} int N; vector<int> G[26]; int xs[26],ys[26]; int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}; void dfs(int v,int p,int x,int y,int dep,int di){ xs[v]=x,ys[v]=y; int d=1<<(28-dep); int ndi=0; for(int u:G[v]) if(u!=p){ if((ndi+2)%4==di) ndi++; dfs(u,v,x+dx[ndi]*d,y+dy[ndi]*d,dep+1,ndi); ndi++; } } int main(){ cin>>N; rep(i,N-1){ char a,b; cin>>a>>b; G[a-'A'].pb(b-'A'); G[b-'A'].pb(a-'A'); } dfs(0,-1,0,0,0,-1); vector<int> X,Y; rep(i,N) X.pb(xs[i]),Y.pb(ys[i]); sort(all(X));sort(all(Y)); X.erase(unique(X.begin(),X.end()),X.end());Y.erase(unique(Y.begin(),Y.end()),Y.end()); rep(i,N) xs[i]=lower_bound(all(X),xs[i])-X.begin(),ys[i]=lower_bound(all(Y),ys[i])-Y.begin(); rep(i,N) xs[i]*=2,ys[i]*=2; int H=X.size()*2-1,W=Y.size()*2-1; vector<string> ans(H,string(W,'.')); rep(i,N) ans[xs[i]][ys[i]]='A'+i; rep(v,N) for(int u:G[v]) if(v<u){ if(xs[v]==xs[u]){ int ya=ys[v],yb=ys[u]; if(ya>yb) swap(ya,yb); for(int y=ya+1;y<yb;y++) ans[xs[v]][y]='-'; }else if(ys[v]==ys[u]){ int xa=xs[v],xb=xs[u]; if(xa>xb) swap(xa,xb); for(int x=xa+1;x<xb;x++) ans[x][ys[v]]='|'; }else{ assert(0); } } cout<<H<<" "<<W<<endl; rep(i,H) cout<<ans[i]<<endl; }
E:発想がunionfindからだったのでunionfindを使っている
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} struct unionfind{ int par[100000]; int d[100000]; void init(int n) { rep(i,n) par[i]=i,d[i]=0; } int find(int x){ if(x==par[x]) return x; int r=find(par[x]); d[x]+=d[par[x]]; return par[x]=r; } void unite(int x,int y,int z){ //w[x]-w[y]=z int rx=find(x),ry=find(y); if(rx==ry) return; d[ry]=d[x]-d[y]-z; par[ry]=rx; } int diff(int x,int y){ //w[x]-w[y]=? find(x),find(y); //いる!! return d[x]-d[y]; } bool same(int x,int y) { return find(x)==find(y); } }UF; int gcd(int x,int y){ if(y==0) return abs(x); return gcd(y,x%y); } int N,M,a[100000],b[100000],c[100000]; int main(){ cin>>N>>M; rep(i,M) cin>>a[i]>>b[i]; UF.init(N); rep(i,M){ if(UF.same(a[i],b[i])){ // int d=-UF.diff(a[i],b[i])+1; // show(d); // if(ans==-1) ans=d; // else ans=gcd(ans,d); }else{ UF.unite(a[i],b[i],1); // show(a[i]); // show(b[i]); } } rep(i,N) c[i]=-1; rep(i,M){ if(UF.same(a[i],b[i])){ int d=-UF.diff(a[i],b[i])+1; if(d==0) continue; int id=UF.find(a[i]); if(c[id]==-1) c[id]=abs(d); else c[id]=gcd(c[id],d); } } long long ans=0; rep(i,N) if(UF.find(i)==i){ if(c[i]==-1){ puts("-1"); return 0; } ans+=c[i]; } cout<<ans<<endl; }
CF359
解きました.
virtualでA,B,Dの3完でした.
A:ひねりのない簡単なやるだけ.
B:すべての部分木に対して重心を一つ求める問題.
サイズと重心を持ちながら木DP.根が重心になるならOKで,そうでないなら一番大きい子の重心から上げていく.
C:どう考えてもセット内最難関(実際ACも一番少ない).Z^3の点がN個与えられる.min マンハッタン距離(v,given points) (vはZ^3の点) のminをみたすvを一つ出力せよ.
二次元だと45度回転だけど,3次元だと正八面体になるので回転で立方体になったりはしない.しかし必要な値は2^3/2=4で,a=-x+y+z,b=x-y+z,c=x+y-z,a+b+c=x+y+zの4つがある区間にある という条件が各制限になる.同じ形の制限ごとに先にまとめて,あとはちゃんと(x,y,z) in Z^3があるかどうかを判定する.まずちゃんと整数になるというのはa,b,cが同符号 と同値なので,r=0,1に対しa=2a'+rとか置いてa'の条件に変えれば良い.あとはa',b',c'を最小に設定しといて,a'+b'+c'が許す範囲で増やしていけばOK.
細かいところがかなり面倒で,うまいこと同値変形しないとなかなか難しい.細かいところまでちゃんと定式化しようとすることが必要.
D:無限に広がる二次元グリッドのN箇所が黒く塗られている.K*K正方形で中にi箇所ぬられているようなものは何個ありますか(iが正のものは有限)
平面走査*2みたいな感じ.まず縦でいつ追加,削除されるかを持って,処理して,あとは横で処理した分を縦がどのくらいに渡るかの係数をかける.横の処理も平面走査で,一つのマスは高々K回しか処理されないのでO(KNlogN)で出来る.
E:N頂点M辺の無向グラフがある.辺iは時間i以下なら使えて,使うと時間がiに変化する.場所s,時間lから場所tに時間rまでにつけるか というクエリが大量に来るのでYes/Noで答えてください.
N≤1000,M,Q≤200000
O(NM+Q)で出来ます.
最短でaからbにいつつけるかmn[a][b]を後ろから更新していく.辺m=(x,y)が繋がるとき,xからvに行けるならyからvにも行けるようになる(逆も同様) + xからyへ時刻mに着けるようになる.クエリをsでまとめておけば答えられる.
C:Submission #18750874 - Codeforces
D:Submission #18717102 - Codeforces
E:Submission #18732270 - Codeforces
CODECHEF LUNCHTIME37
これやってたらSRMレジりミスった.
LCOLLIS:やるだけ
OMWG:O(1)
SQNUMBF: 100個のlong longの積が4以上の平方数で割れるかどうか.素数p^2のみ考えれば良い.pが2つの整数にまたがっている場合は,gcdを取ればpが出てくるのでわかる.1つの整数の場合は,10^6まで全部試したら,残りが平方数になっているしか望みがないのでsqrtとって判定.
TRAVTREE:木があります.pathが順に与えられるので,それぞれ「これまでのpathのうちこのpathと交わっているのは何個」を答えてください.N,Q≤2e5くらい.
この前のRCCでも面倒要素としてあったpathの交わり系だけど,(一点でも)交わるのは3通りに場合分け出来る.
pathをa-b,c-dとしてlcaをx,yとすると,
- xがc-dに含まれる
- yがa-bに含まれる
- 上の両方(これはx=yと同値)
上に向かう途中で分岐することはないのでそれはそう.
今回はそれぞれで数え上げれば良くて,今見てるのをc-dの方とすると,
1:クエリはpathのsum,更新はpointに+1
2:クエリはpointのvalue,更新はpathに+1
3:1を使えばわかる
今回は操作に逆元があるのでEulerTourが使える.
EulerTour + LCA + segtree で二つのpathに分解してそれぞれやればOK.
ほとんどライブラリ
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} const int MAX_V=200000; const int LOGV=18; int par[MAX_V][LOGV],depth[MAX_V]; vector<int> G[MAX_V]; void dfs(int v,int p){ if(p<0) depth[v]=0; else depth[v]=depth[p]+1; par[v][0]=p; for(int u:G[v]){ if(u!=p) dfs(u,v); } } void genlca(int N){ dfs(0,-1); for(int i=1;i<LOGV;i++){ rep(v,N){ if(par[v][i-1]==-1) par[v][i]=-1; else par[v][i]=par[par[v][i-1]][i-1]; } } } int lca(int u,int v){ if(depth[u]<depth[v]){ swap(u,v); } int d=depth[u]-depth[v]; rep(i,LOGV){ if((d>>i)&1) u=par[u][i]; } if(u==v) return u; for(int i=LOGV-1;i>=0;i--){ if(par[u][i]!=par[v][i]){ u=par[u][i]; v=par[v][i]; } } return par[v][0]; } int I; int id[MAX_V*2]; bool in[MAX_V*2]; int v2id[MAX_V][2]; //[0]:in [1]:out void eulertour(int v,int p){ id[I]=v,in[I]=1,v2id[v][0]=I,I++; for(int u:G[v]) if(u!=p) eulertour(u,v); id[I]=v,in[I]=0,v2id[v][1]=I,I++; } struct segtreeRsumPadd{ static const int N=1<<19; int seg[N*2]; segtreeRsumPadd(){ rep(i,N*2) seg[i]=0; } void add(int x,int v){ x+=N; while(x){ seg[x]+=v; x/=2; } } int sum(int a,int b,int l=0,int r=N,int k=1){ if(b<=l||r<=a) return 0; if(a<=l&&r<=b) return seg[k]; return sum(a,b,l,(l+r)/2,k*2)+sum(a,b,(l+r)/2,r,k*2+1); } }sega; struct segtreePsumRadd{ static const int N=1<<19; int seg[N*2]; segtreePsumRadd(){ rep(i,N*2) seg[i]=0; } int val(int x){ x+=N; int ret=0; while(x){ ret+=seg[x]; x/=2; } return ret; } void add(int a,int b,int v,int l=0,int r=N,int k=1){ if(b<=l||r<=a) return; if(a<=l&&r<=b){seg[k]+=v;return;} add(a,b,v,l,(l+r)/2,k*2),add(a,b,v,(l+r)/2,r,k*2+1); } }segb; int main(){ int N,Q; cin>>N; rep(i,N-1){ int a,b; scanf("%d%d",&a,&b); a--,b--; G[a].pb(b); G[b].pb(a); } genlca(N); eulertour(0,-1); cin>>Q; rep(tt,Q){ int a,b; scanf("%d%d",&a,&b); a--,b--; int w=lca(a,b); int A=sega.sum(v2id[w][0],v2id[a][0]+1); int B=sega.sum(v2id[w][0],v2id[b][0]+1); int C=sega.sum(v2id[w][0],v2id[w][0]+1); int D=segb.val(v2id[w][0])-segb.val(v2id[w][1]); // show(A); // show(B); // show(C); // show(D); int ret=A+B+D-C*2; printf("%d\n",ret); sega.add(v2id[w][0],1); sega.add(v2id[w][1],-1); segb.add(v2id[w][0],v2id[a][0]+1,1); segb.add(v2id[w][0],v2id[b][0]+1,1); segb.add(v2id[w][0],v2id[w][0]+1,-1); } }
ARC056
最近ブログ書いてなかったので備忘録的に書いておこう
かなり反省した。
A:書いてそのまま出したら最後K個買ったほうが安いのを忘れていてWA
B:割とすんなり後ろからunionfindが思いつけてよかった.(xに行くとき,x未満は全て埋まっているとして良い.(a(<x)が埋まってないとしたらそもそもsからaには辿りつけないのでsからxに行く時にaが埋まってようが埋まってまいが関係ない) ので,逆からやると使える辺が増えていくunionfind)
C:慣れていれば思考要素は0.部分集合を列挙するbit演算を使う(0を入れないように注意)
D:1時間以上余ってたのに解けなかった・・・
まず貰うDPを考えます.dp[i]=iで飲んだ直後の嬉しみの最大値 とすると,dp[i] = max dp[j]+cost(j,i) for j<i となります,where cost(j,i)=jで飲んだ次にiで飲んだ時の増えるうれしみ.
iを増やした時のcost(j,i)の変わり方は,各酒ごとに注がれる時間が来たら区間addで更新 とできるので,区間maxとaddの出来るstarryskytreeを使えばOK.
dpの更新はsegtreeでできるなあ と思っていたのに配るDPしか頭になくて解けなかった.
冷静に考えてオーダーが落ちるとしたらどこかの処理まとめるしかなくて,くばるのが無理なら貰うしかないですね.
というかcost(j,i)を得られるsegtreeとその更新までは考えてたんだからあとはmaxとるだけなんだけどなあ・・・
今度からちゃんと貰うDPを考えよう,というか閉じた式で書こうとすると貰うDPになって,閉じた式で書けるならその形が嬉しいことが多いから,はい,書きましょう.
コンテスト後に書いたD なぜか2000msピッタリでACだったんだけどこれ結構危険じゃないですか(そんなに定数倍遅い方でもないと思うんだけど)
Submission #780932 - AtCoder Regular Contest 056 | AtCoder
まあscanfにしたら速くなるかもだけど
ICPC国内予選2016
Sleep 18000 (wafrelka,wo,sigma)で出ていました.
チーム戦とはいえはじめてコンテストで一位取った気がするので嬉しいです.
A:例年より問題文も読みやすくて簡単だった
B:wafrelkaがやった
C:woがやった
D:DP
E:いつもの少し面倒なdfs はじめいろいろ間違ってたけどwoにデバグしてもらった
F:Eやってる間にいつの間にかwafrelkaが解いてた
G:Fやってる間にwoと考えてたけど難しかった
H:woに解けたからやってって言われてやったら解けた.(フローでやった)
Hの最小流量がある辺のフローは蟻本に誤植があることで有名なトピックなんですが,実は最新のやつだとちゃんと直されていたらしい(うちは考えてそれっぽいのを出した)
Gはまだちゃんと考えてないんですが割と自然っぽい.(20^2で1つを2つにする と 円を書いて区間を考える みたいなのは両方考えたんだけどちょっと考えが足りなかった)
Hは貪欲解があるらしくてまだ理解してないんですが,SRMのPieOrDolphin(TopCoder Statistics - Problem Statement)に似ているっぽい(問題自体は違う(こっちはminimize sum abs(indeg-outdeg))けど,解法は全く一緒な気がする)
アジアも頑張りたい
ARC055
writerでした。
AtCoDeerくんというシカが主人公です。公式キャラに定着させたい・・・
AtCoderのマスコットキャラクターのAtCoDeerくんというのを思いついたので自由に使っていいですよ(ロゴの横にいるやつをシカということにしてこいつらをマスコットキャラクターにしよう) pic.twitter.com/AoUVGFXHqJ
— 世界一頭が悪い (@sigma425) 2016年1月23日
ちなみにシカではないらしい
A:数え上げ
やるだけ。けっこうすき
B:せんべい
案外難しかったみたいです。
dp[i][j][k] = i枚見てj枚食べていて,"ここまでのmaxを食べているか"=k です。
Nを食べたかどうか という絶対的なものではなく,これまでのmaxを食べたかどうか という相対的な気持ちになると解きやすいと思います。
ちなみにK=1の時はN ->∞ で 1/eに近づきます。
ちなみにN,K<=1e6でも解けます。
BのN,K<=1e6解法
— 世界一頭が悪い (@sigma425) 2016年6月3日
Kがデカい時は1を出力すればOKです
「これまでの最大」以外は食べる意味が無いです。この個数の期待値は1 + 1/2 +...1/N でlogNくらいです
なのでK >> log N なら十分1に近づきます(正確にはちゃんとi個表れるかどうかで計算)
C:ABCAC
名前的にABCかと思ったんですがどう考えてもABCには出せないですね・・・
ABC/ACの切れ目を決め打つのが良い選択です。
こうするとN^2では解けて、速くするにはSA + lcp + RMQ もしくは SA + ローリングハッシュ + にぶたん もしくはZ-algorithm というもの(
文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
を参照) を使うと良いです。
はじめはYes/No問題でしたがO(N^2)が爆速になってしまったので数え上げになりました。
ちなみに元ネタは解説でりんごさんが言っていた「たかいたい」です。
D:隠された等差数列
SRM div1hardのつもりの問題でした。
発想自体は上位陣にはそんなに難しくないと思いますが、細かい部分がかなり難しかったみたいです。
発想:とりあえず与えられた桁が1桁目になるように10^Xで割っておきます.すると整数部分がわかるので、条件が ほげ<=A+B*i<ほげ+1 の形になります。これを二次元平面に落とすと、縦の線分たちをとおるような直線 という条件になります。
あとは傾きの範囲を求める(有理数を推奨しますがdoubleでも通るっぽい(通らないやり方もあるのかもしれません))のですが、これは先に上下の条件たちの必要なものだけを考えて凸にしておくと簡単に求まるようになります。
あとは見てるのは何桁目だったかを1から探索すれば解けます。
答えはO(N^2)くらいになります.
900.....001 というケースを試してみてください。(図に書くと傾きの条件がかなり厳しいことがわかります)
結構テストケースは強いです(例えば,傾きが10^x/hoge みたいなのは結構条件が厳しくなります)
元ネタですが、餃子屋さんのメニューで、
餃子1個 1|
餃子2個 3|ここが隠れている
餃子3個 4|
餃子4個 6|
みたいに上の桁だけが見えてるのを見て思いつきました。
まとめ
難しかったっぽいですが、良い問題が揃ったと思います。参加or問題を見てくださった方々ありがとうございます。
