スポンサーサイト

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

VK Cup 2012 Round 1

2012/03/12 2:00 ~ 4:00
VK Cup 2012 Round 1 の参加記録

どの問題も適度に難しかった。
Round 1 で敗退。ワイルドカード枠もがんばる。

Tags : プログラミング Codeforces

結果

A. AC (00:20)
B. -
C. -
D. pretest TLE
E. -
Standing : 1067/2227
Rating : 18621752


問題

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

A. Dress'em in Vests!

n 人の兵隊と m 着の防弾チョッキがある。
兵隊 i はサイズ a[i]-x 以上 a[i]+y 以下の防弾チョッキを着ることができる。
最大で何人の兵隊が防弾チョッキを着ることができるか?

1 ≦ n, m ≦ 10^5

B. Discounts

n 個の商品をすべて買いたい。
自分は k 個の買い物かごを持っており、それぞれちょうど 1 回だけ使える。
商品は stool か pencil かのどちらか。
stool が一つ以上入っている買い物かごについては、清算の際に、かごにある最も安い商品の値段を半分にできる。
商品のかごへの割り振り方をうまく決めることで、合計支払い金額を最小化せよ。
なお、どのかごにも少なくとも一つの商品が入っていないといけない。

1 ≦ k ≦ n ≦ 10^3

C. Abracadabra
次の手順で文字列 s を構成する。

step 1: s = "a"
step 2: s = s + "b" + s
step 3: s = s + "c" + s
step 4: s = s + "d" + s

step 26: s = s + "z" + s
step 27: s = s + "0" + s
step 28: s = s + "1" + s
step 29: s = s + "2" + s
step 30: s = s + "3" + s


ここで + は文字列の連結を表す。

s の二つの部分文字列 s[l1..r1], s[l2..r2] が与えられるので、これらの最長共通部分文字列の長さを求めよ。

D. Distance in Tree

n 頂点の木が与えられる。
頂点の順序対 (u, v) であって、u と v の距離が k であるものの個数を求めよ。

1 ≦ n ≦ 50000
1 ≦ k ≦ 500

E. Polycarpus the Safecracker

n × n の行列の各成分に 0, 1, ..., 9 のどれかを入れる。
このとき、行列が対称になり、かつすべての行について、それらを横に読んでできる数が素数であるようにしたい。

一番上の行の数字たちが与えられる。
題意をみたす行列は何通り考えられるか?

2 ≦ n ≦ 5

解答

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

A.
int main(){
int m,n,x,y; scanf("%d%d%d%d",&m,&n,&x,&y);
int a[100000],b[100000];
rep(i,m) scanf("%d",a+i);
rep(j,n) scanf("%d",b+j);

vector< pair<int,int> > ans;
for(int i=0,j=0;i<m&&j<n;){
if(a[i]-x<=b[j] && b[j]<=a[i]+y){
ans.push_back(make_pair(i+1,j+1));
i++;
j++;
}
else if(b[j]<a[i]-x){
j++;
}
else{
i++;
}
}

printf("%d\n",ans.size());
rep(i,ans.size()) printf("%d %d\n",ans[i].first,ans[i].second);

return 0;
}

CodeChef May Cook-Off 2011 の PACKBAND と同じ問題。

兵隊と防弾チョッキの間で二部グラフを作って、その最大マッチングを求める問題。
ただし、辺の数が多いのでふつうにやると間に合わない。

兵隊を区間、防弾チョッキを点だと思う。
左の点から順に処理していく。
まだ使っていない区間の中で、右端が一番左にあるものを使うのが最適であることがいえる。

実装は、区間を右端の昇順で、点を昇順でソートして、二つのポインタを進めていく感じで書けばいい。
今回の問題では入力がすでにソートされているので少し楽。

B.
struct item{
int val,id;
bool operator<(const item &a)const{ return val<a.val; }
};

