目次

はじめに

問題は基本的に「プログラミングコンテストチャレンジブック」ベースに作ってます。

解いたらうpしていこうかなと思います。

Javaで解答してるけど、、、単なる趣味です。

効率なアルゴリズムを目指すには

計算量を考慮して作れってことらしい。

例えば、問題1のようにn回のループが4重になっている場合はn^4に比例するので、O(n^4)時間となる。

実行時間制限が1秒の場合

O(10^6)余裕で間に合う
O(10^7)おそらく間に合う
O(10^8)非常にシンプルな処理でない限り厳しい

問題1

問題文

数字が書かれたn枚のカード(K1, K2, ..., Kn)がある。 ここから1枚取り出し、数字を確認して戻すことを4回行う。 4枚のカードの数字の和がmとなる取り出し方が存在するかどうかを計算し、存在するならTrue、存在しないならFalseを出力するプログラムを作成せよ。

条件

  • 1<=n<=50 (カードの枚数)
  • 1<=m<=10^8 (4枚のカードの和)
  • 1<=Ki<=10^8 (カードに書かれている数字)

サンプル1

入力

n = 3
m = 10
k = (1, 3, 5)

出力

True (1、1、3、4と取り出すと和が10になる)

サンプル2

入力

n = 3
m = 9
k = (1, 3, 5)

出力

False (和が9になる取り出し方は存在しない)

解答

import java.io.BufferedReader;		// キーボード入力
import java.io.InputStreamReader;	// キーボード入力
import java.util.Random;			// 乱数

public class question{

	public static void main(String[] args){
 		
		// 使いたい方だけ残してコメントアウト
		
		// キーボード入力
		kai1_key();
		
		// ランダム
		//kai1_ran();
	}
	
	public static int kai1_key(){
		
 		/**
		 * @param n	カードの枚数
		 * @param m	4枚のカードの和
		 * @param k[]	各カード
		 * @param exist	条件を満たす組み合わせがあるか判別
		 */
		
		int n=0, m=0, k[]=new int[50];
		
		boolean exist=false;
		
		// キーボード入力の整数判別ループ用
		boolean LOOP=true;
		
		do{
			try{
				// 入力ストリームを作成する
				BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
				System.out.print("カードの枚数 : ");
				String n2 = input.readLine();		// キーボード入力
				n = Integer.parseInt(n2);		// 文字列を整数に変換
				System.out.print("4枚のカードの和 : ");
				String m2 = input.readLine();		// キーボード入力
				m = Integer.parseInt(m2);		// 文字列を整数に変換
				LOOP=false;				// 整数判別ループ開放
			}catch(Exception e){
				//System.out.println("Exception : " + e);
				System.out.println("整数を入力して下さい。");
			}
		}while(LOOP);
		//System.out.println("カードの枚数 : " + n);
		//System.out.println("4枚のカードの和" + m);
		
		for(int i=0;i<n;i++){
			// 整数判別ループ初期化
			LOOP=true;
			do{
				try{
					// 入力ストリームを作成する
					BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
					System.out.print("k[" + i + "] = ");
					String k2 = input.readLine();		// キーボード入力
					k[i] = Integer.parseInt(k2);		// 文字列を整数に変換
					LOOP=false;				// 整数判別ループ開放
				}catch(Exception e){
					//System.out.println("Exception : " + e);
					System.out.println("整数を入力して下さい。");
				}
			}while(LOOP);
		}
		
		// 4重ループにより全通り試す
		for(int a=0;a<n;a++){
			for(int b=0;b<n;b++){
				for(int c=0;c<n;c++){
					for(int d=0;d<n;d++){
						if((k[a] + k[b] + k[c] + k[d]) == m){
							exist=true;
						}
					}
				}
			}
		}
		
		if(exist) System.out.println("True");
		else System.out.println("False");
		
		return 0;
	}
	
	public static int kai1_ran(){
		
		/**
		 * @param n	カードの枚数
		 * @param m	4枚のカードの和
		 * @param k[]	各カード
		 * @param exist	条件を満たす組み合わせがあるか判別
		 */
		
		int n, m, k[]=new int[50];
		
		boolean exist=false;
		
		//Randomクラスのインスタンス化
		Random rnd = new Random();
		
		// カードの枚数
		n = rnd.nextInt(50) + 1;
		System.out.println("カードの枚数 : " + n);
		
		// 4枚のカードの和
		m = rnd.nextInt(100000000) + 1;
		System.out.println("4枚のカードの和 : " + m);
		
		for(int i=0;i<n;i++){
			k[i] = rnd.nextInt(100000000);
			System.out.println("k[" + i + "] = " + k[i]);
		}
		
		// 4重ループにより全通り試す
		for(int a=0;a<n;a++){
			for(int b=0;b<n;b++){
				for(int c=0;c<n;c++){
					for(int d=0;d<n;d++){
						if((k[a] + k[b] + k[c] + k[d]) == m){
							exist=true;
						}
					}
				}
			}
		}
		
		if(exist) System.out.println("True");
		else System.out.println("False");
		
		return 0;
	}
}

