スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

CodeChef January Cook-Off 2012

2012/01/23 01:00 ~ 03:30 (JST)
CodeChef January Cook-Off 2012 の参加記録

どの問題も、あと数歩届かない。

Tags : プログラミング CodeChef

結果

A. AC (00:20:29)
B. -
C. -
D. 2RE, 4TLE, 3WA
E. -
Standing : 66/436
Rank (Short) : ?? → 39
Rating (Short) : ?? → 1575.811


問題

問題セットの原文はここを参照。

A. Collision in Space

地球と N 個の星の座標が与えられる。
地球と各星はそれぞれ単位速度で、上下左右のいずれかの方向に運動している。
地球と惑星が最初に衝突するのはいつか?
惑星同士は衝突しないと仮定してよい。

1 ≦ テストケース数 ≦ 10
1 ≦ N ≦ 2012
-100 ≦ 座標値 ≦ 100 ( 整数 )

B. Remys last tour

R × C のグリッドで、各マスに重み A[i][j] がある。
最初、自分は 0 行目の好きな位置にいる。
自分の今いる座標を (i, j) とすると
・ (i+1, j)
・ (i, j-1)
・ (i, j+1)
の 3 方向に好きなだけ移動できる。
w-1 行目まで移動したときに一回以上乗ったマスの重みの和を最大化せよ。
( 同じマスに 2 回以上乗っても、重みは一回分のみカウントする。 )

1 ≦ テストケース数 ≦ 5
1 ≦ R, C ≦ 2012
-500 ≦ A[i][j] ≦ 500

C. Moving between Floors

N 本の塔が一列に並んでいる。
各塔は F 階まであり、i 階と i+1 階の間を移動するのに 1 秒かかる。
隣あう塔の 1 階から 1 階へも移動できて、これも 1 秒かかる。

いくつかの塔の間には橋がかかっている。
橋は合計 M 本ある。

自分のいる位置 ( 塔の番号 bq と階数 fq の組 ) が Q 個与えられるので、それぞれに対して
Σ[b=1..N, b!=bq] Σ[f=1..F] ( 位置 (bq, fq) から位置 (b, f) までの最短距離 )
を求めよ。

2 ≦ N, M ≦ 100
1 ≦ F ≦ 10^6
1 ≦ Q ≦ 2012

D. Makx Sum

長さ N の数列 A[1..N] が与えられる。
N(N+1)/2 個ある A[1..N] の連続部分列の和を大きい順に並べたときの K1 番目、K2 番目、K3 番目の数をそれぞれ答えよ。

1 ≦ テストケース数 ≦ 3
2 ≦ N ≦ 10000
1 ≦ K1 < K2 < K3 ≦ min(2012, N*(N+1)/2)
-10000 ≦ A[i] ≦ 10000

E. Zeta-Nim Game

N 山の Nim ゲーム。
山 i には自然数 C[i] が割り当てられていて、山 i から一度に取れる石の数 R は 1 ≦ R ≦ C[i] をみたさないといけない。
山 i から R 個の石を取ったとき、C[i] = R と更新する。
ゲーム開始時は、山 i の石の数は A[i] で C[i] = K である。

先手必勝かどうか判定せよ。

1 ≦ テストケース数 ≦ 10
1 ≦ N ≦ 50
1 ≦ A[i] ≦ 2012
1 ≦ K ≦ 10^5

解答

言語は C++。テンプレはここを参照。

A.
const int INF=1<<29;

struct star{
int x,y;
char dir;
};

void f(int t,star S,double &x,double &y){
if(S.dir=='U') x=S.x, y=S.y+t/2.0;
if(S.dir=='L') x=S.x-t/2.0, y=S.y;
if(S.dir=='D') x=S.x, y=S.y-t/2.0;
if(S.dir=='R') x=S.x+t/2.0, y=S.y;
}

int main(){
int T; scanf("%d",&T);
while(T--){
star E;
int n;
scanf("%d%d %c%d",&E.x,&E.y,&E.dir,&n);

int ans=INF;
rep(i,n){
star A;
scanf("%d%d %c",&A.x,&A.y,&A.dir);
rep(t,410){
double x1,y1; f(t,E,x1,y1);
double x2,y2; f(t,A,x2,y2);
if(x1==x2 && y1==y2){
ans=min(ans,t);
break;
}
}
}

if(ans<INF) printf("%.1f\n",ans/2.0);
else puts("SAFE");
}

return 0;
}

制約が小さいので、素直に時間を 0.5 ずつ進めるシミュレーションをした。
もちろん O(N) でも解けるけど書きにくい。