int main(){
int n,k; scanf("%d%d",&n,&k);
vector<item> stool,pencil;
rep(i,n){
int val,type; scanf("%d%d",&val,&type);
if(type==1) stool .push_back((item){val,i+1});
else pencil.push_back((item){val,i+1});
}
sort(stool .begin(),stool .end());
sort(pencil.begin(),pencil.end());

bool half[1000]={};
vector<item> cart[1000];
// stool の個数が cart の個数以上のとき
if(stool.size()>=k){
rep(i,(int)stool.size()-k){
cart[0].push_back(stool[i]);
half[0]=true;
}
rep(i,k){
cart[i].push_back(stool[i+(int)stool.size()-k]);
half[i]=true;
}
rep(i,pencil.size()) cart[0].push_back(pencil[i]);
}
// stool の個数が cart の個数より少ないとき
else{
rep(i,stool.size()){
cart[i].push_back(stool[i]);
half[i]=true;
}
rep(i,pencil.size()){
cart[min((int)stool.size()+i,k-1)].push_back(pencil[i]);
}
}

// 合計金額を計算
double ans=0;
rep(i,k){
int val_min=cart[i][0].val;
rep(j,cart[i].size()){
ans+=cart[i][j].val;
val_min=min(val_min,cart[i][j].val);
}
if(half[i]) ans-=val_min/2.0;
}

printf("%.1f\n",ans);
rep(i,k){
printf("%d",cart[i].size());
rep(j,cart[i].size()) printf(" %d",cart[i][j].id);
puts("");
}

return 0;
}

stool が何のことなのかよくわからない。

stool の個数の買い物かごの個数の大小で場合わけしてそれぞれ考える。
stool の方が多いときは、高額の stool をひとつずつそれぞれのかごに入れて、その他全部を一つのかごに詰め込むのが最適。
かごの方が多いときは、stool をそれぞれのかごにばらけさせて、pencil を空のかごと最安の stool のかごに詰め込むのが最適。

C.
void dfs(int l,int r,int dep,vector< pair<int,int> > &ans){
if(l>r) return;

ans.push_back(make_pair(l,r));

int n=(1<<dep)-2;
if(l==0 && r==n) return; // !! important !!

int mid=n/2;
int l_next[]={l,max(l,mid+1)-(mid+1)};
int r_next[]={min(r,mid-1),r-(mid+1)};
rep(i,2) dfs(l_next[i],r_next[i],dep-1,ans);
}

int main(){
int l1,r1,l2,r2; scanf("%d%d%d%d",&l1,&r1,&l2,&r2); l1--; r1--; l2--; r2--;

vector< pair<int,int> > ans1,ans2;
dfs(l1,r1,30,ans1);
dfs(l2,r2,30,ans2);

int ans_max=0;
rep(i,ans1.size()) rep(j,ans2.size()) {
ans_max=max(ans_max,min(ans1[i].second,ans2[j].second)-max(ans1[i].first,ans2[j].first)+1);
}
printf("%d\n",ans_max);

return 0;
}

Editorials とそのページのコメント欄、watashi さんのコードなどを参考にして解いた。まだ、いまいち納得できていない。

s の二つの部分文字列を別々に考えて、最後にまとめる。

それぞれの部分文字列について、候補となるものをすべて列挙していく。
s の中央で半分に分けながら再帰的にやる。

segment tree の区間更新を思い浮かべると、候補は高々 30 の定数倍個くらいしかないことがわかる。

C. ( 別解 )
int dp[80][80][80][80];
int dfs(int l1,int r1,int l2,int r2,int dep){
if(l1>r1 || l2>r2) return 0;
if(l1==l2 && r1==r2) return r1-l1+1;

if(r1<80 && r2<80 && dp[l1][r1][l2][r2]!=-1) return dp[l1][r1][l2][r2];

int mid=(1<<dep-1)-1;
int res=0;
if(l1<=mid && mid<=r1 && l2<=mid && mid<=r2){
res=max(res,min(r1,r2)-max(l1,l2)+1);
}
int l1_next[]={l1,max(l1,mid+1)-(mid+1)};
int l2_next[]={l2,max(l2,mid+1)-(mid+1)};
int r1_next[]={min(r1,mid-1),r1-(mid+1)};
int r2_next[]={min(r2,mid-1),r2-(mid+1)};
rep(i,2) rep(j,2) res=max(res,dfs(l1_next[i],r1_next[i],l2_next[j],r2_next[j],dep-1));

if(r1<80 && r2<80) dp[l1][r1][l2][r2]=res;

return res;
}

int main(){
int l1,r1,l2,r2; scanf("%d%d%d%d",&l1,&r1,&l2,&r2); l1--; r1--; l2--; r2--;
memset(dp,-1,sizeof dp);
printf("%d\n",dfs(l1,r1,l2,r2,30));
return 0;
}

自分が最初に出した非想定解法。
一応、2.3 sec くらいで accepted になる。

与えられた部分文字列を s1, s2 とする。