ぶっちゃけ、キーボード入力の所で整数以外が入力された時とかを考慮する必要ないけどね。

作って思ったけど、p.8の友人鬼畜すぎてワロタw

乱数発生させて何回も実行させてみたけど、一回も条件満たさねーよwww

計算量

O(n^4)時間

問題点

4つ取り出すパーターンを全部試し判別してるけどそれってどうなの?ってことらしい。

まぁ、無駄だよね。。。条件を満たすのあるか/ないかが分かればいいだけだから。

問題2

問題文

長さaiの棒iがn本ある。これから3本選んで、最大の周囲の長さを求めよ。 ただし、三角形が作れない場合は0を答えとする。

条件

  • 3<=n<=100 (棒の本数)
  • 1<=ai<=10^6 (棒の長さ)

サンプル1

入力

n = 5
a = {2, 3, 4, 5, 10}

出力

12 (3、4、5の棒を選んだ場合)

サンプル2

入力

n = 4
a = {4, 5, 4, 10, 20}

出力

0 (三角形は作れない)

解答

import java.util.Random;	// 乱数

public class question{

	public static void main(String[] args){
		
		kai2();
	}
	
	public static int kai2(){
		
		/**
		 * @param n	棒の本数
		 * @param ai	棒の長さ
		 * @param ans	周囲の長さ
		 */
		
		int n, a[]=new int[100], ans=0;
		
		//Randomクラスのインスタンス化
		Random rnd = new Random();
		
		// 棒の本数
		n = rnd.nextInt(100) + 3;
		System.out.println("棒の本数 : " + n);
		
		for(int i=0;i<n;i++){
			a[i] = rnd.nextInt(1000000) + 1;
			System.out.println("a[" + i + "] = " + a[i]);
		}
		
		// 問1違い、重複は許されない (i<j<k)
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				for(int k=j+1;k<n;k++){
					//System.out.println("a["+i+"]="+a[i]+"\ta["+j+"]="+a[j]+"\ta["+k+"]="+a[k]);
					int len = a[i] + a[j] + a[k];
					int max = Math.max(a[i], Math.max(a[j], a[k]));	// 一番長い棒の長さ
					int rest = len - max;				// 残り2本の棒の長さの合計
					
					// 三角形を構成できる条件を満たすか判別
					if(max<rest){
						/*
						if(ans<len){
							System.out.println("a["+i+"] = "+a[i]+"\ta["+j+"] = "+a[j]+"\ta["+k+"] = "+a[k]);
						}*/
						ans = Math.max(ans, len);
					}
				}
			}
		}
		
		System.out.println("ans = " + ans);
		
		return 0;
	}
}

ポイント

三角形を作れる条件

一番長い棒 > 他の棒1 + 他の棒2

計算量

O(n^3)

問題3

問題文

長さLcmの竿の上をn匹のアリが毎秒1cmのスピードで歩いています。 アリが竿の端に到達すると竿の下に落ちていきます。 また、竿の上は狭くてすれ違えないので、二匹のアリが出会うと、それぞれ反対を向いて戻っていきます。 各アリについて、現在の竿の左端からの距離x[i]はわかりますが、どちらの方向を向いているのかはわかりません。 すべてのアリが竿から落ちるまでにかかる最小の時間と最大の時間をそれぞれ求めなさい。

条件

  • 1<=L<=10^6 (竿の長さ)
  • 1<=n<=10^6 (アリの数)
  • 0<=Xi<=L (アリの位置)

サンプル

入力

L = 10
n = 3
x = {2, 6, 7}

出力

min = 4 (左向き、右向き、右向き)
max = 8 (右向き、右向き、右向き)

解答

import java.util.Random;	// 乱数

public class question{

	public static void main(String[] args){
		
		kai3();
	}
	
 	public static int kai3(){
	
		/**
		 * @param L	竿の長さ
		 * @param n	アリの数
		 * @param Xi	アリの位置
		 * @param min	最小時間
		 * @param max	最大時間
		 */
		
		int L, n, X[]=new int[1000000];
		
		int min=0, max=0;
		
		//Randomクラスのインスタンス化
		Random rnd = new Random();
		
		// 竿の長さ
		L = rnd.nextInt(1000000) + 1;
		System.out.println("竿の長さ : " + L);
		
		// アリの数
		n = rnd.nextInt(1000000) + 1;
		System.out.println("アリの数 : " + n);
		
		// アリの位置
		for(int i=0;i<n;i++){
			X[i] = rnd.nextInt(L);
			System.out.println("X["+i+"] = " + X[i]);
		}
		
		for(int i=0;i<n;i++){
			max = Math.max(max, Math.max(X[i], L-X[i]));
			min = Math.max(min, Math.min(X[i], L-X[i]));
		}
		
		System.out.println("min = " + min);
		System.out.println("max = " + max);
		
		return 0;
	}
}

ポイント

「二匹のアリが出会うと、それぞれ反対を向いて戻っていく」とあるが、すれ違ったと考えても同じ。

計算量

O(n)

問題

問題文

条件

サンプル

入力

出力

解答


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2016-01-16 (土) 18:03:30 (435d)