スポンサーサイト

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

CodeChef July Cook-Off

2011/07/25 01:00 ~ 03:30 (JST)
CodeChef July Cook-Off の参加記録

自分にしてはよくできた。

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

結果

問題を、問題ページの上から順に A, B, .. と呼ぶことにする。
A. -
B. 2WA, AC (01:24:45)
C. WA, AC (00:24:05)
D. -
E. AC (00:37:12)
Standing : 25/341
Rank (Short) : 52 → 39
Rating (Short) : 1313.323 → 1363.202


問題

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

A.

B. Pleasing Chef
n 個の商品と k 枚のクーポン券がある。
クーポン券には 1 ~ 100 の整数 c が書かれていて、商品の値段を c % にすることができる。

n 個の中から等確率で k 個の商品を選び、各商品に対してクーポン券を 1 枚ずつ使う。
このとき、合計金額がもっとも安くなるようにクーポン券を割り当てる。

合計金額の期待値を求めよ。

1 ≦ k ≦ n ≦ 1000

C. Garden Squares
n × m のグリッドがあり、各マスにはアルファベットが割り当てられている。

四隅に同じアルファベットがくるような正方形はいくつあるか?

1 ≦ n, m ≦ 50

D. Mean Mean Medians
n 個の整数 a1, ..., an が与えられる。
この中から k 個を選んで、それらの中央値と平均の差を最小化せよ。

ここで、中央値とは、小さい順に並べたときに floor((k+1)/2) 番目にくる値のことをいう。

1 ≦ k ≦ n ≦ 60
1 ≦ ai ≦ 1200

E. Misinterpretation
アルファベット小文字からなる長さ n の文字列で、次の操作に関して不変なものの個数を求めよ。

[ 操作 ]
偶数番目の文字をそのままの順序で先頭にもってくる。
奇数番目の文字をそのままの順序で後ろにつなげる。

たとえば、abcdef であれば bdface となる。

解答

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

A.


B.
int main(){
const int Nb=1000;
static double nCr[Nb+1][Nb+1]={}; rep(n,Nb+1) nCr[n][0]=1;
rep(n,Nb) rep(r,n+1) nCr[n+1][r+1]=nCr[n][r+1]+nCr[n][r];

int T; scanf("%d",&T);
while(T--){
int n,k; scanf("%d%d",&n,&k);
int price[1000];
double coupon[1000];
rep(i,n) scanf("%d",price+i);
rep(j,k) scanf("%lf",coupon+j), coupon[j]/=100;

sort(price,price+n);
sort(coupon,coupon+k);

double ans=0;
rep(i,n) for(int j=max(0,k-n+i);j<k&&j<=i;j++) {
double coef=nCr[i][j]*nCr[n-i-1][k-j-1];
ans+=coef*price[i]*coupon[j];
}
ans/=nCr[n][k];
printf("%.3f\n",ans);
}

return 0;
}

商品は値段の昇順に、クーポンは割引率の昇順にソートされているとする。

k 個の商品を固定したとき、高額の商品に割引率が高いクーポン券を割り当てるのが最適。
これは明らか。

なので、答えは
( Σn 個から k 個を選ぶすべての場合Σi=1 to ki 番目の商品の値段 × 対応するクーポンの割引率 ) / nCk
となる。

もちろん、これをそのまま計算すると終わらないので、次のように書き換えてみる。
( Σi = 1 to nΣj=1 to kA(i,j) × 商品 i の値段 × クーポン j の割引率 ) / nCk
ここで、 A(i,j) は i, j で決まる係数。

