スポンサーサイト

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

Codeforces Beta Round #81

2011/08/07 20:00~22:00 (JST)
Codeforces Beta Round #80 の参加記録

久しぶりの Div.1, 2 共通回。
Disgaea: Hour of Darkness というゲームが今回の問題セットのテーマ。

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

結果

A. Hacked
B. AC (00:51)
C. WA (pretest)
D. -
E. -
Hacks : +-0 (0/0)
Standing : 216/1500
Rating : 17861836


問題

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

A. Transmigration
プレイヤーは n 個の skill を持っている。
プレイヤーは transmigrate することで、m 個の skill を習得できる。
transmigration の際にはすでに習得している skill の習熟度が 100k % に落ちる。 (整数値に切捨て)
transmigration 後の習熟度が 100 未満になる skill は忘れてしまう。
新しく習得する skill の習熟度は 0 である。

transmigration の結果、プレイヤーの習得している skill とそれらの習熟度を答えよ。

1 ≦ n, m ≦ 20
0.01 ≦ k ≦ 0.99
k は小数点以下 2 桁の数

B. Dark Assembly
n 人の senator からなる議会がある。
プレイヤーの意見は、議会の半数より多い人数が賛成すれば可決される。

senator は level, loyalty の 2 つのパラメータを持っている。
loyalty は 0 以上 100 以下の整数で、senator がプレイヤーに賛成する確率を表す。

プレイヤーは k 個の candy を持っており、議会の決定の前にそれらを senator たちに渡すことができる。
senator は貰った candy 1 つにつき、loyalty を 10 増やす。 (もちろん loyalty は 100 を超えない)

議会で否決された場合、プレイヤーは反対した senator 全員を倒すことで結果を可決に修正することができる。
この行動は 1 度だけ行える。
プレイヤーが senator 全員を倒せる確率は A / (A + B) で与えられる。
ここで、B は反対した senator 全員の level の合計である。

最終的にプレイヤーの意見が可決される確率の最大値を求めよ。

1 ≦ n, k ≦ 8
1 ≦ A ≦ 9999

C. Item World
n 個の item がある。
item は次の 6 個のパラメータで特徴付けられている。
name : item の名前
class : item の種類. weapon, armor, orb のいずれか
atk : class が weapon の時の item の強さ (それ以外の class については意味がない数値)
def : class が armor の時の item の強さ (〃)
res : class が orb の時の item の強さ (〃)
size : item に入る resident の最大数 (後述)

k 人の resident がいる。
resident は item の中に住んでいて、その item を強くする効果がある。
resident は次の 4 個のパラメータで特徴付けられている。
name : resident の名前
type : resident の種類. gladiator, sentry, physician のいずれか
bonus : item の強さの上昇値. gladiator は atk を、sentry は def を、physician は res を上昇させる
home : resident が今住んでいる item の名前

item の size に空きがあれば、resident はその item に移動することができる。
同時に移動できる resident は 1 人のみ。 ( 2 人を同時にスワップするようなことはできない )

item の中から、weapon, armor, orb をそれぞれ 1 つずつ選びたい。
その際、選んだ weapon の強さ、armor の強さ、orb の強さがこの順で最大になるようにしたい。
どの item を選び、それらにどのように resident を付加させればいいかを答えよ。

3 ≦ n ≦ 100
1 ≦ k ≦ 1000

D.

E.

解答

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

A. (時間外)
int main(){
int n,m,k,dmy1;
char dmy2; cin>>n>>m>>dmy1>>dmy2>>k;

map<string,int> skill;
map<string,int>::iterator it;
rep(i,n){
string name;
int exp; cin>>name>>exp;
exp=k*exp/100;
if(exp>=100) skill[name]=exp;
}
rep(i,m){
string name; cin>>name;
if(skill.count(name)==0) skill[name]=0;
}

cout<<skill.size()<<endl;
for(it=skill.begin();it!=skill.end();++it) cout<<it->first<<' '<<it->second<<endl;

return 0;
}

適当な EPS を足す,整数で処理するなどの誤差対策をしましょう。

B.
int n,a,lev[8],loy[8];

inline int popcount(int x){
x=((x>>1)&0x55555555)+(x&0x55555555);
x=((x>>2)&0x33333333)+(x&0x33333333);
x=((x>>4)+x)&0x0f0f0f0f;
x+=(x>>8);
x+=(x>>16);
return x&0x3f;
}

double dfs(int i,int k){
if(i==n){
// p0 : 投票で可決になる確率
// p1 : 投票で否決になりかつ kill できる確率
double p0=0,p1=0;
rep(S,1<<n){
// q : S だけが賛成する確率
double q=1;
int b=0;
rep(j,n){
if(S&(1<<j)) q*=loy[j]/100.0;
else q*=1-loy[j]/100.0, b+=lev[j];
}
if(2*popcount(S)>n) p0+=q;
else p1+=q*a/(a+b);
}

return p0+p1;
}

double ans=0;
// i 番目の senator に j 個の candy をあげる
rep(j,min(k,(100-loy[i])/10)+1){
loy[i]+=10*j;
ans=max(ans,dfs(i+1,k-j));
loy[i]-=10*j;
}
return ans;
}

int main(){
int k; scanf("%d%d%d",&n,&k,&a);
rep(i,n) scanf("%d%d",lev+i,loy+i);

printf("%.9f\n",dfs(0,k));

return 0;
}

まず、どの senator にいくつの candy をあげるかというのは全探索できる。
状態数は、重複組み合わせを使って nHk 個。

