スポンサーサイト

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

Codeforces Beta Round #37

JST 10/26 00:00~02:00 に行われた Codeforces 第37回の記録です。

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

[ 結果 ]
A. 462(AC)
B. 752(AC)
C. 904(WA,AC)
D. -
E. -
Hack 1 miss
Standing 108/904
Rating 14541626

[ 問題 ]
今回の問題セットはこんな感じでした。

A. Towers
(やや意訳)
長さがまちまちな N 個の積み木が与えられる。すべての積み木は高さ 1 である。
同じ長さの積み木は合体させることができる。合体した積み木は1つの積み木とみなし、高さが 1 増える。
何回かの合体を行い、積み木の数を最小にするとき、積み木の数と積み木の高さの最大値を求める。
1≦ N ≦ 1000, 1 ≦ (各積み木の長さ) ≦ 1000

B. Computer Game
あるゲームにおけるボス戦をシミュレートする。

プレイヤーは N (≦1000) 本の巻物を使ってボスを攻撃する。各巻物は一度しか使えず、また使用条件がある。
[巻物の詳細]
各巻物には pow と dmg の2つのパラメータが設定されている。
pow は 1~100 の整数値であり、ボスのHPが pow[%] 以下であるときにのみ発動可能。
dmg は 1~2000 の整数値であり、ボスに与えるダメージ量を意味する。
巻物は1ターンに高々1本しか使えない。

ゲームはターン制で行われる。ターンは 0 からカウントされる。
[ターンの流れ]
1. ボスは、「すでに発動している巻物の dmg の合計」ポイントのHPを削られる。
2. ボスは、reg (≦1000) ポイントのHPを回復する。ボスのHPは max (≦1000) より大きくならない。
3. ボスのHPが0または負であれば、プレイヤーの勝利。
4. プレイヤーは(発動条件をみたす)巻物を1つ選び、発動することができる。

プレイヤーが最適な戦略をとったとき、ボスを倒すのに必要なターン数と使用した巻物を答える。
与えられた条件下でボスが倒せないときは、それを指摘する。

C. Old Berland Language
0と1だけからなる文字列が N (≦1000) 個ある。
それぞれの文字列の長さ (≦1000) が与えられる。
このとき、「どの文字列も他の文字列の接頭辞になっていないような文字列の組」が構成できるかどうかを答える。構成できる場合は具体例も1つ答える。

D. Lesson Timetable
未読

E. Trial for Chief
未読

[ 解答 ]
言語は C++。include文とusing文は省略。

A.
int main()
{
int n,buc[1001]={}; cin>>n;
for(int i=0;i<n;i++){
int t; cin>>t;
buc[t]++;
}

int tower=0,hmax=0;
for(int i=0;i<=1000;i++){
if(buc[i]>=1) tower++;
hmax=max(hmax,buc[i]);
}

cout<<hmax<<' '<<tower<<endl;

return 0;
}

はじめ、何を血迷ったか、長さをsortして隣接要素を調べることでカウントしていく方法を取ろうとしてしまった。
長さの最大値(=1000)まで入る配列を用意してやって、計数ソートっぽいやりかたでできる。O(N).

B.
typedef pair<int,int>   pii;

int main()
{
int n,maxhp,reg; cin>>n>>maxhp>>reg;
pii scr[1000];
bool used[1000]={};
for(int i=0;i<n;i++) cin>>scr[i].pwr>>scr[i].dmg;

bool suc;
int hp=maxhp,bossdmg=0,t;
vector<pii> res;
for(t=0;;t++){
int dmgmax=0,imax=-1;
for(int i=0;i<n;i++){
if(!used[i] && 100.*hp/maxhp<=scr[i].pwr){
if(dmgmax<scr[i].dmg) dmgmax=scr[i].dmg,imax=i;
}
}
if(~imax){
bossdmg+=scr[imax].dmg;
used[imax]=true;
res.pb(mp(t,imax+1));
}
if(hp==maxhp && imax==-1){
suc=false;
break;
}
hp-=bossdmg;
hp=min(hp+reg,maxhp);
if(hp<=0){
suc=true;
break;
}
}

if(suc){
cout<<"YES"<<endl;
cout<<t+1<<' '<<res.size()<<endl;
for(int i=0;i<res.size();i++) cout<<res[i].first<<' '<<res[i].second<<endl;
}
else cout<<"NO"<<endl;

return 0;
}

コーディングより、問題を読解するほうが難しい。
使える巻物の中でdmgが一番大きいものを選んで使っていけばいい。greedy.
コード中でのターンの流れが↑に書いた和訳と微妙に違っていて、その分を出力のときに+1して帳尻合わせたりしてるけど Accepted もらえたので気にしない。
ボスが倒せないと判断するための条件は、"ボスのHPが最大 かつ そのターンに巻物を使っていない" とした。

C.
typedef pair<int,int>   pii;

bool makeNextCode(string &s)
{
int len=s.length();
for(int i=len-1;i>=0;i--){
if(s[i]=='0'){
s[i]='1';
return true;
}
else s[i]='0';
}
return false;
}

int main()
{
int n,l[1000]; cin>>n;
pii info[1000];
string s[1000];
for(int i=0;i<n;i++) cin>>l[i],info[i]=mp(l[i],i);

sort(l,l+n);
sort(info,info+n);

bool ok=true;
for(int i=0;i<l[0];i++) s[0]+='0';
for(int i=1;i<n;i++){
s[i]=s[i-1];
if(!makeNextCode(s[i])){
ok=false;
break;
}
for(int j=l[i-1];j<l[i];j++) s[i]+='0';
}

string res[1000];
for(int i=0;i<n;i++) res[info[i].second]=s[i];

if(!ok) cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
for(int i=0;i<n;i++) cout<<res[i]<<endl;
}

return 0;
}

「文字列は与えられた文字列長の順に出力する」ということを見逃していて、1WAをもらった。

まず文字列長でsortして、短いものから順に確定させていく。
000..00
からはじめて、
000..01
000..10
と構成していく。
文字列が長くなったら、その分は 0 で埋めて、また同じことをくり返す。
111..11
の次が必要になってしまったら、これ以上は構成不可能なので NO を出力する。

たとえば、与えられた文字列長が
2 2 3 3 5
だと
00
01
100
101
11000
となる。

D.


まだやってない。

E.


まだやってない。

D. E. も解け次第 追記予定。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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