夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

番外編とSRM144-Div.2の500

こんにちは。この前のアルゴリズム番外編の続きです。

どこまでやってましたっけ?


あ、ソートからですね。


まずバブルソートの一例。

解説は参考サイトに任せるとして、まずバブルソート

package sort;

import java.io.*;

public class BubbleSort {
	public static void bubbleSort(int[] a) {
		int i, j, tmp;
		for (i = 0; i < a.length; i++) {
			for (j = i+1; j < a.length; j++) {
				if (a[i] > a[j]) {
					tmp = a[i];
					a[i] = a[j];
					a[j] = tmp;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] ary = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(str[i]);
		bubbleSort(ary);
		for (int i = 0; i < n; i++) {
			if (i != 0) System.out.print(" ");
			System.out.print(ary[i]);
		}
		System.out.println();
	}
}

で、挿入ソートは…

package sort;

import java.io.*;

public class InsertionSort {
	public static void insertionSort(int[] a) {
		int i, j, tmp;
		for (i = 1; i < a.length; i++) {
			j = i;
			while (j > 0 && a[j-1] > a[j]) {
				tmp = a[j-1];
				a[j-1] = a[j];
				a[j] = tmp;
				j--;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] ary = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(str[i]);
		insertionSort(ary);
		for (int i = 0; i < n; i++) {
			if (i != 0) System.out.print(" ");
			System.out.print(ary[i]);
		}
		System.out.println();
	}
}

マージソートはちょっとエディタの都合でコメント文字化けしちゃいましたが・・・

package sort;

import java.io.*;

public class MergeSort {
	public static void mergeSort(int[] a, int[] tmp) {
		m_sort(a, tmp, 0, a.length-1);
	}

	public static void m_sort(int[] a, int[] tmp, int left, int right) {
		int mid;
		if (right > left) {
			mid = (right + left) / 2;	// 中央値
			m_sort(a, tmp, left, mid);	// 左側のリストをマージソート
			m_sort(a, tmp, mid+1, right);	// 右側のリストをマージソート
			merge(a, tmp, left, mid+1, right);	// リストをマージする
		}
	}

	public static void merge(int[] a, int[] tmp, int left, int mid, int right) {
		int i, left_end, a_elem, tmp_pos;
		left_end = mid-1;	// 左側のリストの最後
		tmp_pos = left;		// 一番最初のアドレス
		a_elem = right - left + 1;	// 配列の要素数
		/**
		 * 整列済みのリストAとリストBをマージして整列されたリストCを作ると考えます。
		 *
		 * 1.リストAとリストBの先頭の要素を比較して、小さい方をリストから削除してリストCの末尾に追加する
		 * 2.リストA、リストB、どちらか一方の要素がなくなるまで 1. を繰り返す
		 * 3.残った要素をリストCの末尾に順に追加する
		 *
		 * 以上の手順でマージは完了します。
		 */
		/* 二つのリストに要素が残っている(1と2) */
		while (left <= left_end && mid <= right) {
			if (a[left] <= a[mid]) {
				tmp[tmp_pos] = a[left];
				tmp_pos = tmp_pos+1;
				left++;
			} else {
				tmp[tmp_pos] = a[mid];
				tmp_pos = tmp_pos + 1;
				mid++;
			}
		}
		// ここから下が3
		/* 左側のリスト */
		while (left <= left_end) {
			tmp[tmp_pos] = a[left];
			left = left + 1;
			tmp_pos++;
		}
		/* 右側のリスト */
		while (mid <= right) {
			tmp[tmp_pos] = a[mid];
			mid = mid + 1;
			tmp_pos++;
		}
		/* aにまとめる。この時要素はtmpに昇順に入っている。*/
		for (i = 0; i < a_elem; i++) {
			a[right] = tmp[right];
			right--;
		}
	}

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] ary = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i = 0; i < n; i++) {
			ary[i] = Integer.parseInt(str[i]);
		}
		int[] tmp = new int[n];
		mergeSort(ary, tmp);
		for (int i = 0; i < n; i++) {
			if (i != 0) System.out.print(" ");
			System.out.print(ary[i]);
		}
		System.out.println();
	}
}

