SRM443 Mediumを解いてみた
id:chokudaiせんせのオーダーを極める思考法 (1/3) - ITmedia エンタープライズを読んだのでSRM443 Mediumに再挑戦。
そのSRMのときは頭悪いことにダイクストラ法使って制限時間オーバーで落とされたけど。。*1
しかし記事に載ってる方法で普通に解いても面白くないので、幅優先をベースにした力技で解いてみた。オーダーもへったくれもねえなｗ
…こんなの実戦じゃ書けないです＞＜
#include <map> using namespace std; class BinaryFlips{ int hoge[200001]; int queue[200001]; bool visited[200001]; map<int, int> even, odd; public: int skip(int n) { map<int,int>::iterator i = (n%2 == 0) ? even.upper_bound(n) : odd.upper_bound(n) ; -- i; if (i->first <= n && n <= i->second) { return i->second; } return n; } void add(int begin, int last) { if (skip(begin) != skip(last)) { if (begin%2 == 0) even[begin] = skip(last); else odd[begin] = skip(last); } } int minimalMoves(int A, int B, int K) { even[-1] = -1; odd[-1] = -1; int N = A+B; memset(visited, 0, sizeof(visited)); int n = 0; queue[n++] = A; visited[A] = true; hoge[A] = 0; for (int p = 0; p < n; ++ p) { int a = queue[p]; if (a % K == 0) return hoge[a] + a / K; int begin = max(a-K, K-a); int last = min(a+K, 2*N-a-K); for (int i = begin; i <= last; i += 2) { if (i % K == 0) return hoge[a] + 1 + i / K; if (visited[i]) { i = skip(i); } else { visited[i] = true; queue[n++] = i; hoge[i] = hoge[a] + 1; } } add(begin, last); } return -1; } };
