スポンサーサイト

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

Codeforces Beta Round #76

2011/07/01 0:00~2:00 (JST)
Codeforces Beta Round #76 (Div.1 Only) の参加記録

Tags : プログラミング Codeforces

結果

A. 2WA(pretest), AC (00:30)
B. WA
C. -
D. -
E. -
Hacks : +-0 (0/0)
Standing : 172/417
Rating : 18131792


問題

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

A. Frames
問題ページにある画像のように、n 個のフォルダが並べられている。
1 行にあるフォルダの数は m 個。

長方形領域上のフォルダは一度に選択できる。
同じフォルダを 2 回選択すると、選択が解除される。

フォルダ a からフォルダ b までを選択するために、最小で何回選択すればいいかを求めよ。

1 ≦ n, m ≦ 109
1 ≦ a ≦ b ≦ n

B. End of Exams
m 本のミルクビンから n 個のカップにミルクを注ぎたい。

・ 最初、どのビンにも体積 w のミルクが入っている。
・ カップに入っているミルクの総量は、どのカップも等しいようにする。
・ 1 本のビンからは高々 2 つカップにだけミルクを注ぐことができる。

このような分配が可能かどうかを判定せよ。
可能であれば、具体的な分配方法を 1 つ示せ。

C. Azembler
26 個レジスタ eax, ebx, ..., ezx がある。
最初、ebx, ecx, ..., ezx は 0 に初期化されている。

次の 4 種類の命令がある。
・ lea x, [y]
・ lea x, [y + z]
・ lea x, [k*y]
・ lea x, [y + k*z]

それぞれ、
・ x に y を代入する
・ x に y+z を代入する
・ x に k*y を代入する
・ x に y+k*z を代入する
という操作を意味する。

x, y, z にはレジスタの名前が入る。
k = 1, 2, 4, 8.

eax の n 倍を得るのに必要な命令の最小個数と、具体的な手順を 1 つ答えよ。

1 ≦ n ≦ 255

D. Flags
x 本の縞が入った旗がある。
白,黒,赤,黄の 4 色を使って縞を着色したい。
その際、次の条件がみたされなければいけない。

・ 同じ色の縞は隣り合わない
・ 白と黄は隣り合わない
・ 赤と黒は隣り合わない
・ 黒-白-赤の順 ( またはその逆順 ) が現れない

L ≦ x ≦ R なる x で、上記の条件をみたす旗は合計何通りあるか答えよ。
ただし、上下反転でパターンが一致する旗は同じものとみなす。

1 ≦ L ≦ R ≦ 109

E. Lostborn
n 以下の自然数で a1, a2, ..., ak のどれとも割り切れないものの個数を求めよ。

1 ≦ n ≦ 1013
1 ≦ k ≦ 100
1 ≦ ai ≦ 1000
ai と aj は互いに素 ( i ≠ j )

解答

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

A.
int main(){
int n,m,a,b; scanf("%d%d%d%d",&n,&m,&a,&b);
a--, b--;

int y1=a/m,x1=a%m,y2=b/m,x2=b%m;
if(y1==y2 || (x1==0 && x2==m-1) || (x1==0 && b==n-1)){
puts("1");
}
else if(y1+1==y2 || x1==0 || x2==m-1 || x1==x2+1 || b==n-1){
puts("2");
}
else{
puts("3");
}

return 0;
}

答えが 3 以下であることはすぐにわかるので、
答えが 1 になるときと答えが 2 になるときの条件をすべて書き出せばいい。

相当注意深く書かないと WA になる。
右と左で 2 つの長方形を作れるケースなどを見逃していて 2WA.
pretest が強くて助かった。