あとクイックソート

package sort;

import java.io.*;

public class QuickSort {
	public static void quickSort(int[] a, int left, int right) {
		int l_hold = left;
		int r_hold = right;
		int pivot = a[left];
		while (left < right) {
			while (a[right] >= pivot && left < right)
				right--;
			if (left != right) {
				a[left] = a[right];
				left++;
			}
			while (a[left] <= pivot && left < right)
				left++;
			if (left != right) {
				a[right] = a[left];
				right--;
			}
		}
		a[left] = pivot;
		pivot = left;
		left = l_hold;
		right = r_hold;
		if (left < pivot)
			quickSort(a,left,pivot-1);
		if (right > pivot)
			quickSort(a,pivot+1,right);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] ary = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(str[i]);
		quickSort(ary,0,ary.length-1);
		for (int i = 0; i < n; i++) {
			if (i != 0) System.out.print(" ");
			System.out.print(ary[i]);
		}
		System.out.println();
	}
}

そして選択ソートと

package sort;

import java.io.*;

class SelectionSort {
	public static void selectionSort(int[] a) {
		int i, j, min, tmp;
		for (i = 0; i < a.length; i++) {
			min = i;
			for (j = i+1; j < a.length; j++) {
				if (a[min] > a[j])
					min = j;
			}
			tmp = a[i];
			a[i] = a[min];
			a[min] = tmp;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] ary = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(str[i]);
		selectionSort(ary);
		for (int i = 0; i < n; i++) {
			if (i != 0) System.out.print(" ");
			System.out.print(ary[i]);
		}
		System.out.println();
	}
}

シェルソート

package sort;

import java.io.*;

