Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #75 DIV1 D問題 - Grocer's Problem (この記事を編集する[管理者用])

Source

Codeforces Beta Round #72 DIV1 D問題 (2500pt)
Problem description

問題概要

1~Nのpermutationが与えられる.Nは10^5以下.
一度に,5つ以下の要素を選んで,それらを自由に入れ替えることができる.
ソートするまでの最小手数と,その手順を1つ求める問題.

解法

Greedy.
まず,巡回置換の積に直す.
巡回置換で,要素が5より大きいものは,1回の操作で4つだけ正しい場所において,残りはそのままにできる.
後は,巡回置換で,サイズが5以下のものだけ考える.
5のもの,4のものは,1回の操作で行うしか無い.
後は,2のもの,3のものが両方あるうちは,1回の操作で,それらを1個ずつ潰していく.
3のものが3つ以上あれば,3つは,
 1回目: 1つ潰して,1つをスワップしてサイズ2の置換に落とす
 2回目: 1つ潰して,サイズ2の置換に落としたのも潰す
と2回の操作で潰す.
2のものが2個以上あったら,2個を1回の操作で潰す.
後は,サイズ2のもの,3のものが余ってたら潰す.

C言語のスパゲッティなコード
#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)

int in[120000], used[120000];
int cyc2[120000][7], cyc2_size;
int cyc3[120000][7], cyc3_size;

int now[120000], now_len;

int resA[120000][7], resB[120000][7], res_len[120000], res_size;

void proc(int now[], int now_len){
  int i,j,k;

  if(now_len==1) return;

  if(now_len==2){
    rep(i,2) cyc2[cyc2_size][i] = now[i];
    cyc2_size++;
    return;
  }
  
  if(now_len==3){
    rep(i,3) cyc3[cyc3_size][i] = now[i];
    cyc3_size++;
    return;
  }
  
  if(now_len==4 || now_len==5){
    res_len[res_size] = now_len;
    rep(i,now_len) resA[res_size][i] = now[i];
    rep(i,now_len) resB[res_size][i] = now[(i+1)%now_len];
    res_size++;
    return;
  }

  res_len[res_size] = 5;
  rep(i,5) resA[res_size][i] = now[i];
  rep(i,5) resB[res_size][(i+4)%5] = now[i];
  now[4]=now[0];
  res_size++;

  proc(now+4, now_len-4);
}

int main(){
  int i,j,k,l,m,n;
  int start;

  while(scanf("%d",&n)==1){
    rep(i,n) scanf("%d",in+i);
    rep(i,n) used[i] = 0;
    rep(i,n) in[i]--;

    cyc2_size = cyc3_size = res_size = 0;

    rep(start,n) if(!used[start]){
      now_len = 0;
      k = start;
      while(!used[k]){
        now[now_len++] = k;
        used[k] = 1;
        k = in[k];
      }

      proc(now,now_len);
    }

    while(cyc2_size && cyc3_size){
      res_len[res_size] = 5;
      rep(i,2) resA[res_size][i  ] = cyc2[cyc2_size-1][ i     ];
      rep(i,2) resB[res_size][i  ] = cyc2[cyc2_size-1][(i+1)%2];
      rep(i,3) resA[res_size][i+2] = cyc3[cyc3_size-1][ i     ];
      rep(i,3) resB[res_size][i+2] = cyc3[cyc3_size-1][(i+1)%3];
      res_size++;
      cyc2_size--; cyc3_size--;
    }

    while(cyc3_size>=3){
      res_len[res_size  ] = 5;
      rep(i,3) resA[res_size  ][i  ] = cyc3[cyc3_size-1][ i     ];
      rep(i,3) resB[res_size  ][i  ] = cyc3[cyc3_size-1][(i+1)%3];
      cyc3_size--;

      res_len[res_size+1] = 5;
      rep(i,3) resA[res_size+1][i  ] = cyc3[cyc3_size-1][ i     ];
      rep(i,3) resB[res_size+1][i  ] = cyc3[cyc3_size-1][(i+1)%3];
      cyc3_size--;

      resA[res_size  ][3] = cyc3[cyc3_size-1][0]; resA[res_size  ][4] = cyc3[cyc3_size-1][1];
      resB[res_size  ][3] = cyc3[cyc3_size-1][1]; resB[res_size  ][4] = cyc3[cyc3_size-1][0];
      resA[res_size+1][3] = cyc3[cyc3_size-1][0]; resA[res_size+1][4] = cyc3[cyc3_size-1][2];
      resB[res_size+1][3] = cyc3[cyc3_size-1][2]; resB[res_size+1][4] = cyc3[cyc3_size-1][0];
      cyc3_size--;

      res_size+=2;
    }

    while(cyc2_size>=2){
      res_len[res_size] = 4;
      rep(i,2) resA[res_size][i  ] = cyc2[cyc2_size-1][ i     ];
      rep(i,2) resB[res_size][i  ] = cyc2[cyc2_size-1][(i+1)%2];
      cyc2_size--;
      rep(i,2) resA[res_size][i+2] = cyc2[cyc2_size-1][ i     ];
      rep(i,2) resB[res_size][i+2] = cyc2[cyc2_size-1][(i+1)%2];
      cyc2_size--;
      res_size++;
    }

    while(cyc2_size){
      res_len[res_size] = 2;
      rep(i,2) resA[res_size][i  ] = cyc2[cyc2_size-1][ i     ];
      rep(i,2) resB[res_size][i  ] = cyc2[cyc2_size-1][(i+1)%2];
      res_size++;
      cyc2_size--;
    }

    while(cyc3_size){
      res_len[res_size] = 3;
      rep(i,3) resA[res_size][i  ] = cyc3[cyc3_size-1][ i     ];
      rep(i,3) resB[res_size][i  ] = cyc3[cyc3_size-1][(i+1)%3];
      res_size++;
      cyc3_size--;
    }

    printf("%d\n",res_size);
    rep(i,res_size){
      printf("%d\n",res_len[i]);
      rep(k,res_len[i]){
        if(k) putchar(' ');
        printf("%d",resA[i][k]+1);
      }
      puts("");
      rep(k,res_len[i]){
        if(k) putchar(' ');
        printf("%d",resB[i][k]+1);
      }
      puts("");
    }
  }


  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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