B. (時間外)
int main(){
int n,w,m; scanf("%d%d%d",&n,&w,&m);

vector<pii> ans[50];
int milk=m,cup=n,i=0,j=0;
while(i<m && j<n){
ans[i].push_back(mp(min(milk,cup),j));
if(milk==cup){
milk=m;
cup=n;
i++;
j++;
}
else if(milk<cup){
cup-=milk;
milk=m;
j++;
}
else{ // milk>cup
milk-=cup;
cup=n;
i++;
}
}

bool ok=true;
int cnt[50]={};
rep(i,m) rep(j,ans[i].size()) {
cnt[ans[i][j].second]++;
if(cnt[ans[i][j].second]>2) ok=false;
}

if(!ok) puts("NO");
else{
puts("YES");
rep(i,m){
rep(j,ans[i].size()){
printf("%d %.9f%c",ans[i][j].second+1
,(double)ans[i][j].first*w/m
,j<ans[i].size()-1?' ':'\n');
}
}
}

return 0;
}

「一番多く余っているミルクを空き容量が最大のカップにいれる」
という Greedy でいけそうな気がしたので、よく考えずに書いてみたらダメだった。

正解はもっと単純な Greedy アルゴリズムで、
「ミルクがなくなるまで、左のカップから順番に入れていく」 (文章で説明しにくい!!)
とするだけでいい。

double のままやると誤差が怖かったので、ビンに入っているミルクの量を m として、出力するときに調節した。

C. (時間外)
char ans[6][32];
int n,reg[26]={1},n_ans=6;

bool solve(int pos){
if(reg[pos]>n || pos>=n_ans) return false; // pruning

if(reg[pos]==n){ n_ans=pos; return true; }

bool ok=false;
rep(i,pos+1) rep(j,pos+1) for(int k=1;k<=8;k*=2) {
int v=reg[i]+k*reg[j];
if(v<reg[pos]) continue; // pruning

reg[pos+1]=v;
if(solve(pos+1)){
sprintf(ans[pos],"e%cx, [e%cx + %d*e%cx]",pos+1+'a',i+'a',k,j+'a');
ok=true;
}
}

rep(i,pos+1) for(int k=1;k<=8;k*=2) {
int v=k*reg[i];
if(v<reg[pos]) continue; // pruning

reg[pos+1]=v;
if(solve(pos+1)){
sprintf(ans[pos],"e%cx, [%d*e%cx]",pos+1+'a',k,i+'a');
ok=true;
}
}

return ok;
}

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

solve(0);

printf("%d\n",n_ans);
rep(i,n_ans) printf("lea %s\n",ans[i]);

return 0;
}

加法鎖 (Addition chain) に似ている。
最短の Addition chain を求める問題は NP-complete なので、この問題も多項式時間アルゴリズムが得られる可能性は低いように思えた。

となるとバックトラックで全探索するしかないけど、B を提出してからはずっと E を考えていたので、書く時間がなかった。

[ 2011/07/10 追記 ]

解説を見ながら解いた。
答えがそれほど長くならないことは容易に想像できるので、上限を決めうちしてバックトラックすればよい。
今回は、答えの最大長が 5 であるということを読んで知っていたので、直接、その値を使っている。

バックトラックといっても、どのレジスタからどのレジスタへどの操作をするか、というのをすべて調べていてはさすがに間に合わない。
実は、探索する範囲を
「 i 番目の操作では i+1 番目のレジスタに値を代入する」
というものに制限しても、最適解 (の一つ) が得られる。
なぜなら、すでに作った値に上書きするかわりに、新しいレジスタに書き込んでも悪くはならないから。
レジスタの個数は十分多く (26 個) あることに注意。

さらに、レジスタに書き込む値は (広義) 単調増加するとも仮定できるけど、それはしなくても間に合う。

D. (時間外)
const ll M=1000000007,inv2=500000004;

// row : to, col : from
ll A[9][9]={
{0,0,1,0,0,0,0,0,0}, // WB
{0,0,0,0,1,0,0,0,0}, // WR
{1,0,0,0,0,0,1,0,0}, // BW
{1,0,0,0,0,0,1,0,0}, // BY
{0,1,0,0,0,0,0,1,0}, // RW
{0,1,0,0,0,0,0,1,0}, // RY
{0,0,0,1,0,1,0,0,0}, // YB
{0,0,0,1,0,1,0,0,0}, // YR
{1,1,1,1,1,1,1,1,1} // total
},Apow[30][9][9];