A(i,j) はいくつか?
クーポン j を商品 i に割り当てるのだから、
  • 商品 1, 2, ..., i-1 にはクーポン 1, 2, ..., j-1 の中から i-1 個を割り当てる。
    割り当て方は i-1Cj-1 通り。

  • 商品 i+1, i+2, ..., n にはクーポン j+1, j+2, ..., k の中から n-i 個を割り当てる。
    割り当て方は n-iCn-j 通り。
    • なので、
      A(i,j) = i-1Cj-1 × n-iCn-j
      となる。

      これで、O(nk) で答えが計算できる。
      そのままだと TLE したけど、j のループ範囲を微妙に削ったら間に合った。

      普通に
      dp[i][j] := 商品 i, クーポン j まで見たときの期待値
      で DP することもできるらしい。

      C.
      int main(){
      int T; scanf("%d",&T);
      while(T--){
      int m,n; scanf("%d%d",&m,&n);
      char g[50][51];
      rep(i,m) scanf("%s",g[i]);

      int ans=0;
      rep(i,m) rep(j,n) for(int d=1;i+d<m&&j+d<n;d++) {
      char c=g[i][j];
      if(g[i][j+d]==c && g[i+d][j]==c && g[i+d][j+d]==c) ans++;
      }
      printf("%d\n",ans);
      }

      return 0;
      }

      全探索。
      最初、正方形ではなく長方形を探していて WA をもらってしまった。

      D. (時間外)
      int n,k,a[60];

      int dp[36001]; // dp[j] : i bit目は i 個の和で j が作れるかどうかを表す
      int nl[61],l[61][36001]; // l[i][j] := 左から a[i] までを使って m 個の和として書ける j 番目の数
      int nr[61],r[61][36001]; // r[i][j] := 右から a[i] までを使って m 個の和として書ける j 番目の数

      void precalc(){
      int m,Omega,sum=accumulate(a+n-k/2,a+n,0);

      m=(k-1)/2; Omega=(1<<(m+1))-1;
      memset(dp,0,sizeof dp);
      dp[0]=1;
      rep(i,n){
      for(int j=sum-a[i];j>=0;j--){
      dp[j+a[i]]|=(dp[j]<<1)&Omega;
      }

      nl[i]=0;
      rep(j,sum+1) if(dp[j]&(1<<m)) l[i][nl[i]++]=j;
      }

      m=k/2; Omega=(1<<(m+1))-1;
      memset(dp,0,sizeof dp);
      dp[0]=1;
      for(int i=n-1;i>=0;i--){
      for(int j=sum-a[i];j>=0;j--){
      dp[j+a[i]]|=(dp[j]<<1)&Omega;
      }

      nr[i]=0;
      rep(j,sum+1) if(dp[j]&(1<<m)) r[i][nr[i]++]=j;
      }
      }

      int nearest(const int *a,int sz,int tar){
      int idx=lower_bound(a,a+sz,tar)-a;
      if(idx==sz) return a[sz-1];
      if(idx==0) return a[0];

      return abs(a[idx-1]-tar)<abs(a[idx]-tar)?a[idx-1]:a[idx];
      }

      int main(){
      int T; scanf("%d",&T);
      while(T--){
      scanf("%d%d",&n,&k);
      rep(i,n) scanf("%d",a+i);
      sort(a,a+n);

      if(k==1){ puts("0"); continue; }
      if(k==2){
      int ans=1<<29;
      rep(j,n) rep(i,j) ans=min(ans,abs(2*a[i]-(a[i]+a[j])));
      printf("%.3f\n",ans/2.0);
      continue;
      }

      precalc();

      int ans=1<<29;
      for(int i=(k-1)/2;n-i>k/2;i++){
      int k_med=k*a[i]; // k times median

      rep(j,nl[i-1]){
      int L=l[i-1][j];
      int R=nearest(r[i+1],nr[i+1],k_med-(L+a[i]));
      int k_mean=L+a[i]+R; // k times mean
      ans=min(ans,abs(k_mean-k_med));
      }
      }

      printf("%.3f\n",(double)ans/k);
      }

      return 0;
      }

      Editorials を見ながら解いた。
      コンテスト中に考えていた方針と大体同じだったので嬉しい。

      median の値は n 通り以下しかないので、各 median に対して、ナップザック DP 的な手法で一番近い mean を求める。

      DP をする際、その数が作れるかどうかを bit で管理することで高速化できる。
      これをしないと TLE になる。

      いきなりこれを書くのは難しかったので、
      bool dp[i][j] := i 個の和で j が作れるかどうか
      という DP を一旦書いて、それを bit で並列化するようにした。

      O(nS) (S = Σai) で解けるらしいけど、
      自分のコードは DP で得た和を組み合わせるところを二分探索でやってるので O(n S log S) かかっている。

      これでもまだ TLE したけど、最後のだめ押しで
      sum = accumulate(a, a+n, 0);

      sum = accumulate(a+n-k/2, a+n, 0);
      と書き換えるとようやく間に合うようになった。
      k/2 個程度の和を考えているのだから、上限は ai の大きいほうから k/2 個の和で十分、ということ。

      E.
      const ll M=1000000007;

      class UnionFind{
      vector<int> a;
      public:
      UnionFind(int n):a(n,-1){}
      int find(int x){
      if(a[x]<0) return x;
      return a[x]=find(a[x]);
      }
      void unite(int x,int y){
      x=find(x),y=find(y);
      if(x!=y){ a[x]+=a[y]; a[y]=x; }
      }
      int size(int x){ return -a[find(x)]; }
      };

      int main(){
      int T; scanf("%d",&T);
      while(T--){
      int n; scanf("%d",&n);
      static int a[100000],b[100000];
      rep(i,n) a[i]=i;
      for(int i=1;i<n;i+=2) b[i/2]=a[i];
      for(int i=0;i<n;i+=2) b[i/2+n/2]=a[i];

      UnionFind uf(n);
      rep(i,n) uf.unite(a[i],b[i]);

      ll ans=1;
      static bool checked[100000];
      memset(checked,0,sizeof checked);
      rep(i,n){
      int id=uf.find(i);
      if(!checked[id]){
      ans=ans*26%M;
      checked[id]=true;
      }
      }
      printf("%lld\n",ans);
      }

      return 0;
      }

      具体例で説明するのがよいと思う。

      n=5 のときでやる。

      文字列を a1 a2 a3 a4 a5 とおく。
      これに操作を施すと
      a2 a4 a1 a3 a5
      となる。

      これらが等しいのだから
      a1 = a2
      a2 = a4
      a3 = a1
      a4 = a3
      a5 = a5
      という n 個の式ができる。

      まとめると、
      a1 = a2 = a3 = a4
      a5 = a5
      という 2 つのグループができる。

      a1 と a5 には好きな文字を割り当てることができるので、答えは 262.

      これと同じことを一般の n でやればいい。
      Union-Find を使った。
      スポンサーサイト

コメントの投稿

非公開コメント

はじめまして

はじめまして。

Bを似たような方針で考えたのですが、オーバーフローしないのですね。オーバーフローする!と思って組まなかったので、実際には組んでみると良かったのかも知れません。参考にさせていただいて、自分で取り組んでみます。

C、同じミスをしていました(正方形と長方形の間違い)。squareを四角だと思っていたのです(英辞郎だと「四角・正方形」と書いてあったので…)。でも、長方形ならrectangleを使うよな、といまさらながらです。

Re: はじめまして

はじめまして。

私も B はオーバーフローするかもと思いながら submit したので、通ったのはラッキーでした。
Editorials に書いてある DP 解法だとその心配はないようですね。
プロフィール

fura2

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

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

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