スポンサーサイト

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

Codeforces Beta Round #19

JST 06/25 00:00~02:00 にweb上で行われたプログラミング競技、Codeforces Beta Round 第19回の参加記録です。

さぼってたら Codeforces の記録が 19, 21, 22 と 3 回分もたまってしまった。

問題と解答(の一部)は [ 続きを読む ] から。

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

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

A. World Football Cup
ワールドカップに参加した n チームの中から、決勝戦に進出する n/2 チームを次のルールにしたがって求めよ。
入力として、すべてのチームの対戦結果(nC2通り)が与えられる。
[ルール]
・ 勝ったチームには 3 点、引き分けは 1 点、負けは 0 点の "スコア" が加算される。
・ チームを "スコア" の高い順に並べたときの、上位 n/2 チームが決勝戦進出。
― ただし、 "スコア" が同じであれば "ゴール数 - 被ゴール数" の高い順に並べる。
― ただし、 "スコア" と "ゴール数 - 被ゴール数" が同じであれば "ゴール数" の高い順に並べる。

B. Checkout Assistant
Bob の買い物かごには n 個の商品が入っている。また、それらの価格・レジ打ちにかかる秒数がわかっている。
Bob は、店員がレジ打ちをしている間、1 秒につき 1 つの商品をくすねることができる。
最適な手順を踏んだ場合に、Bob が払わなければならない金額の最小値はいくらか?

C. Deletion of Repeats
D. Points
E. Fairy
問題読んでない。いつか読む。


[ 解答 ]
言語は C++。include文とusing文は省略。
追記した分はテンプレを使っている。テンプレはここを参照。

A.
int match(char **name,int n,char *data)
{
for(int i=0;i<n;i++) if(strcmp(name[i],data)==0) return i;
return 0; // unexecuted
}

int main()
{
int n; scanf("%d",&n);
char _name[50][32];
char *name[50];
char data1[50][50][2][64];
int data2[50][50][2];
for(int i=0;i<n;i++){
scanf("%s",_name[i]);
name[i]=_name[i];
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
scanf("%s %d:%d",data1[i][j][0],&data2[i][j][0],&data2[i][j][1]);

int k; // split
for(k=0;k<strlen(data1[i][j][0]);k++){
if(data1[i][j][0][k]=='-') break;
}
data1[i][j][0][k]='\0';
strcpy(data1[i][j][1],&data1[i][j][0][k+1]);
}
}

int score[50]={0},diff[50]={0},goal[50]={0};
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int s1,s2;
s1=match(name,n,data1[i][j][0]);
s2=match(name,n,data1[i][j][1]);

int sc[2]={data2[i][j][0],data2[i][j][1]};
if(sc[0]>sc[1]) score[s1]+=3;
else if(sc[0]==sc[1]) score[s1]++,score[s2]++;
else score[s2]+=3;
diff[s1]+=(sc[0]-sc[1]);
diff[s2]+=(sc[1]-sc[0]);
goal[s1]+=sc[0];
goal[s2]+=sc[1];
}
}

for(int i=0;i<n;i++){ // bubble sort
for(int j=0;j<n-i-1;j++){
if(score[j]<score[j+1]
||(score[j]==score[j+1] && diff[j]<diff[j+1])
||(score[j]==score[j+1] && diff[j]==diff[j+1] && goal[j]<goal[j+1])){
// swap j,j+1
swap(name[j],name[j+1]);
swap(score[j],score[j+1]);
swap(diff[j],diff[j+1]);
swap(goal[j],goal[j+1]);
}
}
}

vector<string> v;
for(int i=0;i<n/2;i++) v.push_back(name[i]);
sort(v.begin(),v.end());
for(int i=0;i<n/2;i++) cout<<v[i]<<endl;

return 0;
}

今回解けたのはこの1問だけです。題意がなかなかつかめず苦労しました。
問題文どおりに書くだけなんですが、こまごまとしたことを色々とやらないといけないので、凡ミス連発。
7WA, 2TLE を経て Accept できたときには競技終了 4 分前でした。

ソースコードの説明を簡単にしておきます。

ソースは大きく 3 つの部分に分かれます。
・データ入力
入力データのフォーマットは元の問題文を見てもらえばいいのですが、少々めんどうな形になっているので、それを整形する処理(ハイフンを境に文字列を分離)をしています。

・ スコア計算
各チームについて、スコア(score), ゴール数 - 被ゴール数(diff), ゴール数(goal)を計算しています。
入力される試合結果のデータはチーム名の順番になっていないので、そのチームが配列の何番目にいるかを match() で求めています。

・ ソート
問題文の条件に従ってソートします。データ数が多くないのでバブルソートで実装しました。

A問題なのに随分長いコードになりました。うまくすれば、まだまだ短く書けると思います。

B. (時間外)
const ll INF=1LL<<61;

int main(){
int n,t[2000]; scanf("%d",&n);
ll cost[2000];
rep(i,n){ scanf("%d%I64d",t+i,cost+i); t[i]++; }

static ll dp[2001][2001];
fill(dp[0]+1,dp[0]+n+1,INF);
rep(i,n)rep(j,n+1){
if(j<t[i]) dp[i+1][j]=min(dp[i][j],cost[i]);
else dp[i+1][j]=min(dp[i][j],dp[i][j-t[i]]+cost[i]);
}

printf("%I64d\n",dp[n][n]);

return 0;
}

[ 2011/03/21 追記 ]

分からなかったので WJMZBMR さんの解説を見ながら解いた。
この問題かなり難しいんじゃないか? と思っていたら、やっぱり NP-hard だった。
ただし、入力される数値が小さいので擬多項式時間の DP で解ける。

まず、すべての ti に 1 を加える。
そうすると、選んだ ti の総和が n 以上になるような商品の部分集合 S が、買う商品の部分集合に一致する。
( つまり、S に含まれない商品をくすねる時間があるということ )
+1 する操作は、その商品自体を選ぶ分をさっ引いていることに相当する。

このことに気付けば、あとは 0-1 ナップサック問題のような DP で解ける。
ただし、ナップサック問題の目的が
ある容量以下で商品の価値の合計を最大化する
ことであるのに対して、今回の DP は
ある容量以上で商品を価値の合計を最小化する
ことが目的。

dp[i][j] は i-1 番目までの商品を使って j 秒以上の時間を確保するときの最小価値。

分かりやすさのために O(n2) のメモリを確保したけど、2 つめのループを逆に回せば O(n) のメモリでも解ける。
いずれにせよ、時間計算量は O(n2).

C. 以降は未完成です。でき次第、追記します。

Rating は 15041430
うーん...
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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