2012 TCO Algorithm > Round 1B
2012 TCO Algorithm > Round 1B
http://community.topcoder.com/stat?c=round_overview&er=5&rd=15091
250のみ提出。システムテストを通らず、0点。レートは1019から961へ。何とか緑コーダーを維持。Room 22。
Problem | Status | Points | |
---|---|---|---|
250 | FoxAndKgram | Failed Sys. Test | 0.0 |
500 | FoxAndDoraemon | Opened | 0.0 |
1000 | FoxAndPhotography | Unopened | 0.0 |
FoxAndKgram
実装に25分。155.98/250を獲得。システムテストで落ち、結果0点。
- 総括
- うまく書けたように思えた
- システムテストで落ちた
- ALLマクロを使った
#define ALL(x) (x).begin(), (y).end()
-
-
- 開いたマクロは発想になかった
- std::sort、std::count等の記述が圧倒的に速かった
- 実装が読みやすくなった
- 正直こういうマクロはあまり好きではなかったのだが、今後少しずつ導入しようと思う
-
- コードリーディング
- 赤コーダーの実装が最も簡素であった
- 考えられる範囲の答えを反復し、シミュレーションを行って妥当性を確認する実装であった
- 初めて参加したSRM 535のFoxAndIntegersと同様のアイデアであることを再認識
- このパターンを実装する前に計画できるようにしたい
- 赤コーダーの実装が最も簡素であった
提出した実装は以下(システムテストを通らない)。
class FoxAndKgram { public: int maxK(std::vector<int> len) { int size = len.size(), total = std::accumulate(ALL(len), 0); total += size / 2; int ip = 0; for (int i = 1, c; i * i <= total; i ++) { c = std::count(ALL(len), i); for (int j = 1; j * j < i; j ++) if (j == i - j - 1) { c += std::count(ALL(len), j) / 2; } else { c += std::max(std::count(ALL(len), j), std::count(ALL(len), i - j - 1)); } if (c >= i) ip = c; } return ip; };
- k-gramは長さkの列がk列並んでいる
- イメージとしてはこんな感じ
-
- つまり正方形を成す
- ならば面積はk * k
- そのため最大のkは与えられた鉛筆の長さの合計に近い値の平方根の値に近いのではないか
- 列は長さ1の空白を含む場合がある
- 空白は鉛筆に挟まれていなければならない
- 鉛筆の長さの合計に半分の鉛筆の数を足したのが最大の面積となりうる
- つまり、kは以下の不等式を満たす1以上の範囲に収まる
- 列は長さ1の空白を含む場合がある
-
-
-
- 外側の反復の終了条件ではi * i <= totalとした
- SRM 535でのコードリーディングと考察が実って嬉しい
- ここまではとてもよかった
- 外側の反復の終了条件ではi * i <= totalとした
- 内側の反復の終了条件でミス
- 外側の反復の終了条件のノリで記述して間違えていることに気付かなかった
- これじゃあ、j < √iとなってしまう
- 実装しなければならなかったのはj + j + 1 <= iなのであった
- 最大のkの更新でミス
- ipをiで更新しなければならないのにcで更新してしまった
-
- 合計がiとなる長さjの鉛筆とi - j - 1の鉛筆の数を求める
- std::maxではなく、std::minでなければならなかった
- 間違えてはいたけど、この実装結構好き
- 任意の整数のリストから(x, y)のペアが何組あるか調べるのに良さそうだ(ただし、x ≠ yのとき)
- std::maxではなく、std::minでなければならなかった
-
std::min(std::count(ALL(list), x), std::count(ALL(list), y));
上述を考慮して書き換えた実装は以下。
class FoxAndKgram { public: int maxK(std::vector<int> len) { int size = len.size(), total = std::accumulate(ALL(len), 0); total += size / 2; int ip = 0; for (int i = 1, c; i * i <= total; i ++) { c = std::count(ALL(len), i); for (int j = 1; j + j + 1 <= i; j ++) if (j == i - j - 1) { c += std::count(ALL(len), j) / 2; } else { c += std::min(std::count(ALL(len), j), std::count(ALL(len), i - j - 1)); } if (c >= i) ip = i; } return ip; }; };
-
-
- 反復の内側でstd::countするのはすごく無駄
- 初めに分布を求めたほうがよいか(システムテスト済)
- 反復の内側でstd::countするのはすごく無駄
-
class FoxAndKgram { public: int maxK(std::vector<int> len) { int size = len.size(), total = std::accumulate(ALL(len), 0); total += size / 2; std::map<int, int> dist; for (std::vector<int>::iterator it = len.begin(); it != len.end(); ++ it) dist[*it] ++; int ip = 0; for (int i = 1, c; i * i <= total; i ++) { c = dist[i]; for (int j = 1; j + j + 1 <= i; j ++) if (j == i - j - 1) { c += dist[j] / 2; } else { c += std::min(dist[j], dist[i - j - 1]); } if (c >= i) ip = i; } return ip; }; };
-
- 赤コーダーの実装を真似て、答えを反復しシミュレーションを行う実装をしてみる(システムテスト済)
class FoxAndKgram { public: int maxK(std::vector<int> len) { int size = len.size(); for (int i = 50; i >= 1; i --) { std::vector<bool> used(size, false); int c = std::count(ALL(len), i); for (int j = 0; j < size; j ++) for (int k = j + 1; ! used[j] && k < size; k ++) if (! used[k] && len[j] + len[k] + 1 == i) { used[j] = used[k] = true; c ++; } if (c >= i) return i; } return 0; }; };
FoxAndDoraemon
- 30分ほど考えても実装方法に検討も付かなかった
- 後でやる