Single Round Match 536
Single Round Match 536 Round 1 - Division II:
http://community.topcoder.com/stat?c=round_overview&er=5&rd=14728
2問通過。570.69点。レートは785から857へ。
Problem | Status | Points | |
---|---|---|---|
250 | BinaryPolynomialDivTwo | Passed System Test | 202.49 |
500 | RollingDiceDivTwo | Passed System Test | 368.20 |
1000 | MergersDivTwo | Opened | 0.0 |
BinaryPolynomialDivTwo
実装とテストで14分。202.49/250.00獲得。
- 総括
- 難しくはないはずなのだが、時間がかかってしまった
- 実装はグダグダだった
- コードリーディング
- P(0)は反復を利用しないで求めることができる
- sizeはforブロック内で定義すればよい
int p_0 = a[0], p_1 = 0; for (int i = 0, size = a.size(); i < size; i ++) p_1 += a[i];
提出した実装は以下。
class BinaryPolynomialDivTwo { public: int countRoots(std::vector<int> a) { int size = a.size(); int p_0 = 0, p_1 = 0; for (int i = 0; i < size; i ++) { p_0 += a[i] * ((i == 0) ? 1 : 0); p_1 += a[i]; } int count = 0; if (p_0 % 2 == 0) count ++; if (p_1 % 2 == 0) count ++; return count; } };
RollingDiceDivTwo
実装とテストで19分。368.20/500点獲得。
- 総括
- 初めは各試行に関してダイスの目のポピュレーションを取ろうとした
- ポピュレーションをテーブルに書き込み、大きな数値から抽出しようとしたところで各試行を予め整列したほうが合理的であることに気付き、実装し直した
137 == (sort) ==> 137 364 == (sort) ==> 346 115 == (sort) ==> 115 724 == (sort) ==> 247 ||`-- max(7, 6, 5, 7) = 7 |`--- max(3, 4, 1, 4) = 4 `---- max(1, 3, 1, 2) = 3 `-- sum(7, 4, 3) = 14
- コードリーディング
- 今考えると内側の反復で降順(size - 1、size - 2、...、0)としている意味が全くない
for (int i = 0, size = rolls[0].size(); i < size; i ++) { int dp = 0; for (std::vector<std::string>::iterator it = rolls.begin(); it != rolls.end(); ++ it) dp = std::max((*it)[i] - '0', dp); sum += dp; }
提出した実装は以下。
class RollingDiceDivTwo { public: int minimumFaces(std::vector<std::string> rolls) { for (std::vector<std::string>::iterator it = rolls.begin(); it != rolls.end(); ++ it) std::sort(it->begin(), it->end()); int sum = 0; for (int i = 0, size = rolls[0].size(); i < size; i ++) { int dp = 0; for (std::vector<std::string>::iterator it = rolls.begin(); it != rolls.end(); ++ it) dp = std::max((*it)[size - i - 1] - '0', dp); sum += dp; } return sum; } };
MergersDivTwo
10分ほど足らなかった。が、大会中に40分ほど時間をかけていたので合計50分。時間かけ過ぎ。
システムテスト終了後に提出。
- 総括
- r = {5, -7, 3}、k = 2の組み合わせを紙で考えたのが良かった
(( 5 - 7) / 2 + 3) / 2 = (-1 + 3) / 2 = 1 where r = {5, -7, 3}, k = 2, m = 2 (( 5 + 3) / 2 - 7) / 2 = ( 4 - 7) / 2 = -1.5 ((-7 + 3) / 2 + 5) / 2 = (-2 + 5) / 2 = 1.5 (5 - 7 + 3) / 3 = 1.5 where r = {5, -7, 3}, k = 2, m = 3
式を展開すると
5 / 4 - 7 / 4 + 3 / 2 = 1 where r = {5, -7, 3}, k = 2, m = 2 5 / 4 + 3 / 4 - 7 / 2 = -1.5 -7 / 4 + 3 / 4 + 5 / 2 = 1.5 5 / 3 - 7 / 3 + 3 / 3 = 1.5 where r = {5, -7, 3}, k = 2, m = 3
-
- 感覚的により左側にいる数値にかかる係数がより小さくなることが分かる
- 例えば負の値はできるだけ小さくなるのが望ましい。つまり負の値はより左側にあったほうが合計が大きくなりそうだ
- 同様に大きな正の値はできるだけ大きくなるのが望ましい。つまり、正の値、特に大きな値はより係数の大きい右側にあるほうが合計が大きくなりそうだ
- ではまず入力を整列してしまおう
5 -7 3 == (sort) ==> -7 3 5
-
- r = {5, -7, 3}、k = 2の場合は以下の何れかが答えとなりそうだ
-7 3 5 -7 3 5 ~~~~~ ~~~~~~~~ -2 5 0.333 ~~~~~~~ 1.5
-
- 合計は再帰関数で計算する戦略にする。例えば与えられたリストの数が5でk = 3である場合、3つ、4つ、5つの数を合成する選択肢がある。4つの数をまとめるとリストの数が2つとなってしまい、総合的に成立しないことに注意
a b c d e a b c d e a b c d e ~~~~~ ~~~~~~~ ~~~~~~~~~ f d e h e i ~~~~~~~ ~~~~~~ g - *) f = (a + b + c) / 3 g = (f + d + e) / 3 h = (a + b + c + d) / 4 i = (a + b + c + d + e) / 5 - = 成立しない数
-
- つまり、リストの数が1より大きくkより小さい場合は成立しない
- リストの数が1である場合、要素の数が結果
- リストの数がkと同じかそれ以上である場合は、左側からkからリストの数まで合成して、結果が最大になるものを選べばよい
- 今考えればfoldlみたいじゃないか
実装は以下。
class MergersDivTwo { public: double findMaximum(std::vector<int> revenues, int k) { std::sort(revenues.begin(), revenues.end()); std::vector<double> r; for (std::vector<int>::iterator it = revenues.begin(); it != revenues.end(); ++ it) r.push_back(*it); return search(r, k); }; private: double search(std::vector<double> revenues, int k) { int size = revenues.size(); if (size == 1) return revenues[0]; if (size < k) return -1.0e+16; double rp = -1.0e+16; for (int i = k; i <= size; i ++) { double sum = 0.0; for (int j = 0; j < i; j ++) sum += revenues[j]; std::vector<double> r; r.push_back(sum / i); for (int j = i; j < size; j ++) r.push_back(revenues[j]); rp = std::max(search(r, k), rp); } return rp; }; }