あげる candy を固定する。
このとき、求めたい確率 (意見が可決される確率) はいくらか?
これは、すべての根元事象にばらして考えればわかりやすい。
すなわち、各 senator が賛成,反対する場合を全通り調べればいい。
この部分の計算量は O(2n n)
文章で説明するのは大変なので、詳細はソースコード参照。

プログラム全体の計算量は O(nHk k + nHk 2n n) となる。

C. (時間外)
const string CLS[3]={"weapon","armor","orb"};
const string TYPE[3]={"gladiator","sentry","physician"};

struct Item{
string name,cls;
int prm,capa;
};

struct Resident{
string name,type,home;
int bonus;
};

int n,m;
Item itm[100];
Resident resi[1000];

bool can_move(){
int sum=0;
rep(i,n) sum+=itm[i].capa;
return m<sum;
}

vector<Item> listup(const string &cls){
vector<Item> ret;
rep(i,n) if(itm[i].cls==cls) ret.push_back(itm[i]);
return ret;
}

int k_cmp;
bool cmp(const Resident &r1,const Resident &r2){
int a1=(r1.type==TYPE[k_cmp]?r1.bonus:0);
int a2=(r2.type==TYPE[k_cmp]?r2.bonus:0);
return a1>a2;
}

void remove_resident(const string &name){
rep(i,m) if(resi[i].name==name) {
swap(resi[i],resi[m-1]);
m--;
break;
}
}

int main(){
cin>>n;
rep(i,n){
int dmy1,dmy2;
cin>>itm[i].name>>itm[i].cls;
if(itm[i].cls==CLS[0]) cin>>itm[i].prm>>dmy1>>dmy2;
if(itm[i].cls==CLS[1]) cin>>dmy1>>itm[i].prm>>dmy2;
if(itm[i].cls==CLS[2]) cin>>dmy1>>dmy2>>itm[i].prm;
cin>>itm[i].capa;
}
cin>>m;
rep(i,m) cin>>resi[i].name>>resi[i].type>>resi[i].bonus>>resi[i].home;

if(!can_move()){
rep(k,3){
int sum=-1;
string name;
vector<string> ls;
rep(i,n) if(itm[i].cls==CLS[k]) {
int _sum=itm[i].prm;
vector<string> _ls;
rep(j,m) if(resi[j].home==itm[i].name) {
int bonus=(resi[j].type==TYPE[k]?resi[j].bonus:0);
_sum+=bonus;
_ls.push_back(resi[j].name);
}
if(sum<_sum){
sum=_sum;
name=itm[i].name;
ls=_ls;
}
}

cout<<name<<' '<<ls.size();
rep(j,ls.size()) cout<<' '<<ls[j];
cout<<endl;
}

return 0;
}

int capa[3];
string name[3];
vector<string> ls[3];
rep(k,3){
k_cmp=k;
vector<Item> sub=listup(CLS[k]);

int sum=-1;
sort(resi,resi+m,cmp);
rep(i,sub.size()){
int _sum=sub[i].prm;
int _capa=sub[i].capa;
vector<string> _ls;
rep(j,min(m,_capa)){
int bonus=(resi[j].type==TYPE[k]?resi[j].bonus:0);
if(bonus==0) break;
_sum+=bonus;
_ls.push_back(resi[j].name);
}
if(sum<_sum){
sum=_sum;
capa[k]=_capa;
name[k]=sub[i].name;
ls[k]=_ls;
}
}

rep(i,ls[k].size()) remove_resident(ls[k][i]);
}

rep(k,3){
while(min(m,capa[k]-(int)ls[k].size())>0){
ls[k].push_back(resi[0].name);
remove_resident(resi[0].name);
}

cout<<name[k]<<' '<<ls[k].size();
rep(i,ls[k].size()) cout<<' '<<ls[k][i];
cout<<endl;
}

return 0;
}

まず、resident が 1 つも動かせない場合は例外処理しないといけない。

そうでないときは、少なくとも 1 つある空きスペースを使って自由に resident を移動させられる。
なので、weapon, armor, orb の順に、greedy に一番効率のいい resident を選んでいけばいい。

ただし注意点があって、
たとえば その item にとって価値のない resident は付加してはいけない。
その resident は、あとで決める item にとっては価値があるかもしれないから。

このように resident の行き先を決めた後、使わなかった resident を空き容量のある item に適当に詰め込む。
これはどのように詰め込んでもいい。
必ずすべての resident を詰め込めることは保障されている。 ( 問題文に書いてある )

やること 1 つ 1 つは単純だけど、実装がかなり重いと感じた。

D.


E.


感想

前回と同じく C から解こうと思っていたけど、問題文が長くて、大変な実装問題の予感がしたので、B から解き始めた。

B.
完璧な方針はすぐには見えなくて、試行錯誤しながらやっていった。
確率を求める部分の数式が間違っていてデバッグに時間をとられた。

A.
やや軽めの実装。
サンプルからやることが大体推測できる。

多くの例に漏れず、ふつうに書いたらふつうに誤差死した。
注意力が足りない。

C.
問題文長い。
実装重い。
A, B を解き終えてあと 50 分くらい余っていたので全力でコーディングしていた。
途中で A が Hack されたけど、無視して C を書き続けていた。
結局、もうちょっとのところで書きあがらなかったけど、書きあがっていても一部考え漏れがあったので WA だった。
この問題を 30 分かそこらで書いてくる人はすごいと思う。


やっとオレンジに復帰できた。
また紫に戻らないようにがんばる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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