スポンサーサイト

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

Codeforces Beta Round #85

2011/09/03 21:00~23:00 (JST)
Codeforces Beta Round #85 の参加記録

Tags : プログラミング Codeforces 未解決

結果

A. AC (00:06)
B. AC (01:15)
C. AC (00:59)
D. -
E. -
Hacks : +-0 (0/0)
Standing : 53/485
Rating : 17911926


問題

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

A. Petya and Inequations
n 個の正整数 a1, ..., an
・ Σ ai2 ≧ x
・ Σ ai ≦ y
を同時に満たすものが存在するかどうか判定せよ。
存在する場合は具体的な値を 1 つ答えよ。

1 ≦ n ≦ 105
1 ≦ x ≦ 1012
1 ≦ y ≦ 106

B. Petya and Divisors
整数の組 xi, yi が n 組与えられる。
各組 xi, yi に対して、
「xi の約数で、かつ xi-1, xi-2, ..., xi-yi のどの約数にもなっていないものの個数」 を求めよ。

1 ≦ n ≦ 105
1 ≦ xi ≦ 105
0 ≦ yi ≦ i-1

C. Petya and Spiders
m × n のグリッドがある。
最初、各マスには 1 匹ずつクモがいる。
クモたちは上下左右に 1 マスだけ移動するか、その場所にとどまるかすることができる。
同じマスに複数のクモが入ることができて、グリッドの外には出ることができない。
移動後にクモがいるマスは最小でいくつあるか?

1 ≦ m × n ≦ 40

D.

E.

解答

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

A.
int main(){
int n;
ll x,y; cin>>n>>x>>y;

static ll a[100000];
a[0]=y-(n-1);
for(int i=1;i<n;i++) a[i]=1;

if(y<n || inner_product(a,a+n,a,0LL)<x) cout<<-1<<endl;
else{
rep(i,n) cout<<a[i]<<endl;
}

return 0;
}

Σ ai = y を満たしながら
Σ ai2 を最大化すると考える。

とすると、直感的には
a1 = 1
a2 = 1
...
an-1 = 1
an = y - (n-1)
とするのがベストなように思える。

これは正しくて、証明も難しくない。
ai ≧ 2 となる i が 2 つ以上あれば、それは最適でないことが示せる。

あとは、Σ ai = y をそもそも満たせない場合に注意してコーディングすればいい。

以前から使ってみたかった std::inner_product をはじめて使うことができて満足。

B.
vector<int> divisor(int a){
vector<int> res;
for(int i=1;i*i<=a;i++) if(a%i==0) {
res.push_back(i);
if(i*i<a) res.push_back(a/i);
}
return res;
}

int main(){
int n; scanf("%d",&n);
static int last[100001];
memset(last,-1,sizeof last);
rep(i,n){
int x,y; scanf("%d%d",&x,&y);
vector<int> d=divisor(x);

int ans=0;
rep(j,d.size()){
if(last[d[j]]<i-y) ans++;
last[d[j]]=i;
}
printf("%d\n",ans);
}

return 0;
}

素直にやろうとすると O(n2) かかってしまって間に合わない。
以前のクエリの情報をいかにすばやく取り出すかというのがポイント。

以前の計算結果のすべては必要ではなくて、ある約数が最後に現れたのがいつかさえ分かればいい。
つまり、

last[a] := ( a が xi の約数であるような最大の i )

という配列 last を用意してやればいい。
これで、以前の情報が O(1) で取り出せる。

x の約数を全列挙するのは O(√x) かかるので、全体の計算量は O(n √x) になる。
約数を求める部分はライブラリからコピペ。

C.
class DominatingSet{
const int n;
const long long Omega;
vector<long long> mask,mask2;

int dfs(int u,long long S,int tmp,int &ub){
if(S==Omega){
ub=tmp;
return tmp;
}
if(u==n || tmp>=ub || (S|mask2[u])!=Omega) return n;

return min(dfs(u+1,S,tmp,ub),dfs(u+1,S|mask[u],tmp+1,ub));
}

public:
DominatingSet(const vector< vector<int> > &adj):n(adj.size()),Omega((1LL<<adj.size())-1){
mask.resize(n);
rep(u,n){
mask[u]=1LL<<u;
rep(i,adj[u].size()) mask[u]|=1LL<<adj[u][i];
}

mask2.resize(n);
mask2[n-1]=mask[n-1];
for(int u=n-1;u>0;u--) mask2[u-1]=mask[u-1]|mask2[u];
}

int solve(){
int ub=n;
return dfs(0,0,0,ub);
}
};

int main(){
int m,n; scanf("%d%d",&m,&n);

vector< vector<int> > adj(m*n);
rep(i,m) rep(j,n) rep(k,4) {
int y=i+dy[k],x=j+dx[k];
if(0<=y && y<m && 0<=x && x<n) adj[i*n+j].push_back(y*n+x);
}

printf("%d\n",m*n-DominatingSet(adj).solve());

return 0;
}

グリッドをグラフとみると、支配集合 (Dominating Set) の最小サイズを求める問題だということに気付く。
専門的にはこの数を Domination Number と呼ぶらしい。

Spaghetti Source によれば、頂点数 40 なら気合の枝刈りバックトラックで間に合うとのこと。
上記コードは、あとで書き直してきれいにクラス化したもの。

ちなみに、想定解は bit DP らしい。

D.


E.


感想

A.
simple math.
実装問題よりこういうのの方が好き。

B.
けっこうな時間考えても方針が浮かばなかったので、先に C に行った。
C を解いて戻ってきて、さらに考えるとようやく解法に気付いた。

C.
(自分にとっては) 知識問題でラッキーだった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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