SRM 462 250pt: AgeEncoding

TopCoder

問題概要

ビット列が与えられる。これをa進数(aは0より大きい実数)として解釈したとき、age(<100)になるようなaの値を求める問題。

考えたこと

  • (これは当時落とした記憶がある。コーナーケースの厳しい問題で、大撃墜祭りになったことを覚えている。初撃墜を決めたのもこの回だったような)
  • 二分探索はすぐ見えるのでサクッと実装する。
  • 問題はコーナーケースだ。age==1のときは複雑。
  • 先頭の桁が1になるような正規化をすると楽になるような気もするけど、面倒そう。
    • 後から考えるとそうすべきだった。findしてsubstrすればよい。
  • とりあえず多項式に2とか適当な値突っ込んで1.0(0.0)が帰ってくればこの多項式は恒等的に1.0(0.0)だろう。
  • その値で場合分けすればよい。大丈夫だよね？
  • 提出したら落ちた。2回同じ間違いを繰り返すのは精神的にくるものがある。
  • 考慮漏れしてたのはage==1かつ最下位の桁が0のとき。これは普通に解がある…。
  • 訂正したら通った。

practiceで通ったコード

#include <string>
#include <algorithm>
using namespace std;

struct AgeEncoding {

	double getRadix(int age, string candlesLine) {
		//コーナーケース
		double test = calc(2.0, candlesLine);
		if(test == 1.0){
			return age==1?-2:-1;
		}
		else if(test == 0.0){
			return -1;
		}
		else if(age == 1 && candlesLine[(int)candlesLine.length() - 1] == '1'){
			return -1;
		}

		double low = 0.0, high = 101;
		for(int loop=0; loop<100; loop++){
			double mid = (low + high) / 2.0;
			if(calc(mid, candlesLine) > age){
				high = mid;
			}
			else{
				low = mid;
			}
		}

		return low;
	}

	//多項式を計算する
	double calc(double x, const string& coef){
		double val = coef[0] - '0';
		for(int i=1; i<(int)coef.size(); i++){
			val = (val * x) + coef[i] - '0';
		}
		return val;
	}
};