スポンサーサイト

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

Codeforces Round #100

2011/01/05 00:00~02:00 (JST)
Codeforces Round #100 の参加記録

100 回記念で、上位 100 人は T シャツがもらえる。

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

結果

A. WA, AC (00:20)
B. 3WA, AC (01:39)
C. WA, AC (00:35)
D. AC (01:31)
E. -
F. -
Standing : 236/2821
Rating : 20242043


問題

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

A. New Year Table

半径 R の円形のテーブルがある。
テーブルの上に n 枚の皿を載せる。
皿は半径 r の円形。
皿は重ならないように、かつテーブルの縁に接するように配置したい。 ( 接してもいい )
所望の配置が可能かどうか判定せよ。

1 ≦ n ≦ 100
1 ≦ r, R ≦ 1000

B. New Year Cards

Alex には n 人の友人がいる。
各友人は年賀状を 1 枚ずつ Alex に送ってくる。
送られてくるタイミングはばらばら。

Alex は友人たちに年賀状をメールで送りたい。
Alex は友人から来た年賀状をコピーして別の友人に送る作戦をとる。

Alex と各友人には、n 種類の年賀状に対して好きである度合いがある。

Alex は次のルールに従って送る年賀状を選ぶ。
1. 年賀状を送ってきた友人には同じ年賀状を返さない。
2. 1. に該当しない年賀状のなかで、Alex が一番好きなものを選ぶ。

各友人に年賀状を送るタイミングはいつでもいい。

どのタイミングで年賀状を送れば、各友人の受け取る年賀状の好きの度合いを最大化できるか?

2 ≦ n ≦ 300

C. New Year Snowmen

n 個の雪球がある。
半径の相異なる雪球を 3 つ選んで雪だるまを作る。
最大いくつの雪だるまが作れるか?

1 ≦ n ≦ 10^5

D. New Year Contest

tourist が年越しコンテストに参加する。
問題は n 問ある。
コンテスト時間は 12/31 18:00 ~ 1/1 6:00.

tourist は Wrong Answer を出さない。
提出時間によって決まるペナルティがあり、その値は 0:00 から離れた分数に等しい。

tourist は以下の戦略をとる。
最初の 10 分ですべての問題を読み、解くのにかかる時間を特定する。
以降、Accepted 数を最大化し、かつそうした上でペナルティの合計を最小化するような順序で問題を解く。

問題を解いても提出せずに、あとで一気に提出することは可能。
なお、提出にかかる時間は無視できる。

Accepted 数とペナルティの合計を求めよ。

1 ≦ n ≦ 100

解答

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

A.
const double PI=acos(-1);
const double EPS=1e-9;

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

bool ok;
if ( r >R) ok=false;
else if(2*r>R) ok=(n==1);
else{
double theta=asin((double)r/(R-r));
ok=(n<=(int)(PI/theta+EPS));
}

puts(ok?"YES":"NO");

return 0;
}

図を描いてみればわかるように、大きい円の中心から小さい円に接線を 2 本引いたときの接線間の角度がわかればいい。
( と簡単に言ってるけど、気付くのに結構時間がかかった )

この角度は逆三角関数を使えばすぐに出せる。

誤差で落ちまくると思っていたので Hack に挑戦してみたけど、手元と Cf サーバで実行結果が違って落ちなかった。悲しい。
実際は pretest が強かったらしい。

B.
int main(){
int n; scanf("%d",&n);
int fr[300][300];
rep(i,n) rep(j,n) scanf("%d",fr[i]+j), fr[i][j]--;
int rank[300];
rep(i,n){
int a; scanf("%d",&a), a--;
rank[a]=i;
}

int ans[300],sendrank[300];
rep(i,n) sendrank[i]=n;
rep(i,n){ // カード i をもらう
rep(j,n){ // 友人 j に送る
// カード c を送る
int c=-1;
rep(k,i+1) if(k!=j && (c==-1 || rank[k]<rank[c])) c=k;
if(c==-1) continue; // 送れるカードがない

int r;
for(r=0;r<n;r++) if(fr[j][r]==c) break;
if(r<sendrank[j]){
ans[j]=i;
sendrank[j]=r;
}
}
}

rep(j,n) printf("%d%c",ans[j]+1,j<n-1?' ':'\n');

return 0;
}

