Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1815-3fdc1619
この記事にトラックバックする(FC2ブログユーザー)

January 2011 Challenge 6問目 - Splitting Giant Subs (チャレンジ形式) (この記事を編集する[管理者用])

Source

codechef January 2011 Challenge 6問目 (チャレンジ形式)
Problem Statement
January 2011 Challengeの参加記録

問題概要

要素数N (1000以下) の整数列が与えられる.
各要素は1以上500以下で,同じ数字はちょうど偶数個だけ含まれている.
途中で分断して,奇数個目の塊をAに,偶数個目の塊をBに分けたとき,AとBに含まれる各数字の数を等しくしたい.
そのような分断の仕方を1つ求める問題.
スコアは,分断の数が小さいほうが良いスコア.

解法

各数字をAに分けるかBに分けるか決めて,隣接するのが違う方に分けなければいけない場所で分断すれば良い.
焼きなました.

C言語のスパゲッティなコード (スコア1743)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define RAND (rand()/(RAND_MAX+1.0))
#define LARGE_MAX 1
#define LOOP_MAX 160000

int N, MX;
int in[1001];

int go[2][501], all[501];

int res, *res_arr, res_mem[1111];
int tmp, *tmp_arr, tmp_mem[1111];

int edge[1001][1001], es[1001];

int main(){
  int i,j,k,l,br,loop,large;
  int now, add, ok;
  int size;
  double p, per, mul, ad;

  srand(time(NULL));
  res_arr = res_mem + 1;
  tmp_arr = tmp_mem + 1;

  scanf("%d",&size);
  while(size--){
    scanf("%d",&N);
    rep(i,N) scanf("%d",in+i);
    MX = in[0]; REP(i,1,N) if(MX < in[i]) MX = in[i];
    rep(i,N) in[i]--;

    rep(i,MX) go[0][i] = go[1][i] = all[i] = 0;
    rep(i,N) all[in[i]]++;

    res = 0; now = 0;
    rep(i,N){
      if(go[now][in[i]] >= all[in[i]]/2) res++, now^=1;
      go[now][in[i]]++; res_arr[i]=now;
    }
    res_arr[-1] = 0; res_arr[N] = 1;
    tmp_arr[-1] = 0; tmp_arr[N] = 1;

    tmp = res; rep(i,N) tmp_arr[i] = res_arr[i];
    rep(i,N) es[i]=0;
    rep(i,N) REP(j,i+1,N) if(in[i]==in[j]){
      edge[i][es[i]++] = j;
      edge[j][es[j]++] = i;
    }

    ad = LOOP_MAX * 0.5;
    mul = 1.0 / (LOOP_MAX + ad);
    rep(large,LARGE_MAX){
      rep(loop,LOOP_MAX){
        i = (int)(N * RAND);
        if(tmp_arr[i-1]==tmp_arr[i] && tmp_arr[i]==tmp_arr[i+1]) i=(int)(N * RAND);
        if(tmp_arr[i-1]==tmp_arr[i] && tmp_arr[i]==tmp_arr[i+1]) i=(int)(N * RAND);
        j = edge[i][(int)(es[i] * RAND)];
        if(tmp_arr[i] == tmp_arr[j]) j = edge[i][(int)(es[i] * RAND)];
        if(tmp_arr[i] == tmp_arr[j]) j = edge[i][(int)(es[i] * RAND)];
        if(tmp_arr[i] == tmp_arr[j]) continue;
        if(tmp_arr[j-1]==tmp_arr[j] && tmp_arr[j]==tmp_arr[j+1]) continue;
        if(i>j) k=i, i=j, j=k;

        add = 0;
        if(i+1==j){
          if(tmp_arr[i-1]==tmp_arr[i]) add++; else add--;
          if(j+1<N){
            if(tmp_arr[j+1]==tmp_arr[j]) add++; else add--;
          }
        } else {
          if(tmp_arr[i-1]==tmp_arr[i]) add++; else add--;
          if(i+1<N){
            if(tmp_arr[i+1]==tmp_arr[i]) add++; else add--;
          }
          if(tmp_arr[j-1]==tmp_arr[j]) add++; else add--;
          if(j+1<N){
            if(tmp_arr[j+1]==tmp_arr[j]) add++; else add--;
          }
        }

        if(add<0) ok=1; else {
          ok = 0;
          per = (loop+ad) * mul;
          p = exp( -(add*add+1) *2.5* per*per*per );
          if(p > RAND) ok = 1;
        }
        if(ok){
          k = tmp_arr[i]; tmp_arr[i]=tmp_arr[j]; tmp_arr[j] = k;
          tmp += add;
        }
        if(res > tmp){
          res = tmp;
          rep(i,N) res_arr[i] = tmp_arr[i];
        }

        if(loop%1000==621){
          res = tmp = 0;
          REP(i,1,N) if(res_arr[i-1]!=res_arr[i]) res++;
          REP(i,1,N) if(tmp_arr[i-1]!=tmp_arr[i]) tmp++;
        }
      }
    }

    res=0; REP(i,1,N) if(res_arr[i-1]!=res_arr[i]) res++;
    
    printf("%d\n",res); br=0;
    REP(i,1,N) if(res_arr[i-1]!=res_arr[i]){
      if(br)putchar(' '); else br=1;
      printf("%d",i); k++;
    }
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1815-3fdc1619
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。