Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

Beta Round #92 DIV1 A問題/DIV2 C問題 - Prime Permutation (この記事を編集する[管理者用])

Source

Codeforces Beta Round #92 DIV1 A問題 (1000pt)
Codeforces Beta Round #92 DIV2 C問題 (2000pt)
Problem description

問題概要

1000文字以下のアルファベット小文字からなる文字列が与えられる.
文字を自由に並べ換えて,任意の素数pと1以上の整数xに対して,p文字目とxp文字目の文字を一致させたい.
できるなら,並べ替え他文字列を1つ求める,できないならそれを指摘する問題.

解法

ある素数を2倍したら,2の倍数であるから,2文字目と一致しなければならなく,その素数の倍数は全て2文字目と一致しなければならない.
ある素数に対して,2倍したら文字数を超える場合は,任意の文字を入れられる.
よって,同じ文字を入れなければいけない場所を列挙して,それと同じ数以上に存在する文字がなければ不可能.
存在すれば,その場所はその文字で埋めて,他は何でも良い.
1文字の場合に注意する.

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 unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int main(){
  int i,j,k,l,m,n;
  int ind[1001];
  int num[1001], sz;
  char in[1020];
  int cnt[26];
  int dame = 0;

  while(scanf("%s",in)==1){
    n = strlen(in);
    if(n==1){puts("YES"); puts(in); continue;}

    rep(i,26) cnt[i] = 0;
    rep(i,n) cnt[in[i]-'a']++;
    rep(i,n) in[i] = 0;
    
    unionInit(ind,n+1);

    for(i=2;i<=n;i++){
      for(j=2*i;j<=n;j+=i) unionConnect(ind, i, j);
    }

    k = 0;
    REP(i,1,n+1) if(unionGet(ind,2)==unionGet(ind,i)) k++;

    rep(i,26) if(cnt[i] >= k){
      REP(j,1,n+1) if(unionGet(ind,2)==unionGet(ind,j)){
        cnt[i]--;
        in[j-1] = 'a'+i;
      }
      break;
    }
    if(i==26){puts("NO"); continue;}

    rep(i,n) if(!in[i]){
      rep(j,26) if(cnt[j]) break;
      cnt[j]--; in[i] = j+'a';
    }
    puts("YES");
    puts(in);
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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