2 進小数で書ける数しか出てこないので、double 値を == で比較するという荒業をやった。

B. ( あとで解いた )
int h,w,a[2012][2012];

int solve(){
// dp[i][j] := (i,j) からスタートしたときの最適解
static int dp[2013][2012];
rep(j,w) dp[h][j]=0;
for(int i=h-1;i>=0;i--){
// lsum[j] := max{ a[i][k]+a[i][k+1]+...+a[i][j] | k<=j }
// rsum[j] := max{ a[i][j]+a[i][j+1]+...+a[i][k] | j>=k }
static int lsum[2012],rsum[2012];
rep(j,w){
lsum[ j ]=(j>0?max(lsum[j-1],0):0)+a[i][ j ];
rsum[w-j-1]=(j>0?max(rsum[w-j],0):0)+a[i][w-j-1];
}

// ldown[j] := (i,j) からスタートして (i,j+1) を通らず (i,k) (k<=j) で次の行に降りるルートにおける最適解
// rdown[j] := (i,j) からスタートして (i,j-1) を通らず (i,k) (k>=j) で次の行に降りるルートにおける最適解
static int ldown[2012],rdown[2012];
rep(j,w){
ldown[ j ]=lsum[ j ]+dp[i+1][ j ];
rdown[w-j-1]=rsum[w-j-1]+dp[i+1][w-j-1];
if(j>0){
ldown[ j ]=max(ldown[ j ],a[i][ j ]+ldown[j-1]);
rdown[w-j-1]=max(rdown[w-j-1],a[i][w-j-1]+rdown[w-j]);
}
}

rep(j,w){
int route1=(j> 0 ?max(lsum[j-1],0):0)+rdown[j];
int route2=(j<w-1?max(rsum[j+1],0):0)+ldown[j];
dp[i][j]=max(route1,route2);
}
}

return *max_element(dp[0],dp[0]+w);
}

int main(){
int T; scanf("%d",&T);
while(T--){
int type; scanf("%d%d%d",&h,&w,&type);
if(type==1){
rep(i,h) rep(j,w) scanf("%d",a[i]+j);
}
else{
int x,p,q,m; scanf("%d%d%d%d",&x,&p,&q,&m);
int cur=x;
rep(i,h) rep(j,w) {
cur=(cur*p+q)%m;
a[i][j]=x-cur;
}
}
printf("%d\n",solve());
}

return 0;
}

コンテスト中は、O(R*C^2) の区間 DP っぽいなーとかちょっと妄想したけど、他の問題に集中していたのであまり考えられなかった。

Editorials の英語がまったく読めなかったので、writer のソースコードを解読した。
うまいことやれば dp[i][j] の更新が O(1) でできますよという話らしい。
計算量は O(R*C)。
コード中にコメントをいっぱい書いたのでそっちを参照。

C. ( あとで解いた )
const int INF=1<<29;

struct vertex{
int id,h; // 塔の番号, 階数
bool operator<(const vertex &v)const{ return id!=v.id ? id<v.id : h<v.h; }
};

struct edge{
vertex u,v;
int cost;
};

// a + (a+1) + (a+2) + (a+n-1)
ll sum(ll a,ll n){ return a*n+n*(n-1)/2; }

// h1 階までの最短距離が d1, h2 階までの最短距離が d2 のときの
// h1, h1+1, ..., h2 階までの最短距離の和
ll calc(int h1,ll d1,int h2,ll d2){
if(d1>d2) swap(d1,d2);
ll a=sum(d1,d2-d1);
h1+=d2-d1;
d1=d2;
return a+sum(d1,(h2-h1+1)/2)+sum(d2,(h2-h1+2)/2);
}

