昆布活動記録？

明日はバイオリンとやらの発表会とやら…

先輩がRedCoderだとはしってたけどまさか日本５位とは…さすがIOI９位です。
ちなみにその先輩はPKU1000問以上解いてるとか…時間ｗ

今日は三問。

450

壊れたコンピュータの問題。どうやらある桁のbitをいじろうとするとその桁以降がすべて変わってしまう（正確にはたとえばある桁を1に変えるとそれ以降がすべて1になる。）らしい。で、おかしくなったbit文字列が与えられるから何回操作したらすべて0の状態からその状態まで持っていけるか？という問題。

要約下手ですが、解法はreverseして逆演算。

class StrangeComputer {
   public:
   int setMemory(string mem)
  {
	int ans = 0, j;
	char tmp;
	reverse(mem.begin(), mem.end());
	for (int i=0; i<mem.length(); i++) {
		if (mem[0] == '0') tmp = '1';
		else tmp = '0';
		for (j=0; j<mem.length(); j++) {
			if (mem[j] != '0') break;
		}
		if (j == mem.length()) break;
		for (j=0; j<mem.length(); j++) {
			if (mem[j] == tmp) break;
			mem[j] = tmp;
		}
		cout << mem << endl;
		ans++;
	}
	return ans;
  }
};

Member Pilot Round2

なんかよくわかんないけど一応449と450の間にあったので‥
問題自体はなんかトライアングル作りたいらしくて、てっぺんはXかXX、で与えられた数字の数だけXが現れる三角形を求める。
vectorで返すんだけど、すべての文字列は最下辺のXの数だけの長さがあって、Xじゃないところは.で埋める。もちろんXは真ん中に来るように。

とりあえず制約多いけどXとXXの二通りにわけて出来る方で答えもとめればOK。ちなみに作れないときは空の配列返します。

class Xosceles {
   public:
   vector <string> draw(int xCount)
  {
	vector<string> ans;
	bool b = false;
	int c = 0;
	for (int i=1; c<xCount; i+=2) {
		c += i;
		if (c > xCount) {
			b = true;
			break;
		}
	}
	int n = 0;
	c = 0;
	if (b) {
		for (int i=2; c<xCount; i+=2) {
			c+=i;
			n=i;
			if (c > xCount) {
				b = false;
				break;
			}
		}
		if (b) {
			for (int i=n; i>1; i-=2) {
				string tmp = "";
				for (int j=0; j<(n-i)/2; j++) tmp += '.';
				for (int j=0; j<i; j++) tmp += 'X';
				for (int j=0; j<(n-i)/2; j++) tmp += '.';
				ans.push_back(tmp);
			}
		}
	} else {
		for (int i=1; c<xCount; i+=2) {
			c+=i;
			n=i;
		}
		for (int i=n; i>0; i-=2) {
			string tmp = "";
			for (int j=0; j<(n-i)/2; j++) tmp += '.';
			for (int j=0; j<i; j++) tmp += 'X';
			for (int j=0; j<(n-i)/2; j++) tmp += '.';
			ans.push_back(tmp);
		}
	}
	reverse(ans.begin(), ans.end());
	return ans;
  }
};

449

問題文の読解ゲー
山の終了地点と開始地点の一覧あたえられるから、一番長いコースで山をのぼりおりしたときどのくらい歩いたか求めます。

すべての山はどこかで繋がっているから開始地点の最小と終了地点の最大から距離を求め、
山の角度はすべて45度なのでその距離に√２かけて終わり。

class MountainRoad {
   public:
   double findDistance(vector <int> start, vector <int> finish)
  {
	double ans;
	int s = 1001, f = -1001;
	for (int i=0; i<start.size(); i++) s = min(s, start[i]);
	for (int i=0; i<finish.size(); i++) f = max(f, finish[i]);
	ans = (f-s)*sqrt(2);
	return ans;
  }
};