POJ 3276 - Face The Right Way

http://poj.org/problem?id=3276

概要

N 頭の牛が一列に並んでいて，それぞれが前か後ろを向いている． 連続した K 頭の牛の向きを逆にする automatic cow turning machine がある． ただし automatic cow turning machine は牛の向きだけを変えて，牛の位置は変えないことに注意．

すべての牛が前を向いているようにするために必要な automatic cow turning machine の使用回数を最小にするような最小の K を答える．

制約

• 1 <= N <= 5000

解法

1 <= K <= 5000 を全探索した．

ある K について，題意を達成できるかどうかの判定をナイーブに実装すると最悪 O( K^2 ) かかって，全体で O( K^3 ) で TLE． そこで Binary Indexed Tree で判定を O(K log K) でやるようにすると全体で O(K^2 log K) でなんとか通る (1329MS)．

status を見ると普通に数百MSで通されているので，もっとちゃんとした方法がありそう．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 template <class T>
 6 struct BinaryIndexedTree
 7 {
 8   T tree;
 9   const int size;
10   BinaryIndexedTree(const T& t, int s) : tree(t), size(s) {}
11   int read(int i) const
12   {
13     int sum = 0;
14     while (i > 0) {
15       sum += tree[i];
16       i -= i & -i;
17     }
18     return sum;
19   }
20 
21   int read_single(int i) const
22   {
23     int sum = tree[i];
24     if (i > 0) {
25       const int z = i - (i & -i);
26       --i;
27       while (i != z) {
28         sum -= tree[i];
29         i -= (i & -i);
30       }
31     }
32     return sum;
33   }
34 
35   void add(int i, int v)
36   {
37     while (i <= size) {
38       tree[i] += v;
39       i += (i & -i);
40     }
41   }
42 };
43 
44 int main()
45 {
46   int N;
47   scanf("%d", &N);
48   static bool dir[5000];
49   for (int i = 0; i < N; i++) {
50     char c[2];
51     scanf("%1s", c);
52     if (*c == 'F') {
53       dir[i] = true;
54     } else {
55       dir[i] = false;
56     }
57   }
58 
59   static int d[5001];
60   BinaryIndexedTree<int*> bit(d, N);
61   int K = 0, M = 1000000;
62   for (int k = 1; k <= N; k++) {
63     fill_n(d, N+1, 0);
64     int m = 0;
65     for (int i = 0; i <= N-k; i++) {
66       if ((dir[i] + bit.read(i+1)) % 2 == 0) {
67         ++m;
68         bit.add(i+1, 1);
69         bit.add(k+i+1, -1);
70       }
71     }
72     for (int i = N-k; i < N; i++) {
73       if ((dir[i] + bit.read(i+1)) % 2 == 0) {
74         goto FAIL;
75       }
76     }
77     if (m < M) {
78       K = k;
79       M = m;
80     }
81 FAIL:
82     ;
83   }
84   printf("%d %d\n", K, M);
85   return 0;
86 }