public class ShellSort {
	public static void shellSort(int[] a) {
		int i, j, inc, tmp;
		inc = a.length-1;
		while (inc > 0) {
			for (i = 0; i < a.length; i++) {
				j = i;
				tmp = a[i];
				while (j >= inc && a[j-inc] > tmp) {
					a[j] = a[j-inc];
					j -= inc;
				}
				a[j] = tmp;
			}
			if (inc/2 != 0) {
				inc = inc/2;
			} else if (inc == 1) {
				inc = 0;
			} else {
				inc = 1;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] ary = new int[n];
		String[] str = br.readLine().split(" ");
		for (int i = 0; i < n; i++)
			ary[i] = Integer.parseInt(str[i]);
		shellSort(ary);
		for (int i = 0; i < n; i++) {
			if (i != 0) System.out.print(" ");
			System.out.print(ary[i]);
		}
		System.out.println();
	}
}


で、SRM144 Div.2 550問題に苦戦していて、今のコード(問題付き。CodeProcessorで)

// BEGIN CUT HERE
// PROBLEM STATEMENT
// Let's say you have a binary string such as the following:
// 
// 011100011
// 
// One way to encrypt this string is to add to each digit the 
// sum of its adjacent digits.  For example, the above string 
// would become:
// 
// 123210122
// 
// In particular, if P is the original string, and Q is the 
// encrypted string, then Q[i] = P[i-1] + P[i] + P[i+1] for 
// all digit positions i.  Characters off the left and right 
// edges of the string are treated as zeroes.
// 
// An encrypted string given to you in this format can be 
// decoded as follows (using 123210122 as an example):
// 
// Assume P[0] = 0.
// Because Q[0] = P[0] + P[1] = 0 + P[1] = 1, we know that P
// [1] = 1.
// Because Q[1] = P[0] + P[1] + P[2] = 0 + 1 + P[2] = 2, we 
// know that P[2] = 1.
// Because Q[2] = P[1] + P[2] + P[3] = 1 + 1 + P[3] = 3, we 
// know that P[3] = 1.
// Repeating these steps gives us P[4] = 0, P[5] = 0, P[6] = 
// 0, P[7] = 1, and P[8] = 1.
// We check our work by noting that Q[8] = P[7] + P[8] = 1 + 
// 1 = 2.  Since this equation works out, we are finished, 
// and we have recovered one possible original string.
// 
// Now we repeat the process, assuming the opposite about P[0]:
// 
// Assume P[0] = 1.
// Because Q[0] = P[0] + P[1] = 1 + P[1] = 0, we know that P
// [1] = 0.
// Because Q[1] = P[0] + P[1] + P[2] = 1 + 0 + P[2] = 2, we 
// know that P[2] = 1.
// Now note that Q[2] = P[1] + P[2] + P[3] = 0 + 1 + P[3] = 
// 3, which leads us to the conclusion that P[3] = 2.  
// However, this violates the fact that each character in the 
// original string must be '0' or '1'.  Therefore, there 
// exists no such original string P where the first digit is 
// '1'.
// 
// Note that this algorithm produces at most two decodings 
// for any given encrypted string.  There can never be more 
// than one possible way to decode a string once the first 
// binary digit is set.
// 
// Given a String message, containing the encrypted string, 
// return a String[] with exactly two elements.  The first 
// element should contain the decrypted string assuming the 
// first character is '0'; the second element should assume 
// the first character is '1'.  If one of the tests fails, 
// return the string "NONE" in its place.  For the above 
// example, you should return {"011100011", "NONE"}.
// 
// DEFINITION
// Class:BinaryCode
// Method:decode
// Parameters:String
// Returns:String[]
// Method signature:String[] decode(String message)
// 
// 
// CONSTRAINTS
// -message will contain between 1 and 50 characters, 
// inclusive.
// -Each character in message will be either '0', '1', '2', 
// or '3'.
// 
// 
// EXAMPLES
// 
// 0)
// "123210122"
// 
// Returns: { "011100011",  "NONE" }
// 
// The example from above.
// 
// 1)
// "11"
// 
// Returns: { "01",  "10" }
// 
// We know that one of the digits must be '1', and the other 
// must be '0'.  We return both cases.
// 
// 2)
// "22111"
// 
// Returns: { "NONE",  "11001" }
// 
// Since the first digit of the encrypted string is '2', the 
// first two digits of the original string must be '1'.  Our 
// test fails when we try to assume that P[0] = 0.
// 
// 3)
// "123210120"
// 
// Returns: { "NONE",  "NONE" }
// 
// This is the same as the first example, but the rightmost 
// digit has been changed to something inconsistent with the 
// rest of the original string.  No solutions are possible.
// 
// 4)
// "3"
// 
// Returns: { "NONE",  "NONE" }
// 
// 5)
// "12221112222221112221111111112221111"
// 
// Returns: { "01101001101101001101001001001101001",  
// "10110010110110010110010010010110010" }
// 
// END CUT HERE
import java.util.*;
public class BinaryCode {
	public String[] decode(String message) {
		int[] Q = new int[message.length()];
		for (int i = 1; i < message.length(); i++)
			Q[i] = (int)message.charAt(i);
		int[] P = new int[Q.length];
		String[] ans = new String[2];
		// when P[0] = 0
		P[0] = 0;
		int count = 0;
		while (true) {
			if (count == 0) {
				P[1] = Q[0] - P[0];
			} else {
				P[count+1] = Q[count] - (P[count]+P[count-1]);
			}
			if (P[count] != 0 && P[count] != 1) {
				ans[0] = "NONE";
				break;
			} else if (count == Q.length-2) {
				ans[0] = "";
				for (int i = 0; i < Q.length; i++)
					ans[0] += String.valueOf(P[i]);
				break;
			}
			count++;
		}
		// when P[0] = 1;
		P[0] = 1; count = 0;
		while (true) {
			if (count == 0) {
				P[1] = Q[0] - P[0];
			} else {
				P[count+1] = Q[count] - (P[count]+P[count-1]);
			}
			if (P[count] != 0 && P[count] != 1) {
				ans[1] = "NONE";
				break;
			} else if (count == Q.length-2) {
				ans[1] = "";
				for (int i = 0; i < Q.length; i++)
					ans[1] += String.valueOf(P[i]);
				break;
			}
			count++;
		}
		return ans;
	}

	// BEGIN CUT HERE
	public static void main(String[] args) {
		BinaryCode temp = new BinaryCode();
		System.out.println(temp.decode(args[0])[1]);
	}
	// END CUT HERE
}

なぜか全部NONE返してしまう。

たすけて〜