問題文が難解すぎたので clar で訊きまくった。

読解できれば、全部のタイミングを試すだけ。

C.
struct snowball{
int num,size;
bool operator<(const snowball &sb)const{ return num<sb.num; }
};

struct triple{ int a,b,c; };

int main(){
int n; scanf("%d",&n);
static int a[100000];
rep(i,n) scanf("%d",a+i);
sort(a,a+n);

priority_queue<snowball> Q;
for(int i=1,pre=a[0],cnt=1;i<=n;i++){
if(i<n && a[i]==pre) cnt++;
else{
Q.push((snowball){cnt,pre});
cnt=1;
if(i<n) pre=a[i];
}
}

vector<triple> ans;
while(Q.size()>=3){
snowball sb[3];
rep(i,3) sb[i]=Q.top(), Q.pop();

ans.push_back((triple){sb[0].size,sb[1].size,sb[2].size});

rep(i,3){
sb[i].num--;
if(sb[i].num>0) Q.push(sb[i]);
}
}

printf("%d\n",ans.size());
rep(i,ans.size()){
int v[]={ans[i].a,ans[i].b,ans[i].c};
sort(v,v+3,greater<int>());
printf("%d %d %d\n",v[0],v[1],v[2]);
}

return 0;
}

各半径の雪だまが何個あるかをカウントして、多いものから貪欲に使っていく。
priority_queue で O(n log n).

直感的には正しいけど、コンテスト中は証明できなかった。
Editorial の証明の要約を書いておく。
  1. 最大 k 個の雪玉が作れるとする
  2. 同じサイズの雪玉が k 個より多くあっても意味がないので、同じサイズの雪玉は k 個以下と仮定
    この仮定によりアルゴリズムの挙動は変化しない
  3. 1. より、雪玉の合計個数は 3k 以上なのは明らか
  4. 2. と 3. より、異なるサイズの雪玉が 3 種類以上存在 ( 鳩ノ巣原理 )
  5. "同じサイズ k 個" が 3 セット以上あるとき、明らかにアルゴリズムは正しい答えを出す
  6. "同じサイズ k 個" が 3 セット未満のとき、4. より、アルゴリズムは少なくとも 1 ステップ進められる
  7. 1 ステップ進めると、同じサイズの雪玉は k-1 個以下、雪玉の合計個数は 3(k-1) 以上という状況になるので、帰納的に続けられる

別解として、Editorial の Solution 1 がおもしろい。
- 答えを決めうちして二分探索。
- サイズ k の解があるかの判定は、k 個より多く重複した分を切ってしまったときに 3k 個以上の雪球が残っているか?
- ソートして、k 個おきに 3 つずつとっていくことで解が構成できることから、正しさが証明できる。

D.
int main(){
int n; scanf("%d",&n);
int a[100];
rep(i,n) scanf("%d",a+i);

sort(a,a+n);

int b[100],t=10;
rep(i,n){
b[i]=t+a[i];
t+=a[i];
}

int cnt=0,pena=0;
rep(i,n) if(b[i]<=720) cnt++, pena+=max(b[i]-360,0);
printf("%d %d\n",cnt,pena);

return 0;
}

短い時間で解ける問題から順に解いていくのが最適。
0:00 より前に解き終わった問題はストックしておいて、0:00 にまとめて出す。

証明は、たとえば UTPC 2011 ファーストアクセプタンス と同じ感じでできると思う。
( ちゃんと考えてない )
Editorial にちゃんとしたものが載ってる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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