2015-02-09
■ JOI 2015本選 参加記
(2/4) ノロウイルスに感染したと思わしき症状が現れる
(2/6) 参加が危ぶまれたが、何とか受けさせてもらうことが出来た。
(2/7) 体調が悪いのでプラクティスのみ参加して一旦ホテルに帰る。
(2/8) 朝オリセンに行く。各位にあって少し話す。
〜競技〜
1. 易化しすぎでしょって思ったけどそれはこれが知識ゲーだからなのであったの巻
#include#include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define fi first #define sc second typedef long long ll; int n,m; int a[100005],r[100005]; int x[100005],y[100005],z[100005]; int main() { scanf("%d %d",&n,&m); for(int i=0;i<m;i++) { scanf("%d",&a[i]); } for(int i=1;i<n;i++) { scanf("%d%d%d",&x[i],&y[i],&z[i]); } for(int i=1;i<m;i++) { int x = a[i-1]; int y = a[i]; if(x>y) swap(x,y); y--; r[x]++; r[y+1]--; } for(int i=2;i<n;i++) { r[i] += r[i-1]; } ll res = 0; for(int i=1;i<n;i++) { ll s = 1LL*r[i]*x[i]; ll t = 1LL*z[i]+1LL*r[i]*y[i]; res += min(s,t); } printf("%lld\n",res); }
>>N <= 2000 <<
どう見ても状態数O(N^2)、遷移O(1)なのに勘違いして時間を食ってしまった。先に3に行く。
3. さすがに人を舐め過ぎなんだよなぁ....
#include#include #include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define fi first #define sc second #define INF 10000000000000LL typedef long long ll; typedef pair<int,ll> P; typedef pair<pair<int,int>,ll> PP; typedef pair<ll,int> Q; int n,m; vector
edge[100005]; vector,greater
> que; fill(d,d+100005,INF); d[1] = 0; que.push(mp(0,1)); while(!que.empty()) { Q q = que.top(); que.pop(); if(q.fi != d[q.sc]) continue; for(int i=0;i<edge[q.sc].size();i++) { int v = edge[q.sc][i].fi; ll ad = edge[q.sc][i].sc; if(d[v] > q.fi+ad) { d[v] = q.fi+ad; que.push(mp(d[v],v)); } } } for(int i=0;i<a.size();i++) { int x = a[i].fi.fi; int y = a[i].fi.sc; ll ad = a[i].sc; ll ke = max(d[x],d[y]); ma[ke] += ad; //cout << ke << " " << ad << " " << x << " " << y << endl; } res = sum; for(map<ll,ll>::iterator it = ma.begin();it != ma.end();++it) { sum -= it->sc; res = min(res,sum + c*it->fi); } printf("%lld\n",res); }
2(再). 戻って見るとクソであることに気づく。
#include#include #include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define fi first #define sc second #define INF 10000000000000LL typedef long long ll; typedef pair<int,int> P; int n; ll a[2005]; ll dp[2005][2005]; int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lld",&a[i]); queue
que; for(int i=0;i<2005;i++) for(int j=0;j<2005;j++) dp[i][j] = -INF; for(int i=0;i<n;i++) { dp[i][i] = a[i]; que.push(mp(i,i)); } ll res = 0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int lb = j; int ub = (j+i)%n; res = max(res,dp[lb][ub]); if(i==n-1) continue; if(i%2==0) { if(a[(lb+n-1)%n] > a[(ub+1)%n]) { dp[(lb+n-1)%n][ub] = max(dp[(lb+n-1)%n][ub],dp[lb][ub]); } else { dp[lb][(ub+1)%n] = max(dp[lb][(ub+1)%n],dp[lb][ub]); } } else { dp[(lb+n-1)%n][ub] = max(dp[(lb+n-1)%n][ub],dp[lb][ub]+a[(lb+n-1)%n]); dp[lb][(ub+1)%n] = max(dp[lb][(ub+1)%n],dp[lb][ub]+a[(ub+1)%n]); } } } printf("%lld\n",res); }
4.
見て真面目に考えるが解けず。1年前からなんも成長してねぇな＾〜となって絶望。
さすがににぶたんは考えるので24点は自明だなぁと思って通す。
#include#include #include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define fi first #define sc second #define INF 10000000000000LL typedef long long ll; int main() { int n,m; scanf("%d%d",&n,&m); if(n > 20) return 0; int x[20],y[20]; bool q[20]={}; vector<int>v; for(int i=0;i<m;i++) { cin >> x[i] >> y[i]; v.pb(x[i]); q[y[i]] = true; } vector<int>s; for(int i=1;i<=n;i++) if(!q[i]) s.pb(i); for(int i=m;i<n;i++) { cin >> x[i]; v.pb(x[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=v.size()-1;i>=0;i--) { int bit = 0; for(int j=m;j<n;j++) if(x[j] >= v[i]) bit++; int a[50]; for(int j=0;j<m;j++) a[y[j]] = (x[j] >= v[i]); for(int j=0;j<(1<<(n-m));j++) { if(__builtin_popcount(j) != bit) continue; for(int k=0;k<s.size();k++) a[s[k]] = (((j>>k)&1)); int lb=1,ub=n; while(ub-lb>1) { int d = a[lb]+a[lb+1]+a[lb+2]; if(d>=2) a[ub+1] = 1; else a[ub+1] = 0; lb+=3; ub++; } if(a[ub] == 1) { printf("%d\n",v[i]); return 0; } } } }
5. どうみてもこれクソムズだよなぁ...(この判断が致命傷であった) 20点解法だけ書こう.....ということで実装する。
#include#include #include #include #include #include #include #include using namespace std; #define pb push_back #define mp make_pair #define fi first #define sc second #define INF 10000000000000LL typedef long long ll; typedef pair<int,int> P; int n,m,l,p; P za[100005]; int rui[4005][4005],s[4005][4005]; ll res; ll zan[12]; int rec(int a,int b,int c,int d) { return rui[b][d] - rui[a-1][d] - rui[b][c-1] + rui[a-1][c-1]; } int cnt(int a,int b,int c,int d) { return rec(a,b,c,d)-rec(a+1,b-1,c+1,d-1); } void solve() { int res = 0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { for(int k=l;k<=min(n+1-i,m+1-j);k++) { if(!cnt(i,i+k-1,j,j+k-1)) res++; } } } cout << res << endl; } int main() { scanf("%d%d%d%d",&n,&m,&l,&p); for(int i=0;i<p;i++) { scanf("%d%d",&za[i].fi,&za[i].sc); s[za[i].fi][za[i].sc] = 1; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) rui[i][j] = rui[i-1][j]+rui[i][j-1]-rui[i-1][j-1]+s[i][j]; if(p>10 && n>500) return 0; else if(n <= 500) {solve(); return 0;} for(int i=l;i<=min(n,m);i++) { res += 1LL*(n-i+1)*(m-i+1); } for(int ii=0;ii<p;ii++) { int x = za[ii].fi; int y = za[ii].sc; for(int i=1;i<=n;i++) { for(int j=i+l-1;j<=n;j++) { if(!(i<=x && x<=j)) continue; if(y+i-j < 1) continue; int a = cnt(i,j,y+i-j,y); zan[a]++; } } for(int i=1;i<=m;i++) { for(int j=i+l-1;j<=m;j++) { if(!(i<=y && y<j)) continue; if(x+j-i > n) continue; int a = cnt(x,x+j-i,i,j); zan[a]++; } } for(int i=1;i<=n;i++) { for(int j=i+l-1;j<=n;j++) { if(!(i continue; if(y+j-i > m) continue; int a = cnt(i,j,y,y+j-i); zan[a]++; } } for(int i=1;i<=m;i++) { for(int j=i+l-1;j<=m;j++) { if(!(i continue; if(x+i-j < 1) continue; int a = cnt(x+i-j,x,i,j); zan[a]++; } } } for(int i=1;i<=p;i++) res -= (zan[i]/i); printf("%lld\n",res); }
4(再). 何度見てもわからずなので諦める。
5(再). 満点解法を真面目に考えているとクソであることがわかる。この時点で1時間はあったのだが3ヶ月以上引退してる人は書き終わらなかったよ....
終了。100+100+100+24+20 = 344 (おそらく6位) (クソクソ & クソ)
5番が解析が始まると同時に通る。(終了30秒前にはこれが書き上がったと思われるが何故か正しく挙動しなかった...)(実際には最後マイナーチェンジしてたかもしれない)
stant
予選も6番ギリで終わらなかったし何か改善しないと春でもやらかしそうで怖い。
本選は完全に最下位でしたが、一応IOIに行ってきた身なので春合宿は本気でやりたいと思います。
