TopCoder(Practice_144_DIV_1_300)

[TopCoder]練習（SRMs 1 144 DIV 1 300)

問題を読む為の英単語

単語	意味
following	次の
say	示す
encrypt	暗号化・符号化
adjacent	隣接した
above	上の
particular	詳細
opposite	反対の

問題概要

・入力
０〜３までの数列
・出力
入力のコードを複合化したバイナリコード
・詳細
文字がn個の入力数列をQ[0], Q[1], ... Q[n]とする。
出力すべきバイナリコード数列をP[0],P[1],...,P[n]とする。
入力と出力には以下の関係が成り立つ。
Q[0] = P[0] + P [1]
Q[1] = P[0] + P [1] + P [2]
Q[2] = P[1] + P [2] + P [3]
Q[k] = P[k-1] + P[k] + P[k+1]
Q[n] = P[n-1] + P[n]

しかしながら、P[0]を0とするか、1とするかで解答が異なる。
P[0]が0と1のそれぞれの場合の複合コードを出力せよ。

ただし、複合不可である場合は"NONE"と出力せよ。

解答コード(C#)

	class BinaryCode
	{
		public string[] decode (string message)
		{
			int size = message.Length;
			int[] P = new int[size];
			int[] Q = new int[size];
			string[] ans = new string[2];

			int P_1st = 0;
			bool flg;
			string[] Q_str = new string[size];

			//入力文字列を分割
			for (int i = 0; i < size; i++) {
				Q_str [i] = message.Substring (i, 1);
			}

			//文字列を整数型に変換
			for (int i = 0; i < size; i++) {
				Q [i] = int.Parse (Q_str [i]);
			}

			//P[0]=0,1分繰り返す
			for (P_1st = 0; P_1st < 2; P_1st++) {
				//P[0]初期化
				P [0] = P_1st;
				//復号
				if (size > 1) {
					P [1] = Q [0] - P [0]; 
					for (int i = 2; i < size; i++) {
						P [i] = Q [i - 1] - P [i - 2] - P [i - 1];
					}
				}

				//復号結果が正しいか判定
				flg = true;
				//入力文字サイズが2以下あれば、復元不可
				if (size < 2) {
					flg = false;
					// 最終文字列の復号関係が正しくなければ復元不可
				}else if (Q [size - 1] != P [size - 1] + P [size - 2]) {
					flg = false;
				} else {
					//復号結果がバイナリでなければ復元不可
					for (int i = 0; i < size; i++) {
						if (P [i] < 0 || P [0] > 2) {
							flg = false;
							break;
						}
					}
				}

				//出力文字列生成
				if (flg == true) {
					string tmp = "";
					for (int i = 0; i < size; i++) {
						tmp = tmp + P [i].ToString ();
					}
					ans [P_1st] = tmp;
				} else {
					ans [P_1st] = "NONE";
				}
			}
			return ans;
		}
	}

テスト

入力：123210122
結果：{"011100011", "NONE"}

入力：11
結果：{"01", "10"}

入力：3
結果：{"NONE","NONE"}

入力：12221112222221112221111111112221111
結果：{"01101001101101001101001001001101001", "10110010110110010110010010010110010"}

TopCoderで多用しそうなコード

・string型を一文字ずつ分割

Q_str [i] = message.Substring (i, 1);

・文字列を整数型に変換

Q [i] = int.Parse (Q_str [i])

・コンソール出力

Console.WriteLine (Q_str [i]);