PCK 2015 予選
9AC1WAでした。8間に合わなくて速度不足を痛感。本選までもっと実装力も発想力も鍛えます。
1~7を自分が解いて9をeyさんが解いて10を二人で解きました(eyさんが最初に解いたがWAが出て自分がデバッグした)
8ほぼ書き終わってたのに間に合わなくて辛い(TrieでやるとMLEするらしいのでどの道通せてなかったかも)
おそらく4位。去年より順位下がってつらい。
1 やるだけ
int main() { int p,m,c; cin >> p >> m >> c; cout << p+m+c << endl; return 0; }
2 やるだけ
int h1,h2; int k1,k2; int a,b,c,d; int main() { scanf("%d %d",&h1,&h2); scanf("%d %d",&k1,&k2); scanf("%d %d %d %d",&a,&b,&c,&d); int h = 0,k = 0; h = h1*a+h2*b+(h1/10)*c+(h2/20)*d; k = k1*a+k2*b+(k1/10)*c+(k2/20)*d; if(h>k)printf("hiroshi\n"); else if(k>h)printf("kenjiro\n"); else printf("even\n"); return 0; }
3 やるだけ
int D,L; int main() { scanf("%d %d",&D,&L); printf("%d\n",(D/L)+(D%L)); return 0; }
4 やるだけ
int N; int a[105]; int main() { memset(a,0,sizeof(a)); scanf("%d",&N); for(int i=0;i<3;i++) { int k; scanf("%d",&k); for(int j=0;j<k;j++) { int val; scanf("%d",&val); val--; a[val]|=(1<<i); } } int ans = 0; for(int i=0;i<N;i++) { //printf("%d %d\n",i,a[i]); if(a[i]==7||a[i]==6||a[i]==4)ans++; } printf("%d\n",ans); return 0; }
5 やるだけ
int N; int p[105]; int imos[105]; int main() { scanf("%d",&N); for(int i=0;i<N;i++)scanf("%d",&p[i]); for(int i=0;i<N;i++)imos[p[i]]++; for(int i=100;i>0;i--)imos[i-1]+=imos[i]; for(int i=100;i>=0;i--)if(imos[i]>=i) { printf("%d\n",i); return 0; } return 0; }
6 やるだけ
int C,N; char ch[1010][1010]; int f[1010][1010]; bool ok[1010][1010]; int bad = 0; bool check(int x,int y) { if(f[x][y]==f[x][N-1-y]&&f[x][y]==f[N-1-x][y]&&f[x][y]==f[N-1-x][N-1-y])return true; return false; } int ans = 0; int main() { scanf("%d %d",&C,&N); for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin >> ch[i][j]; } } for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(ch[i][j]=='0')f[i][j]=0; else f[i][j]=1; } } int M = N/2; for(int i=0;i<M;i++) { for(int j=0;j<M;j++) { if(check(i,j))ok[i][j]=true; else { ok[i][j]=false; bad++; } } } if(bad==0)ans++; for(int i=0;i<C-1;i++) { int k; scanf("%d",&k); for(int j=0;j<k;j++) { int x,y; scanf("%d %d",&x,&y); x--;y--; f[x][y]^=1; if(x>=M)x=N-1-x; if(y>=M)y=N-1-y; bool d = check(x,y); if(d!=ok[x][y]) { if(d)bad--; else bad++; } ok[x][y]=d; } if(bad==0)ans++; } printf("%d\n",ans); return 0; }
7 UnionFind使うだけ
const int SIZE = 250000; struct UnionFind { int par[SIZE]; void init(int n) { for(int i=0;i<n;i++) { par[i] = i; } } int find(int x) { if(par[x] == x)return x; else return par[x] = find(par[x]); } void unite(int x,int y) { x = find(x); y = find(y); if(x==y)return; if(x > y)par[y] = x; else par[x] = y; } bool same(int x,int y) { return find(x) == find(y); } }uf; int N,M,K; int main() { scanf("%d %d %d",&N,&M,&K); //0 N-1 N N+M-1 uf.init(N+M); for(int i=0;i<K;i++) { int type; int a,b,c,x; scanf("%d",&type); if(type==1) { scanf("%d %d",&a,&b); a--;b--; a = uf.find(a); b = uf.find(b); //cout << a << ' ' << b << endl; if(a>=N&&b>=N&&a!=b) { printf("%d\n",i+1); return 0; } uf.unite(a,b); } else { scanf("%d %d",&c,&x); c--;x--; c = uf.find(c); //cout << c << ' ' << x+N << endl; if(c>=N&&c!=x+N) { printf("%d\n",i+1); return 0; } uf.unite(c,x+N); } } printf("0\n"); return 0; }
8 Trieで数えるだけだと思ったけどロリハじゃないと通らないらしい
9 二分探索
#define INF 100000000 using namespace std; typedef pair<double,double> P; long long x[100000]; long long r[100000]; double min(double a,double b){return a<b?a:b;} double max(double a,double b){return a>b?a:b;} P cross(P a,P b){ return P(max(a.first,b.first),min(a.second,b.second)); } bool solve(double w,int n){ P seg=P(-INF,INF); for(int i=0;i<n;i++){ if(w>r[i])return false; double left=x[i]-sqrt(r[i]*r[i]-w*w); double right=x[i]+sqrt(r[i]*r[i]-w*w); P cseg=cross(seg,P(left,right)); if(cseg.first>cseg.second)return false; else seg=cseg; } return true; } int main(){ int n,i; scanf("%d",&n); for(i=0;i<n;i++)scanf("%lld %lld",&x[i],&r[i]); double bottom=0,top=1000001; for(int bi=0;bi<40;bi++){ double mid=(bottom+top)/2; if(solve(mid,n))bottom=mid; else top=mid; } printf("%.12lf\n",bottom); return 0; }
10 JOI春のオリエンテーリングみたいにトポソして片方先に行かせながらDP
#define INF 1000000000000LL typedef pair<int,int> P; vector<P> re[1000]; int cost1[2000]; int cost2[2000]; bool used[1000]; vector<int> ord; long long dp[1000][1000]; int depth[1000]; long long min(long long a,long long b){return a<b?a:b;} void dfs(int v){ used[v]=true; for(int i=0;i<re[v].size();i++){ int u=re[v][i].first; if(!used[u])dfs(u); } ord.push_back(v); } int main(){ int n,m,i,j,k,l; scanf("%d %d",&n,&m); for(i=0;i<m;i++){ int a,b; scanf("%d %d %d %d",&a,&b,&cost1[i],&cost2[i]); a--;b--; re[b].push_back(P(a,i)); } for(i=0;i<n;i++)used[i]=false; dfs(n-1); for(i=0;i<n;i++)for(j=0;j<n;j++)dp[i][j]=INF; dp[ord[0]][ord[0]]=0; for(i=0;i<n;i++)depth[ord[i]]=i; for(i=0;i<n;i++){ for(j=i;j<n;j++){ int u=ord[i]; int v=ord[j]; if(u!=v){ for(k=0;k<re[v].size();k++){ int w=re[v][k].first; int e=re[v][k].second; if(depth[u]<=depth[w])dp[u][v]=min(dp[u][v],dp[u][w]+cost1[e]); else dp[u][v]=min(dp[u][v],dp[w][u]+cost1[e]); } } else{ for(k=0;k<re[v].size();k++){ for(l=0;l<re[v].size();l++){ int w1=re[v][k].first; int e1=re[v][k].second; int w2=re[v][l].first; int e2=re[v][l].second; if(e1==e2)dp[v][v]=min(dp[v][v],dp[w1][w1]+cost1[e1]+cost2[e1]); else{ if(depth[w1]<=depth[w2])dp[v][v]=min(dp[v][v],dp[w1][w2]+cost1[e1]+cost1[e2]); else dp[v][v]=min(dp[v][v],dp[w2][w1]+cost1[e1]+cost1[e2]); } } } } } } printf("%lld\n",dp[n-1][n-1]); return 0; }
AOJ 2436 Card
だいぶ想定解まで迫ったもののO(N^4)から落とせず、解説を見てしまった。
桁数でまとめる発想がなかったのは頭悪すぎたので反省
typedef long long ll; #define MOD 1000000007 const int SIZE = 100100; ll inv[SIZE+10],fac[SIZE+10],facinv[SIZE+10]; ll Pow[1010],kai[210]; ll val[210]; ll nCr(int n,int r) { if(n<r)return -1; if(n<0||r<0)return -1; return ((fac[n]*facinv[r]%MOD)*facinv[n-r])%MOD; } ll func(int n) { ll ret = 0ll; for(int i=0;i<=n;i++)ret = (ret+(nCr(n,i)*kai[i])%MOD)%MOD; return ret; } void init() { fac[0]=1ll; for(int i=1;i<=SIZE;i++)fac[i]=(fac[i-1]*i)%MOD; inv[1]=1ll; for(int i=2;i<=SIZE;i++)inv[i]=((-(MOD/i)*inv[MOD%i])%MOD+MOD)%MOD; facinv[0]=1ll; for(int i=1;i<=SIZE;i++)facinv[i]=(facinv[i-1]*inv[i])%MOD; Pow[0]=1ll; for(int i=0;i<1000;i++)Pow[i+1]=(Pow[i]*10ll)%MOD; kai[0]=1ll; for(int i=1;i<=200;i++)kai[i]=(kai[i-1]*i)%MOD; for(int i=0;i<=200;i++)val[i]=func(i); } int cnt_digit(ll x) { if(x==0ll)return 1; int ret = 0; while(x){ret++;x/=10ll;} return ret; } ll dp[210][1010]; int n; ll a[210]; int dig[210]; ll digit_sum[5]; int del[5]; int zero=-1; int N; void culc_dp(int unuse) { memset(dp,0,sizeof(dp)); dp[0][0]=1ll; for(int i=0;i<N;i++) { if(i==unuse)continue; for(int j=i;j>=0;j--) { for(int k=0;k<=j*4;k++) { if(dp[j][k]==0)continue; dp[j+1][k+dig[i]]+=dp[j][k]; dp[j+1][k+dig[i]]%=MOD; } } } } ll solve() { ll ans = 0ll; for(int d=1;d<=4;d++) { if(del[d]==-1)continue; culc_dp(del[d]); for(int i=0;i<N;i++) { for(int j=0;j<=4*N;j++) { if(dp[i][j]==0)continue; ans += (((((((val[N-i-1]*kai[i])%MOD)*digit_sum[d])%MOD)*dp[i][j])%MOD)*Pow[j])%MOD; ans %= MOD; } } } return ans; } int main() { init(); memset(del,-1,sizeof(del)); scanf("%d",&n); N=n; for(int i=0;i<n;i++)scanf("%lld",&a[i]); for(int i=0;i<n;i++) { dig[i]=cnt_digit(a[i]); digit_sum[dig[i]]+=a[i]; del[dig[i]]=i; if(a[i]==0)zero=i; } ll ans = solve(); //cout << solve() << ' '; if(zero!=-1) { swap(a[zero],a[n-1]); N--; memset(del,-1,sizeof(del)); memset(digit_sum,0,sizeof(digit_sum)); for(int i=0;i<N;i++) { dig[i]=cnt_digit(a[i]); digit_sum[dig[i]]+=a[i]; del[dig[i]]=i; } ans -= solve(); //cout << solve() << endl; ans = ((ans%MOD)+MOD)%MOD; } printf("%lld\n",ans); return 0; }
AOJ 2256 Divide the Cake
ケーキの端にイチゴが乗ってる時(sample1)の対処をメモ。
len(Y)は片方を(0,Y)に固定したときに等分できる右側の部分の長さを返す関数。
ただ、(0,Y)にイチゴがあると色々面倒なので+eps,-epsの２つに分けて処理した。
誤差怖かったけど通ったので良かった(小並感)
int W,H,N; int x[210],y[210]; double len(double Y) { vector<double> v; for(int i=0;i<2*N;i++)v.pb(atan2(y[i]-Y,x[i])); sort(all(v)); double low = tan(v[N-1])*(double)W + Y; double high = tan(v[N])*(double)W + Y; low = max(low,0.0); low = min(low,(double)H); high = max(high,0.0); high = min(high,(double)H); return high-low; } int main() { while(1) { scanf("%d %d %d",&W,&H,&N); if(W==0&&H==0&&N==0)break; for(int i=0;i<N*2;i++)scanf("%d %d",&x[i],&y[i]); vector<P> v; for(int i=0;i<N*2;i++)v.pb(P(x[i],y[i])); v.pb(P(W,0));v.pb(P(W,H)); vector<double> border; for(int i=0;i<v.size();i++) { for(int j=i+1;j<v.size();j++) { if(v[i].fi==v[j].fi)continue; double res = (double)v[i].sec-(double)v[i].fi*(double)(v[j].sec-v[i].sec)/(double)(v[j].fi-v[i].fi); if(0.0<=res&&res<=(double)H)border.pb(res); } } border.pb(0.0);border.pb(H); sort(all(border)); border.erase(unique(all(border)),border.end()); double ans = 0.0; for(int i=0;i<border.size()-1;i++)ans+=(len(border[i]+eps)+len(border[i+1]-eps))/2.0*(border[i+1]-border[i]); ans /= (double)H; ans /= (double)H; printf("%.12f\n",ans); } return 0; }
AOJ 2313 Box Witch
個人的にハマるポイントが山ほどあったので戒めのメモ。
まず、自分のライブラリはverify済でも信用してはいけません
(まぁこれはverifyした後にちょっとわかり易くしようと書き換えた自分が悪いのでなんとも言えませんが)
(でもまさかadd_edgeが間違ってるとは…)
次に、dfsする前に絶対memset忘れないように!!
(これに大体5時間溶かしました)
そして解法のことですが、辺削除の時どっち向きに流れているか注意!!
(なぜかずっとe.cap>0なら使われててそうでなければ使われてないという判定をしていました)
自分の思考ガバガバすぎなので反省します…
const int MAX_V=100100; struct edge { int to,cap,rev; edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){} }; vector<edge> G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap) { edge new_edge1(to,cap,G[to].size()); G[from].pb(new_edge1); edge new_edge2(from,cap,G[from].size()-1); G[to].pb(new_edge2); } int dfs(int v,int t,int f) { if(v==t)return f; used[v]=true; for(int i=0;i<G[v].size();i++) { edge &e=G[v][i]; if(!used[e.to]&&e.cap>0) { int d=dfs(e.to,t,min(f,e.cap)); if(d>0) { e.cap-=d; G[e.to][e.rev].cap+=d; return d; } } } return 0; } int flow=0; int N; int max_flow(int s,int t) { for(;;) { memset(used,0,sizeof(used)); int f=dfs(s,t,INF); if(f==0)return flow; flow+=f; } } int ex[505][505]; int E,Q; int ind(int A,int B){for(int i=0;i<G[A].size();i++)if(G[A][i].to==B)return i;} void increase(int A,int B) { int id = ind(A,B); edge &e = G[A][id]; e.cap++; } int decrease(int A,int B) { int id = ind(A,B); edge &e = G[A][id]; int ret = e.cap; e.cap=0; return ret; } int up_query(int A,int B) { increase(A,B); increase(B,A); return max_flow(0,N-1); } int down_query(int A,int B) { int c = decrease(A,B); decrease(B,A); if(c==2)swap(A,B); if(c==1)return flow; else { memset(used,0,sizeof(used)); if(dfs(A,B,1)>0)return flow; memset(used,0,sizeof(used)); dfs(N-1,B,1); memset(used,0,sizeof(used)); dfs(A,0,1); flow--; return flow; } } int main() { scanf("%d %d %d",&N,&E,&Q); for(int i=0;i<E;i++) { int F,T; scanf("%d %d",&F,&T); F--;T--; ex[F][T]=1; ex[T][F]=1; } for(int i=0;i<N;i++) { for(int j=i+1;j<N;j++) { add_edge(i,j,ex[i][j]); } } max_flow(0,N-1); for(int i=0;i<Q;i++) { int M,A,B; scanf("%d %d %d",&M,&A,&B); A--;B--; if(M==1)printf("%d\n",up_query(A,B)); else printf("%d\n",down_query(A,B)); } }
AOJ 2439 Hakone
良問DPとして有名な箱根駅伝。結構考えましたがわからず解説を読んでしまいました。
JAGの解説が少しわかりにくかったのでここにまとめておきます。
順位表の'-'は確定するので無視します。
現在の中継地点の順位表を1位から順に見ていって、前の中継地点での順位表を上から埋めていく感じです。
DP[i][j]:=(i位まででj個未確定で放置)の場合の数
というテーブルを考えます。
初期化はdp[0][0]=1で求める値はdp[n][0]です
dp[i][j]からの状態遷移は、
(i)i+1位が'D'の時
1~iで開いてる所(すなわちj個)にi+1位のやつを入れるのでj通り。dp[i+1][j]+=dp[i][j]*j
上とあわせてi+1位のところに放置してたやつ(すなわちj個)を入れるのでj通り。dp[i+1][j-1]+=dp[i][j]*j*j
(ii)i+1位が'U'の時
i+1位のところに放置してたやつ(すなわちj個)を入れるのでj通り。dp[i+1][j]+=dp[i][j]*j
完全に放置。dp[i+1][j+1]+=dp[i][j]
O(N^2)ですが、想定解は未確定の数と放置してたやつ(両者は常に等しい)を分けてO(N^3)のようです
このDPが本当に重複なく数えられているかはdp[0][0]からdp[n][0]までのパスと一対一に対応してることを考えるとわかると思います。
典型と言われるのもわかるような気がします。これの類題は絶対落とさないようにしていく所存です
#include <cstdio> #include <iostream> using namespace std; typedef long long ll; #define MOD 1000000007 ll dp[300][300]; int n; char c[300]; int main() { scanf("%d",&n); for(int i=0;i<n;i++)cin >> c[i]; dp[0][0]=1ll; for(int i=0;i<n;i++) { if(c[i]=='-')for(int j=0;j<=n;j++)dp[i+1][j]=dp[i][j]; if(c[i]=='D') { for(int j=0;j<=i;j++) { if(j>0)dp[i+1][j-1] = (dp[i+1][j-1]+(((dp[i][j]*j)%MOD)*j%MOD))%MOD; dp[i+1][j] = (dp[i+1][j]+((dp[i][j]*j)%MOD))%MOD; } } if(c[i]=='U') { for(int j=0;j<=i;j++) { dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%MOD; dp[i+1][j] = (dp[i+1][j]+((dp[i][j]*j)%MOD))%MOD; } } } printf("%lld\n",dp[n][0]); return 0; }
閉路の偶奇
グラフの閉路を検出するのはDFSなりベルマンフォードなりで適当に出来ますよね。
今日奇数長の閉路の検出が出来ずに困ってしまったのでメモ。
全然今まで気付かなかったのですが
「偶数長の閉路しかない⇔2部グラフ」
です。あとはこれより、2部グラフかどうかさえ判定できればいいです。
これは簡単ですね。
(追記)多重辺、ループのない時です
Counting Sort
ちょいちょい勉強したことでも書き留めておこうと思います。
Counting Sortというのを知りました。
sortなんてquick sortとmerge sortだけ知ってりゃ十分やとか思ってたんやけど、CFでこれを使う問題が解けんくて悔しかったから書いときます。
この方法は数列とかのソートより、アルファベットみたいに種類に限りがあるものに対するソートに向いてるみたいです。
abracadabraをソートする時はa,b,c,d,rの数を数えて、それぞれ5,2,1,1,2なのでaaaaabbcdrrとするという感じです。
要するに数えたら後は並べるだけ。ってことです。
数える部分もsortする部分も(連続区間なので)segtreeを使って高速化できる場合があります。