int main(){
int nb,nf,m; scanf("%d%d%d",&nb,&nf,&m);
vector<edge> E;
rep(i,m){
int id1,h1,id2,h2,cost;
scanf("%d%d%d%d%d",&id1,&h1,&cost,&id2,&h2); id1--; h1--; id2--; h2--;
E.push_back((edge){(vertex){id1,h1},(vertex){id2,h2},cost});
}
rep(i,nb-1){
// 隣り合う塔の一階どうしをつなぐ
E.push_back((edge){(vertex){i,0},(vertex){i+1,0},1});
}
m=E.size();

// 重要な頂点のみをみる
vector<int> V[100];
rep(i,m){
vertex u=E[i].u,v=E[i].v;
V[u.id].push_back(u.h);
V[v.id].push_back(v.h);
}
// 頂点集合から重複を除いて、あとのためにソート
int n=0;
rep(i,nb){
sort(V[i].begin(),V[i].end());
V[i].erase(unique(V[i].begin(),V[i].end()),V[i].end());
n+=V[i].size();
}

map<vertex,int> f; // 頂点 -> 頂点番号
rep(i,nb) rep(j,V[i].size()) {
vertex v={i,V[i][j]};
if(f.count(v)==0) f.insert(make_pair(v,f.size()));
}

// Warshall-Floyd
static int wf[300][300];
rep(u,n) rep(v,n) wf[u][v]=(u==v?0:INF);
rep(i,m){
vertex u=E[i].u,v=E[i].v;
wf[f[u]][f[v]]=wf[f[v]][f[u]]=E[i].cost;
}
rep(i,nb) rep(j,(int)V[i].size()-1) {
vertex u={i,V[i][j]},v={i,V[i][j+1]}; // 同じ塔の隣り合う階どうしをつなぐ
wf[f[u]][f[v]]=wf[f[v]][f[u]]=V[i][j+1]-V[i][j];
}
rep(w,n) rep(u,n) rep(v,n) wf[u][v]=min(wf[u][v],wf[u][w]+wf[w][v]);

// query
int nq; scanf("%d",&nq);
while(nq--){
int id,h; scanf("%d%d",&id,&h); id--; h--;

// u に近い重要な 2 頂点
int u1,u2,h1,h2;
rep(j,V[id].size()){
if(V[id][j]>h) break;
h1=V[id][j];
u1=f[(vertex){id,h1}];
}
rep(j,V[id].size()){
h2=V[id][j];
u2=f[(vertex){id,h2}];
if(V[id][j]>=h) break;
}

int d[300]; // d[v] := クエリ頂点 u から重要な頂点 v への最短距離
rep(v,n) d[v]=min(abs(h1-h)+wf[u1][v],abs(h2-h)+wf[u2][v]);

ll ans=0;
rep(i,nb) if(i!=id) { // 塔 i の距離の和
rep(j,(int)V[i].size()-1){
int v1=f[(vertex){i,V[i][j]}];
int v2=f[(vertex){i,V[i][j+1]}];
ans+=calc(V[i][j],d[v1],V[i][j+1],d[v2])-d[v2]; // 重要な 2 頂点間
}

int v=f[(vertex){i,V[i].back()}];
ans+=sum(d[v],nf-V[i].back()); // 一番高い重要な頂点から塔のてっぺんまで
}
printf("%lld\n",ans);
}

return 0;
}

Editorials みた。

一見すると頂点数 N*F の単一始点最短路だけど、注目すべき頂点は高々 2*M+N (≦ 300) 個しかない。
( 各辺の両端と各塔の 1 階 )

この縮約したグラフで最短路を求める。
Warshall-Floyd で間に合う。

クエリの処理は、各塔ごとに調べていけばいい。
今、塔 b に注目しているとする。
縮約したグラフで塔 b (のある階) に対応する頂点を階数の小さいものから一列に並べる。
これを a[1], a[2], ..., a[n] と書く。
a[i]-a[i+1] 間の階の最短距離の和は、a[i] までの最短距離と a[i+1] までの最短距離から定数時間で求められる。
( a[i] から行く方が近い階と a[i+1] から行く方が近い階がバランスするところをみつける )
a[n]-(塔の最上階) 間についても簡単にできる。
最上階を縮約グラフに含めるとちょっと楽かもしれない。

実装はけっこう大変。あんまりうまく書けなかった。
縮約グラフの頂点数を V とすると、
前処理 : O(V^3)
1 クエリ : O(V log V)
かかっている。

D. ( あとで解いた )
int merge(int m,int *a,int n,int *b,int k3){
int i=0,j=0,t=0;
static int c[2012];
while(t<=k3 && (i<m || j<n)){
if (i==m) c[t++]=b[j++];
else if(j==n) c[t++]=a[i++];
else if(a[i]>b[j]) c[t++]=a[i++];
else c[t++]=b[j++];
}
rep(k,t) a[k]=c[k];
return t;
}

