SRM 437
Single Round Match 437 Round 1 - Division II
http://community.topcoder.com/stat?c=round_overview&rd=13699
練習。250に4分。500はなかなか難しく、数時間かけた。
Problem | Status | Points | |
---|---|---|---|
250 | TheBeauty | Opened | AC |
500 | TheSwap | Opened | WA |
1000 | ThePower | Unopened |
- 250に4分
- 簡単だった
- 500には数時間をかけた
- 貪欲法で実装し始める
- 意外に解けない
- 動的計画法で書き直した
TheBeauty
4分。
- 数値を文字列に直して集合を作る
- intからstd::stringに変換した
- std::ostringstreamを用いた
- EACHマクロを導入した
#define EACH(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); ++ i)
- 多少慣れたような気がする
実装は以下。
#define EACH(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); ++ i) class TheBeauty { public: int find(int n) { std::ostringstream ss; ss << n; std::string s(ss.str()); std::set<int> set; EACH(it, s) set.insert(*it); return set.size(); }; };
TheSwap
数時間かけた。
- 貪欲法で解こうとした
- 左から全体が整列されるように交換していき、最後にkが余っていたら辻褄を合わせる作戦とした
- なかなかうまく動作しない。例えばn = 3566、k = 2という場合
- 結果が6653となって欲しい
- しかし、6635等になってしまう場合がある
- 結局動的計画法で実装し直した
- 初めは計算量が大きすぎると考えていた
- しかし、左から全体が整列されるように選んでいくと、それほどの計算量ではないのかも、と思い始めた
- nは高々1,000,000
- つまり桁数は7桁
- 左から交換していく
- 一番左の文字での選択肢は
- 注目している文字より右側に位置するの文字の中でより大きなものと交換するか
- そのままにするか
- 一番左の文字での選択肢は
- n桁であるとすれば、交換するn - 1組み合わせとそのままにする1組み合わせの合計n組み合わせ
- 右に進むので、次はn - 1桁
- 組み合わせ数は次の式で計算できる
-
- 高々5040組み合わせ
- 整列が終わってしまってもkが残っている場合は辻褄を合わせる
- 同じ数値が2つ以上あれば、それらを入れ換えればよい
- 結果は変わらない
- kが偶数であれば、同じペアを交換し続ければよい
- 結果は変わらない
- kが奇数で合った場合のみ、最後の2文字を入れ換える
- 同じ数値が2つ以上あれば、それらを入れ換えればよい
- 文字列から数値への変換を、また数値から文字列を行うために、stoiとitosという関数を用意した
inline int stoi(const std::string& s) { std::istringstream ss(s); int i; ss >> i; return i; } inline std::string itos(int i) { std::ostringstream ss; ss << i; return ss.str(); }
実装は以下。
class TheSwap { public: int findMax(int n, int k) { if (n < 10) return -1; if (n < 100 && n % 10 == 0) return -1; size_ = itos(n).size(); return search(n, 0, k); }; private: int search(int i, int j, int k) { if (k == 0) return i; std::string s(itos(i)); if (j == size_) { std::vector<int> dist(10, 0); EACH(it, s) dist[*it - '0'] ++; if (*std::max_element(ALL(dist)) > 1) { return i; } else if (k % 2 == 0) { return i; } else { std::swap(s[size_ - 2], s[size_ - 1]); return atoi(s.c_str()); } } int ip = 0; for (char c = '9'; c > s[j]; c --) { std::vector<int> a; for (int u = j + 1; u < size_; u ++) if (s[u] == c) a.push_back(u); if (a.empty()) continue; EACH(it, a) { std::swap(s[j], s[*it]); ip = std::max(search(stoi(s), j + 1, k - 1), ip); std::swap(s[j], s[*it]); } break; } return std::max(search(i, j + 1, k), ip); }; private: int size_; };
- 見た。すごかった
- 考察して実装し直してみよう
- nが[1, 1,000,000]であるため、数値の種類は最大でも7
- 1,000,000の場合、つまり7桁の場合先頭の数値の種類は1つ
- つまり最大の組み合わせ数は1から6までの総乗の、720
- たった7920だ
- kの最大値は10
- kは探索を行っている間に0になる
- 取りうる範囲[0, 10]の11種類
- 数値とkをメモ化する
- 最大でも7920種類
これを参考に、実装した(システムテスト済み)。
class TheSwap { public: int findMax(int n, int k) { return search(itos(n), k); }; private: int search(std::string s, int k) { int size = s.size(); std::pair<int, int> key(stoi(s), k); if (memo_.count(key)) return memo_[key]; int& r = memo_[key]; if (k == 0) return r = stoi(s); r = -1; for (int i = 0; i < size; i ++) for (int j = i + 1; j < size; j ++) { if (i == 0 && s[j] == '0') continue; std::swap(s[i], s[j]); r = std::max(search(s, k - 1), r); std::swap(s[i], s[j]); } return r; }; };
- すごくすっきりした
- このような問題を考えるときに、木構造を考える癖があるようだ
- 最初に10組み合わせで、次も10組み合わせだから100組み合わせ、次も10組み合わせだから1000組み合わせ...等々
- 頭の中では、そのような木を想像してしまっている
- 実際には二次元配列で、その大きさも決して大きくはないものなのだ
- std::mapのキーにstd::pairを用いると2次元配列を扱っているかのようにメモ化できる
- 競技プログラミングでは頻出するテクニックらしい
- 慣れていないのでちょっと怖い
- また、std::mapにキーが存在するかどうかはstd::map::countを使うとよい
- キーが存在すれば1を、存在しなければ0を返す
- std::mapのキーの数を数える発想がなかったので、目から鱗
- std::mapの内容を参照すると、実装がさらにすっきりする
- firewoodさんの実装から学んだ