SRM 340 Div II
SRM 340 Div II
http://community.topcoder.com/stat?c=round_overview&er=5&rd=10664
練習。DP強化週間の一環。
Problem | Status | Points | |
---|---|---|---|
250 | CssPropertyConverter | Passed System Test | 248.20 |
500 | ProblemsToSolve | Failed System Test | 0.00 |
1000 | CsCourses | Unopened |
- 250に2分
- 500に45分ほどかけて、システムテストを落とした
- DPで実装することが出来ずDFSで実装したが、メモ化の実装を間違えて落とした
- エディトリアルを見て、グラフの問題であることに気付き、考察を行った
CssPropertyConverter
http://community.topcoder.com/stat?c=problem_statement&pm=7503&rd=10664
2分。248.20点。
- やるだけ(一回言ってみたかった)
提出した実装は以下(システムテストを通る実装)。
class CssPropertyConverter { public: std::string getCamelized(std::string cssPropertyName) { std::string s; bool camerize = false; EACH (it, cssPropertyName) if (*it == '-') { camerize = true; } else if (camerize) { s += toupper(*it); camerize = false; } else { s += *it; } return s; }; };
ProblemsToSolve
http://community.topcoder.com/stat?c=problem_statement&pm=7504&rd=10664
- DP強化週間だけに、まずDPでの実装を考えた
- 以下のようなDPテーブルを考えた
- DPの計算量とメモリ量は、O(N3)
dp[i番目][i番目の頂点までの最小の値][i番目の頂点までの最大の値] = 経由した頂点数
- 制約は以下
- 概算すると、50 × 103 × 103 = 50 × 106 = 5 × 107
- DPテーブルにはintを用いたい
- SRMでのメモリ制限は64Mバイトである。intが4バイトであるので、16M要素 = 1.6 × 107要素が上限
- 納まらない...
- 双対な関係のDPを用いるのではないか?
- 自分の実力では思いつかない...
- 仕方がないのでDFSで考えてみる
- 関数プロトタイプは以下とした
dfs(i番目, i番目の頂点までの最小の値, i番目の頂点までの最大の値) -> 経由した頂点数を返す
- これもO(N3)だ
- だが、(i番目の頂点までの最小の値, i番目の頂点までの最大の値)の組み合わせは高々50 × 50 = 2,500通りであるはず
- (i番目, i番目の頂点までの最小の値, i番目の頂点までの最大の値)としても、その組み合わせ数は高々50 × 50 × 50 = 125,000 = 1.25 × 105
- メモ化で十分間に合うはず
- メモ化再帰で実装を開始した
- なんだかんだで20分ほどかかってしまったが、テストも通ったので投稿した
- システムテストを落とす。TLEであった
- メモ化の実装を間違えていた
- dfs関数の最後を「return r;」としていた orz
以下は訂正した実装(システムテストを通る)。
class ProblemsToSolve { public: int minNumber(std::vector<int> pleasantness, int variety) { pleasantness_ = pleasantness; variety_ = variety; size_ = pleasantness.size(); memo_.clear(); return std::min(std::min(dfs(1, pleasantness[0], pleasantness[0]) + 1, dfs(2, pleasantness[0], pleasantness[0]) + 1), size_); }; private: int dfs(int i, int j, int k) { int key = ((i * 1024 + j) * 1024) + k; if (memo_.count(key)) return memo_[key]; j = std::min(pleasantness_[i], j); k = std::max(pleasantness_[i], k); if (std::abs(j - k) >= variety_) return memo_[key] = 1; int r = INF; if (i + 1 < size_) r = std::min(dfs(i + 1, j, k) + 1, r); if (i + 2 < size_) r = std::min(dfs(i + 2, j, k) + 1, r); return memo_[key] = r; }; private: std::vector<int> pleasantness_; int variety_; int size_; std::map<int, int> memo_; };
- 信じられないくらい簡潔な実装が掲載されていた
- {|pi - pj| | i < j}が与えられた閾値よりも大きいペアを先に全探索している
- また、先日考察したWarshall-Floyd法に近い実装のようにも感じる
- あ
- いきなり全貌が見えてきた
- これはグラフの問題であったのだ
- しかも先日@simezi_tanさんにご教授いただいたグラフの問題に近いように感じる
- 類似問題でもあるし、しっかり考察することにした
- まずは全探索について考えてみる
- 以下を満たすiとjのペアを考える
- これらのペアを含む経路は条件を必ず満たす
- i < jとしているので、頂点0、i、jを通ればやはり条件を満たす
- 条件を満たす経路の中で訪れる頂点の数が最小のものを探せばいい
- 図示しよう
- 閾値を6とすると、2と8の頂点を通る必要がある
- 任意の頂点iとjの間の最短距離をδ(i, j)とする
- 頂点4と2、8を通る最短経路は以下のように表すことができる
- 任意の頂点のペアの最短経路の距離が分かれば、これを計算できる
- ならば、Warshall-Folyd法だ
- そのために、隣接行列を用意する。アスタリスクは接続されていないことを表し、実際の行列での値は無限大だ
Warshall-Floyd法を用いた実装(システムテストを通る)。
#define INF 1000000000 class ProblemsToSolve { public: int minNumber(std::vector<int> pleasantness, int variety) { int size = pleasantness.size(); std::vector<std::vector<bool> > valid(size, std::vector<bool>(size)); for (int i = 0; i < size; i ++) for (int j = i + 1; j < size; j ++) valid[i][j] = (std::abs(pleasantness[i] - pleasantness[j]) >= variety); std::vector<std::vector<int> > m(size, std::vector<int>(size, INF)); for (int i = 0; i < size; i ++) { if (i + 1 < size) m[i][i+1] = 1; if (i + 2 < size) m[i][i+2] = 1; } for (int k = 0; k < size; k ++) for (int i = 0; i < size; i ++) for (int j = 0; j < size; j ++) m[i][j] = std::min(m[i][j], m[i][k] + m[k][j]); m[0][0] = 0; int cp = INF; for (int i = 0; i < size; i ++) for (int j = 0; j < size; j ++) if (valid[i][j]) cp = std::min(1 + m[0][i] + m[i][j], cp); return std::min(cp, size); }; };
- Warshall-Floydを適用した結果、隣接行列は以下のようになる
- 経路の辺の数がはδ(0, 2) + δ(2, 5)を計算すればいい(1 + 2 = 3)
- 辺の数が3であるため、頂点の数は3 + 1 = 4
- 例外があった
- 通らなければならない初め頂点が0のとき、最短経路はδ(0, 0) + δ(0, j)として計算する
- しかしδ(0, 0)は無限大が収められているので、誤動作する
- 便宜上δ(0, 0)を0としておけばこれを実現できる
- グラフの問題としても解くことが出来た
- しかし、チラ見したエディトリアルの実装のようなシンプルさに欠ける
- エディトリアルを今一度読む
- ああ、なるほど
- これは先日考察したグラフの処理に近い
- 頂点iからjまでにn個の頂点がある場合、最短経路の辺の数は以下の式で計算出来る
- 頂点0からiのグラフを見てみよう。この場合nは3。確かにそうなっている
- 頂点iからjへのグラフには最短経路が2種類ある。nは4。最短経路は双方ともに2だ
- これを実装してみよう
エディトリアルを熟読してからの実装(システムテストを通る)。
class ProblemsToSolve { public: int minNumber(std::vector<int> pleasantness, int variety) { int size = pleasantness.size(); int cp = size; for (int i = 0; i < size; i ++) for (int j = i + 1; j < size; j ++) if (std::abs(pleasantness[i] - pleasantness[j]) >= variety) cp = std::min(1 + (i + 1) / 2 + (j - i + 1) / 2, cp); return cp; }; };