int main(){
int T; scanf("%d",&T);
while(T--){
int n,k1,k2,k3; scanf("%d%d%d%d",&n,&k1,&k2,&k3); k1--; k2--; k3--;
int a[10000];
rep(i,n) scanf("%d",a+i);

int sum[10001]={0};
rep(i,n) sum[i+1]=sum[i]+a[i]; // 連続部分列の和が O(1) で引けるように DP で前処理

int n_ans=0,n_mn=1;
int ans[2012],mn[2013]={0};

rep(i,n){
int cand[2012];
rep(j,n_mn) cand[j]=sum[i+1]-mn[j];

// merge
n_ans=merge(n_ans,ans,n_mn,cand,k3);

// insert
rep(j,n_mn+1) if(j==n_mn || mn[j]>sum[i+1]) {
for(int k=n_mn-1;k>=j;k--) mn[k+1]=mn[k];
mn[j]=sum[i+1];
break;
}
if(n_mn<=k3) n_mn++;
}

printf("%d %d %d\n",ans[k1],ans[k2],ans[k3]);
}

return 0;
}

k-th なんとかは k 番目にいいものまで持っておくのが定番な気がしたので、そういう風にやろうとした。
コンテスト中は、priority_queue とか nth_element とか色々試行錯誤しながら、なんとか O(N*K3) のコードを書いたけど、定数が大きかったようで最後まで TLE がとれなかった。

上記コードは Editorials の方針そのまま。
A[i] を右端とする連続部分列の和、上位 K3 個 …… (*)
を各 i について求める。
挿入ソートの要領でやれば、全体で O(N*K3) でできる。
( データ構造を工夫すればもっと速くできるけど、どうせ他がボトルネックになる )

別個、
{ A[1], .., A[i] } のいずれかを右端とする連続部分列の和、上位 K3 個 …… (**)
を管理しておく。
各 i について (*) を用いて (**) を更新する。
マージソートの要領でやれば、全体で O(N*K3) でできる。

E. ( あとで解いた )
int main(){
// g[n][ k ] = mex{ g[n-1][1], g[n-2][2], ..., g[n-k][k] }
// g[n][k+1] = mex{ g[n-1][1], g[n-2][2], ..., g[n-k][k], g[n-k-1][k+1] }
static int g[2013][2013];
for(int n=1;n<=2012;n++){
int i=0;
bool vis[2013]={};
for(int k=1;k<=n;k++){
vis[g[n-k][min(k,n-k)]]=true;
for(;vis[i];i++);
g[n][k]=i;
}
}

int T; scanf("%d",&T);
while(T--){
int n,k; scanf("%d%d",&n,&k);
int ans=0;
rep(i,n){
int a; scanf("%d",&a);
ans^=g[a][min(k,a)];
}
puts(ans?"Nancy":"Zeta");
}

return 0;
}

まず、A[i] < K であっても何の意味もないので K ≦ A[i] と仮定していい。
なので、状態数は A[i]*K = 2012^2 になる。

定石にしたがって Grundy 数を計算しようとしたら、遷移に O(K) かかって間に合わないことに気付いた。
規則性を探してみたけど全然見つからない。
ちなみに、小さい A[i], K での Grundy number はこんな感じになる。
A\K| 1 2 3 4 5 6 7 8 9
---+--------------------------------------
 1 | 1
 2 | 0 2
 3 | 1 2 2
 4 | 0 0 0 3
 5 | 1 1 1 3 3
 6 | 0 2 3 3 3 3
 7 | 1 2 2 3 3 3 3
 8 | 0 0 0 0 0 0 0 4
 9 | 1 1 1 1 1 1 1 4 4
10 | 0 2 3 4 4 4 4 4 4 4
11 | 1 2 2 2 2 2 2 4 4 4 4
12 | 0 0 0 3 4 4 4 4 4 4 4 4
13 | 1 1 1 4 4 4 4 4 4 4 4 4 4
14 | 0 2 3 3 3 3 5 5 5 5 5 5 5 5
15 | 1 2 2 3 3 3 3 5 5 5 5 5 5 5 5
16 | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
17 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5
18 | 0 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5
19 | 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5


コンテスト中はここで諦めて別の問題に取り組んだ。

以下、editorials そのまま。
Grundy number の更新式は
g[n][ k ] = mex{ g[n-1][1], g[n-2][2], ..., g[n-k][k] }
となる。 ( mex{ a1, .., an } は a1, .., an に現れない最小の非負整数 )
g[n][k+1] も書き下すと
g[n][k+1] = mex{ g[n-1][1], g[n-2][2], ..., g[n-k][k], g[n-k-1][k+1] }
となる。
2 つの違いは最後の 1 項だけであることがポイント。

なので、n を固定して k についてループすれば、g[n][1..k] を線形時間で求められる。
( 今どこまで進んだかを表すポインタをもっておく、よくあるアレ )

ふつうにやろうとすると間に合わないけど、うまく問題の構造を調べれば計算量が落ちるという、セオリーどおりというか、とてもまっすぐな問題。
良問だと思う。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。