Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Facebook Hacker Cup 2012 Round 1 2問目 - Recover the Sequence (この記事を編集する[管理者用])

Source

Facebook Hacker Cup 2012 Round 1 2問目

問題概要

とある1~N (Nは10000以下) のpermutation配列に対して,問題文中にあるマージソートのプログラムを動かした.
そのプログラムは,比較する際,どっちが大きいかで,1か2を出力している.
Nと出力結果だけが与えられた時,元々の置換を求める問題.

解法

1~Nが順番に並んでいる配列を,問題文と同じようにマージソートする.
その際,出力結果をみて,それと同じように大小関係を決める.
後は,そうやって得られた配列の対応関係を逆にすれば良い.(ソート結果がa[i] = kなら,b[k] = iにして,bが答え)

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

void normal_merge_sort(int arr[], int n);
void normal_merge(int arr1[], int n1, int arr2[], int n2);
void solve_merge_sort(int arr[], int n);
void solve_merge(int arr1[], int n1, int arr2[], int n2);
int checksum(int arr[], int n);

int res[100000], inv[100000];
int memory[100000];

char input[8000000]; int input_st;

int main(){
  int i,j,k,N;
  int sum;
  int size, count = 0;

  scanf("%d",&size);
  while(size--){
    scanf("%d%s",&N,input);
    input_st = 0;
    
    rep(i,N) res[i] = i;
    solve_merge_sort(res, N);

    rep(i,N) inv[res[i]] = i;
    rep(i,N) res[i] = inv[i]+1;

    sum = checksum(res,N);
/*    normal_merge_sort(res, N); puts("");*/
    printf("Case #%d: %d\n",++count,sum);
  }

  return 0;
}


void normal_merge_sort(int arr[], int n){
  int mid;
  
  if(n <= 1) return;
  mid = n/2;

  normal_merge_sort(arr, mid);
  normal_merge_sort(arr+mid, n-mid);
  normal_merge(arr, mid, arr+mid, n-mid);
}

void normal_merge(int arr1[], int n1, int arr2[], int n2){
  int i, size = 0;
  int st1 = 0, st2 = 0;

  while(st1 < n1 && st2 < n2){
    if(arr1[st1] < arr2[st2]){
      putchar('1');
      memory[size++] = arr1[st1++];
    } else {
      putchar('2');
      memory[size++] = arr2[st2++];
    }
  }

  while(st1 < n1) memory[size++] = arr1[st1++];
  while(st2 < n2) memory[size++] = arr2[st2++];
  rep(i,size) arr1[i] = memory[i];
}

void solve_merge_sort(int arr[], int n){
  int mid;
  
  if(n <= 1) return;
  mid = n/2;

  solve_merge_sort(arr, mid);
  solve_merge_sort(arr+mid, n-mid);
  solve_merge(arr, mid, arr+mid, n-mid);
}

void solve_merge(int arr1[], int n1, int arr2[], int n2){
  int i, size = 0;
  int st1 = 0, st2 = 0;

  while(st1 < n1 && st2 < n2){
    if(input[input_st++]=='1'){
      memory[size++] = arr1[st1++];
    } else {
      memory[size++] = arr2[st2++];
    }
  }

  while(st1 < n1) memory[size++] = arr1[st1++];
  while(st2 < n2) memory[size++] = arr2[st2++];
  rep(i,size) arr1[i] = memory[i];
}

int checksum(int arr[], int n){
  int i, res = 1;
  rep(i,n) res = (31 * res + arr[i]) % 1000003;
  return res;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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