s1, s2 の最長共通部分文字列で '3' を含むもの、
s1, s2 の最長共通部分文字列で '2' を含むもの、
s1, s2 の最長共通部分文字列で '1' を含むもの、
・・・
というのを再帰で順に計算していく。
元の文字列は真ん中の文字について対称になっているので、右半分はそのまま左半分にスライドさせられる。

このままだと 2^30 くらいかかるけど、深さが 23 くらいになると状態がメモリに乗るので、以降はメモ化できる。

D.
int n;
vector<int> G[50000];
int parent[50000];
void dfs(int u,int pre){
parent[u]=pre;
rep(i,G[u].size()){
int v=G[u][i];
if(v!=pre) dfs(v,u);
}
}
int main(){
int k; scanf("%d%d",&n,&k);
rep(i,n-1){
int u,v; scanf("%d%d",&u,&v); u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(0,-1);
// dp[u][i] := ( u を根とする部分木の頂点で u からの距離が i であるものの総数 )
static int dp[50000][501];
rep(u,n) dp[u][0]=1;
rep(i,k) for(int u=1;u<n;u++) dp[parent[u]][i+1]+=dp[u][i];
ll ans=0;
rep(u,n){
ans+=dp[u][k];
int v=u,w=parent[u];
for(int i=1;i<=k;i++){
if(w==-1) break;
ans+=dp[w][k-i];
if(i<k) ans-=dp[v][k-i-1];
v=parent[v];
w=parent[w];
}
}
printf("%I64d\n",ans/2);
return 0;
}

コンテスト中に出したコードは、500*50000 回くらい再帰呼び出しをしていて、定数倍の差で TLE していた。
終わってから、ループで DP するように書き直したら通った。悲しい。

頂点 0 を木の根と思う。
頂点 u を根とする部分木を T(u) と書くことにする。

木の上で DP する。
dp[u][i] := ( T(u) の頂点で u からの距離が i であるものの総数 )
木のトポロジカル順序を気にしなくても、ループを i, u の順に回すことで自動的にトポロジカル順序になる。

答えは
( Σu ∈ V ( u との距離が k である T(u) の頂点の個数 )
+ ( u との距離が k である V-T(u) の頂点の個数 ) )/2

で計算できる。
Σ の中身の第一項は dp[u][k] そのもの。
第二項は、u の親へ k ステップだけ昇りながら計算していける。
u の親を p(u) と書くと
( u との距離が k である V-T(u) の頂点の個数 )
= ( dp[p(u)][k-1] - dp[u][k-2] )
+ ( dp[p(p(u))][k-2] - dp[p(u)][k-3] )
+ ( dp[p(p(p(u)))][k-3] - dp[p(p(u))][k-4] ) + …

となる。
右辺の括弧でくくった第 i 項では、
「 u を端点とし、u の i 個上の先祖を通り、u の i+1 個上の先祖を通らない長さ k のパスの個数 」
を数えていることになる。

それにしても、この問題を 700 人以上が正解しているというのが信じられない。

E.
const int P_MAX=100000;
bool er[P_MAX+1];
void sieve(){
rep(i,P_MAX+1) er[i]=(i>=2);
for(int i=2;i*i<=P_MAX;i++) if(er[i]) for(int j=i*i;j<=P_MAX;j+=i) er[j]=false;
}

int n,B[5][5];
int dfs(int i,int j){
if(i==n-1){
int res=1;
for(int k=1;k<n;k++){
int cnt=0;
rep(a,10){
B[k][k]=a;
int num=0;
rep(l,n) num=10*num+B[k][l];
if(er[num]) cnt++;
}
res*=cnt;
}
return res;
}

if(j==n){
if(B[i][n-1]%2==0 && B[i][n-1]!=2) return 0; // pruning
return dfs(i+1,i+2);
}

int res=0;
rep(a,10){
B[i][j]=B[j][i]=a;
res+=dfs(i,j+1);
}
return res;
}

int main(){
sieve();

int T; scanf("%d",&T);
while(T--){
char s[8]; scanf("%s",&s);
n=strlen(s);
rep(i,n) B[0][i]=B[i][0]=s[i]-'0';
printf("%d\n",dfs(1,2));
}

return 0;
}

Editorials を見ながら解いた。
対角成分以外の要素 ( 高々 6 個 ) について全探索する。
対角成分は他の行とは独立に決められるので、その部分をまとめて数えてかけ算して足し算する。

最後の部分は前処理しておけば速くできるけど、毎回計算しても間に合った。
ただし、毎回計算するなら、末尾が偶数のときに枝刈るとかをしないといけない。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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