Hatena::Grouptopcoder

Div2脱出のための日記 このページをアンテナに追加

2011-07-28

TopCoder SRM 513 Div2

| 20:16 | TopCoder SRM 513 Div2 - Div2脱出のための日記 を含むブックマーク はてなブックマーク - TopCoder SRM 513 Div2 - Div2脱出のための日記 TopCoder SRM 513 Div2 - Div2脱出のための日記 のブックマークコメント

結果

rating 763 → 771

points: 155.48

  • Easy 250: 22:00
  • Medium 500: Compiled
  • Hard 1000: 未open
  • : 撃墜なし/非撃墜なし

room 80: 8位

全体: 639位

久々のroom一桁順位です。自分にはスピードがないので1問では差がつきません。

問題

  • Easy 250 Training Camp

n日間の講習会の最後にテストを行う。

テスト問題はm問からなりそれぞれの問題は、講習日の内容に依存している場合がある。

生徒の出欠の記録から、生徒の正答できるはずの問題を予想せよ。

  • Medium 500 Yet Another Incredible Machine

XY座標系(-10000 <= x <= 10000)にバーを設置するためのマウントポイントが

n個(1<= n <= 50)ある。

i番目のマウントポイントにはバーiが水平に設置され長さL[i]である。

マウントポイントの座標は、(M[i], i+1)と表わせる。

バーiをマウントポイントiの一番左端にマウントすると

(M[i] - L[i], i+1)、(M[i], i+1)をバーiが占め、

一番右端にマウントすると(M[i], i+1)、(M[i] + L[i], i+1)をバーiは占める。

マウントポイントから外れない範囲でバーはx方向に1単位で任意の位置に動かすことができる。

次にボールをバーより高い位置から落下させる。m個(1<= m <= 50)のボールはそれぞれ

独立なx座標b[k]から落下するとした場合、

全てのバーがどのボールとも衝突しないように、バーを配置する組合せは何通りあるか。

解答

  • Easy 250 Training Camp
class TrainingCamp {
public:
    vector <string> determineSolvers(vector <string> attendance,
    				     vector <string> problemTopics) {
	vector<string> v = attendance;
	vector<string> u = problemTopics;
	vector<string> w;
	int days = v[0].size();
	for (int i = 0; i < v.size(); ++i) {
	    stringstream ss;
	    for (int j = 0; j < u.size(); ++j) {
		char c = 'X';
		for (int k = 0; k < days; ++k) {
		    if (u[j][k] == 'X' && v[i][k] == '-') {
			c = '-';
		    }
		}
		ss << c;
	    }
	    w.push_back(ss.str());
	}
	return w;
    }
};

  • Medium 500 Yet Another Incredible Machine

これは修正してsystem testを通したもの。

実戦では、テストケース4が通らず提出を断念。

敗因は、

    • unsigned long longを使うべき変数でintを使っていた。
    • 1000000009のmoduloをループ内の組合せ計算後、

毎回modするべきところをreturn時しかやっていなかった。

以上。他のロッジック部分は問題なかったので残念。


class YetAnotherIncredibleMachine {
public:
    int countWays(vector<int> platformMount,
		  vector<int> platformLength, vector<int> balls) {
	int const M = 1000000009;
	vector<int> X = platformMount;
	vector<int> L = platformLength;
	int const nr = X.size();
	int const b_nr = balls.size();
	unsigned long long sum = 1;
	for (int i = 0; i < nr; ++i) {
	    int c = 0;
	    for (int x = X[i] - L[i]; x <= X[i]; x++) {
		bool hit = false;
		for (int k = 0; k < b_nr; ++k) {
		    if (x <= balls[k] && balls[k] <= x + L[i]) {
			hit = true;
		    }
		}
		if (!hit) {
		    c++;
		}
	    }
	    if (c == 0) {
		return 0;
	    } else {
		sum *= c;
		sum %= M;
	    }
	}
	return sum;
    }
};

総括・反省

  • Easy 250 Training Camp

Easyは平易なので、問題文は雰囲気だけ見て、テストケースだけを真剣に読むという時短作戦を決行。

Example 0の説明文が全てを語ってくれていたので作戦は奏功しましたが、

生徒の出欠表と、問題と講習日の対応表からの判定手順を紙上で検討していたら、

トータルで22分ほど掛りました。

コンパイルから全テスト確認、submitが1パスで行ったのは良いのですが、

やはり、Easyは15分、200pointsくらいは欲しいところ。

  • Medium 500 Yet Another Incredible Machine

問題文がちょっとまどろっこしく読むのに時間がかかりましたが、

ロジック自体はEasy程度の平易なものでした。

moduloとかxの値域が[-10000:10000]とか、いかにもintのoverflow

匂わせるヒントがあったのですが気づかなかったのが敗因です。

メソッドのreturnがintだったので騙されました。

概算として、バー50本を20000箇所に独立に配置する場合の場合の数を考えると、

20000を表現するのに必要なbit数は2^16 = 65536から15bitsは必要ですから、

20000^50 〜 2^(15 + 50) = 2^65

2^64を越えてunsigned long longでも間に合わない値になる場合がありえるということで、

modulo取れという指定が必要とされたわけです。

"*="を繰替すような計算があれば、intで済まない可能性大。

moduloと言われたら、64bits変数でも表現できない数が出てくる。

以上が本問の教訓でした。

  • 全体

500はロジックは問題なかったので残念ですが、overflowの権化のような

問題なので教訓になりました。

当面の目標としては、2問正答してコンスタントにroom 5位以内を目指したいところです。

5位を続けていれば、ratingは1000くらいまで順調に上るはずと考えています。

今回は、vector,string,stringstreamくらいしか使わなかったですが、

STLの使い方でコンパイルでトチらなくなってきたのと

ループと条件文によるロジック構成をエディタ上で試行錯誤しなくなったのは、

良い傾向です。

しばらく、400番台のEasy,Mediamのセットを1時間で解く練習でもします。

以上。