質問編集履歴

2017/05/08 01:09

投稿

nuiri1343

スコア54

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,301 +1,3 @@
-###問題
+自力で頑張ってみようかと思います。
-任意の数列Aと、いくつかの任意の置換Pが与えられたとき、
-数列AにPをそれぞれ1回以下ずつ適用した時、得られる数列のなかで辞書順で最も早いものを出力しなさい
-なお、数列の長さと、置換の数は標準入力より得られるものとする
-###
-置換Pが何種類与えられるかは、その時々によって違います。よって、与えられた置換の数が多ければ多いほど得られる数列はものすごい勢いで多くなっていくと思います。
-置換2種類ならば、辞書順比較しなければならないのは5種類の数列、
-置換3種類ならば、辞書順比較しなければならないのは15種類の数列、
-...
-適用する置換が1つ以下なので
-例えば置換P1とP2が与えられた場合、比較するのは
-A
-AをP1で置換したもの
-AをP2で置換したもの
-AをP1で置換したものをP2で置換したもの
-AをP2で置換したものをP1で置換したもの
-これをどう実装すればいいか全くわかりませんでした。
-一応なんとか試行錯誤して書いたソースコードを下に示しますが
-これは、与えられる置換の数を5つまでとして作ったものです
-本当は置換の数に制限はありません。
+アドバイスありがとうございました。
-###ソースコード
-```java
-import java.util.*;
-public class Main {
-    public static void main(String[] args) throws Exception{
-        Scanner sc = new Scanner(System.in);
-        int n = Integer.parseInt(sc.nextLine());//数列の長さ取得
-        String[] line = sc.nextLine().split(" ",0);
-        int[] s = new int[n];
-        for(int i=0;i<n;i++){//数列A取得
-            s[i] = Integer.parseInt(line[i]);
-        }
-        int m = Integer.parseInt(sc.nextLine());//置換の数取得
-        int[][] p = new int[m][n];
-        for(int i=0;i<m;i++){
-            line = sc.nextLine().split(" ",0);
-            for(int j=0;j<n;j++){
-                p[i][j] = Integer.parseInt(line[j]);//置換数列取得
-            }
-        }
-	int[] min = new int[n];//辞書順で一番早いものを都度保持するための配列
-	for(int i=0;i<n;i++){
-	    min[i] = s[i];//まずは初期の数列を保存
-	}
-	int[] temp;
-	for(int i=0;i<m;i++){
-	    temp = chikan(s,p[i]);//適用する置換が1種類の時
-	    tempMin(temp,min);
-	    for(int j=0;j<m;j++){
-		if(m==1)break;
-		if(i==j)continue;
-		int[] temp2 = chikan(temp,p[j]);//適用する置換が2種類の時
-		tempMin(temp2,min);
-		for(int k=0;k<m;k++){
-		    if(m==2)break;
-		    if(j==k||i==k)continue;
-		    int[] temp3 = chikan(temp2,p[k]);//適用する置換が3種類の時
-		    tempMin(temp3,min);
-		    for(int l=0;l<m;l++){
-			if(m==3)break;
-			if(j==l||i==l||k==l)continue;
-			int[] temp4 = chikan(temp3,p[l]);//適用する置換が4種類の時
-			tempMin(temp4,min);
-			for(int o=0;o<m;o++){
-			    if(m==4)break;
-			    if(j==o||i==o||k==o||l==o)continue;
-			    int[] temp5 = chikan(temp4,p[o]);//適用する置換が5種類の時
-			    tempMin(temp5,min);
-			}
-		    }
-		}
-	    }
-	}
-	for(int i=0;i<n;i++){
-	    if(i!=0){
-		System.out.print(" ");
-	    }
-	    System.out.print(min[i]);
-	}
-	System.out.println("");
-    }
-    public static void tempMin(int[] temp,int[] min){//minと比較して、辞書順で早ければminを更新
-	for(int j=0;j<temp.length;j++){
-	    if(temp[j]==min[j]){
-		continue;
-	    }
-	    if(temp[j]>min[j]){
-		break;
-	    }
-	    if(temp[j]<min[j]){
-		for(int k=0;k<temp.length;k++){
-		    min[k]=temp[k];
-		}
-	    }
-	}
-    }
-    public static int calc(int m){//置換の数から、最終的に得られる数列の数を計算する
-        int answer=0;
-        for(int i=1;i<=m;i++){
-            answer+=calcP(m,i);
-        }
-        return answer;
-    }
-    public static int calcP(int m,int n){//順列の計算
-        int answer=1;
-        for(int i=0;i<n;i++){
-            answer *= (m-i);
-        }
-        return answer;
-    }
-    public static int[] chikan(int[] s,int[] p){//sをpによって置換する
-	int[] t = new int[s.length];
-	for(int i=0;i<p.length;i++){
-	    t[p[i]-1] = s[i];
-	}
-	return t;
-    }
-}
-```
-###補足
-上記は、予想外の入力の際の例外など全然行っていませんが、
-そこはひとまず目をつぶってください。
-見にくくてわけわからないプログラムで申し訳ありません。
-本当にわからなくて、いろいろと試行錯誤していたらこんな形になってしまいました。
-自分のあげたソースコードは無視して
-解答だけでもかまいませんので
-お詳しい方どうか教えていただけないでしょうか