ll f(ll x){
if(x==0) return 0;

x--;
ll v[9]={1,1,1,1,1,1,1,1,4},v2[9];
for(int t=0;x;t++,x/=2) if(x&1) {
memset(v2,0,sizeof v2);
rep(i,9) rep(j,9) {
v2[i]+=Apow[t][i][j]*v[j];
v2[i]%=M;
}
memcpy(v,v2,sizeof v);
}

return v[8];
}

ll solve(ll x){ return (f(x)+f((x+1)/2))*inv2%M; }

int main(){
memcpy(Apow[0],A,sizeof A);
rep(t,29) rep(i,9) rep(j,9) rep(k,9) {
Apow[t+1][i][j]+=Apow[t][i][k]*Apow[t][k][j];
Apow[t+1][i][j]%=M;
}

int l,r; scanf("%d%d",&l,&r);
printf("%d\n",(solve(r)-solve(l-1)+M)%M);

return 0;
}

[ 2011/07/10 追記 ]

解説を見ながら解いた。

上から順に色を塗っていく。
次にどの色を塗れるかは、前 2 回分にどの色を塗ったかが分かれば特定できる。
これを普通の DP でやってはもちろん間に合わないので、行列に落とし込んで、繰り返し二乗法を使うことを考える。

ここまでで、任意の長さの旗の塗り方の総数が計算できる。
あとは、これらの総和を求めないといけない。
それをやるにはとてもよい方法があって、行列を 1 行拡張してやって、その行を使って今までの和を一緒に計算すればいい。
詳細はソースコード参照。行列の積を書き下すと、確かに総和が求められていることが分かる。
ちょうど、普通の DP で dp[i+1]=dp[i]+a[i] とするのを行列でやっている感じ。

上下反転で同じになるものを同一視するというのは、単に 2 で割ればいい。
ただし、左右対称なパターンは一度しかカウントされていないので、その分は調節しないといけない。

E. (時間外)
const int N_MAX=10000;

int a[100];
ll dp[N_MAX][100];

ll solve(ll n,int i){
if(i==-1) return n;

ll &res=dp[n][i];
if(n<N_MAX && ~res) return res;

ll ans=solve(n,i-1)-solve(n/a[i],i-1);
if(n<N_MAX) res=ans;
return ans;
}

int main(){
memset(dp,-1,sizeof dp);

ll n;
int k; scanf("%I64d%d",&n,&k);
rep(i,k) scanf("%d",a+i);

sort(a,a+k);

printf("%I64d\n",solve(n,k-1));

return 0;
}

正解者のコードを読んで理解した。

dp (n, i) := n 以下で ai までのどれとも割り切れない自然数の個数
とする。

n 以下で ai までのどれとも割り切れない自然数の個数
= n 以下で ai-1 までのどれとも割り切れない自然数の個数
- n 以下で ai-1 までのどれとも割り切れない、かつ、ai と割り切れる自然数の個数

である。

ここで、右辺第 2 項は、
{ ai, 2 ai, ..., floor(n/ai) ai } の中で ai-1 までのどれとも割り切れない数の個数
と言い換えられる。
さらに、ai と aj が互いに素という条件から、これは
{ 1, 2, ..., floor(n/ai) } の中で ai-1 までのどれとも割り切れない数の個数
に等しい。
これは、dp (floor(n/ai), i-1) そのものである。

ゆえに、次の漸化式が成り立つ。
dp (n, i) = dp (n, i-1) - dp (floor(n/ai), i-1).

あとは、これを計算すればいいのだけど、
まともにやると 2k 回くらいの再帰呼び出しが起こるので間に合わない。
メモ化しようにも n が大きすぎる。

そこで、一部だけメモ化することを考える。
さらに、ai を値の降順に調べることで、早い段階で n を小さくして、メモ化の恩恵を受けやすくする。
こうすると、最悪ケースでも 1sec 程度で終わるようになった。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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