2010年10月1日金曜日

PKU Judge Online 1731 Orders

■1731 Orders

□Problem
文字列sが与えられる.sの順列を辞書式順で生成せよ.但し,重複する文字列は省く.

□Solution
順列生成は再帰で.
重複を省くためには,以下.
まず,
s=c0c1…cn-1
に,
vk=kと数字を割り当てる.
再帰で順列を生成し,
s'=ca0ca1…can-1
となったとする.
cai=caj (i<j)
となるi,jがあった時,
vi<vj
であれば,その順列を出力し,そうでない場合は出力しない.
実際には,この判定を再帰の途中で行い,枝刈りをしている.

出力が遅かったため(TLEした),
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
として,最後にまとめてストリームをフラッシュ.

□Code
package p1731;

import java.util.*;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.lang.*;
import java.math.*;

// AC
public class Main{
Scanner sc=new Scanner(System.in);

char[] cs;
int[] order;
int n;

void recursive(int j){
if(j==n){
println(new String(cs));
return;
}
for(int i=j; i<n; i++){
// right rotate [j,i]
char c=cs[i];
int t=order[i];
for(int k=i; k>j; k--){
cs[k]=cs[k-1];
order[k]=order[k-1];
}
cs[j]=c;
order[j]=t;
boolean f=true;
for(int k=j; k<=i; k++){
if(cs[j]==cs[k]&&order[j]>order[k]){
f=false;
break;
}
}
if(f)
recursive(j+1);
// left rotate [j,i]
for(int k=j; k<i; k++){
cs[k]=cs[k+1];
order[k]=order[k+1];
}
cs[i]=c;
order[i]=t;
}
}

void run(){
cs=sc.next().toCharArray();
n=cs.length;
order=new int[n];
for(int i=0; i<n; i++)
order[i]=i;
Arrays.sort(cs);
recursive(0);
System.out.flush();
}

void println(String s){
System.out.println(s);
}

void print(String s){
System.out.print(s);
}

public static void main(String[] args){
System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}

0 件のコメント: