夢追い人

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

SRM144 Div.2のpart.1

TwitterでTopCoderの練習方法を聞いたところ…

@touyou_ 個人的にはTopCoderの過去問のほうをお勧めします。自分の解いた問題のほかの人のコードが見れるので、よいところをどんどんマネしていくと良いと思います。あと、問題の解説ページもかなり詳しいのでお勧めです。 http://bit.ly/gieluq

と、RedCoderの方から言われましたんでもう一回心機一転してC++で。

では…とりあえず1100については英語解読しなきゃなんないんでとりあえずEasyとMediumです。

200

大分前にもJavaでやって正解していた超簡単な問題。

とりあえず気をつけると言えば割るとき条件分岐してないとちょっとエラーしちゃうかな?ぐらい。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

using namespace std;

class Time {
	public:
	string whatTime(int seconds) {
		int h = 0, m = 0, s = 0;
		if (seconds >= 3600) h = seconds/3600;
		seconds -= h*3600;
		if (seconds >= 60) m = seconds/60;
		seconds -= m*60;
		s = seconds;
		stringstream ss; 
		ss << h << ":" << m << ":" << s;
		string time = ss.str();
		return time;
	}
};

あとはstringstreamぐらいですかね。まぁコレはしらべといてください。

550

これは一応めんどくさいのでJavaの移植と言う形をとってみましたが…

どうしてもだめ。

class BinaryCode {
	public:
	vector <string> decode(string message) {
		vector<string> ans(2);
		vector<int> p0, p1;
		p0.push_back(0); p1.push_back(1);
		int i=0;
		while (true) {
			if (i == 0) {
				p0.push_back((int)message[i] - p0[0]);
			} else if (i != message.length()-1) {
				cout << (int)message[i]-p0[i]-p0[i-1] << endl;
				p0.push_back((int)message[i] - (p0[i]+p0[i-1]));
			}
			if (p0[i] != 0 && p0[i] != 1) {
				ans[0] = "NONE";
				break;
			} else if (i == message.length()-1) {
				ans[0] = "";
				for (int i = 0; i < message.length(); i++)
					ans[0] += (char)p0[i];
				break;
			}
			i++;
		}
		i=0;
		while (true) {
			if (i == 0) {
				p1.push_back((int)message[i] - p1[0]);
			} else if (i != message.length()-1) {
				p1.push_back((int)message[i] - (p1[i]+p1[i-1]));
			}
			if (p1[i] != 0 && p1[i] != 1) {
				ans[0] = "NONE";
				break;
			} else if (i == message.length()-1) {
				ans[0] = "";
				for (int i = 0; i < message.length(); i++)
					ans[0] += (char)p1[i];
				break;
			}
			i++;
		}
		return ans;
	}
};

絶対に一個目がNONE、二個目が””になってしまう…

ということで早速他人のコードを見てみました。550点だった方のものを・・・

class BinaryCode {
	public:
	vector <string> decode(string message) {
		vector<string> res;
		string a="", b="";
		int i, j, k;
		if (message.size()==1) {
			if(message[0]=='0') {
				res.push_back("0");
				res.push_back("NONE");
			} else if (message[0]=='1') {
				res.push_back("NONE");
				res.push_back("1");
			} else {
				res.push_back("NONE");
				res.push_back("NONE");
			}
			return res;
		}
		for (i=0; i<message.size(); i++) {
			a.push_back('0');
			b.push_back('0');
		}
		b[0]='1';
		for (i=1; i<message.size(); i++) {
			if (i==1) {
				a[i] += message[i-1]-a[i-1];
			} else {
				a[i] += message[i-1]-a[i-1]-a[i-2]+'0';
			}
			if (a[i]!='1' && a[i]!='0') {
				a="NONE";
				break;
			}
		}
		if (message[message.size()-1]-a[a.size()-1]-a[a.size()-2]+'0'!=0) {
			a="NONE";
		}
		for (i=1; i<message.size(); i++) {
			if (i==1) {
				b[i] += message[i-1]-b[i-1];
			} else {
				b[i] += message[i-1]-b[i-1]-b[i-2]+'0';
			}
			if (b[i]!='1' && b[i]!='0') {
				b="NONE";
				break;
			}
		}
		if (message[message.size()-1]-b[b.size()-1]-b[b.size()-2]+'0'!=0) {
			b="NONE";
		}
		res.push_back(a);
		res.push_back(b);
		return res;
	}
};

あとRedCoderの方の…

class BinaryCode {
	public:
	vector <string> decode(string message) {
		string s = message;
		int n = s.size(), i, a[99];
		vector<string> ret;
		ret.clear();
		a[0] = 0;
		for (a[1]=0;a[1]<2;a[1]++) {
			for (i=1;i<=n;i++) a[i+1] = s[i-1]-48-a[i]-a[i-1];
			string res = "";
			for (i=1;i<=n;i++) res += (char)(a[i]+48);
			for (i=1;i<=n;i++)
				if (a[i] < 0 || a[i] > 1) res = "NONE";
			if (a[n+1] != 0) res = "NONE";
			ret.push_back(res);
		}
		return ret;
	}
};

550点の方は地味ですが確実な気がします。
ちょっとcharの足し算について理解しないと直感的でない部分がありますが…

そしてRedCoderは…なんかエレガントですが…

わかりにくい(;´Д`)

48の意味がわかりません。


ではpart2をお楽しみに!

広告を非表示にする