Codeforces Round #129 (Div. 2)

ABCDを解いた。

A: やるだけ
B: どういう数列に変化させるのが最適かは簡単に分かる。1ステップでは出来る限り範囲をインクリメントするべき。
C: dp[ n桁目 ][ 最後に使った数字 ][ 小さくなったか ][ 最初の非 0 の数字 ]
D: やるだけ

以下、本番で投げたコード



A

view plainprint?

1. #include <algorithm>  
2. #include <complex>  
3. #include <iostream>  
4. #include <map>  
5. #include <numeric>  
6. #include <queue>  
7. #include <deque>  
8. #include <set>  
9. #include <sstream>  
10. #include <stack>  
11. #include <vector>  
12.   
13. #include <cassert>  
14. #include <cmath>  
15. #include <cstdio>  
16. #include <cstdlib>  
17. #include <cstring>  
18.   
19. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
20. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
21. #define ALL(c) (c).begin(),(c).end()  
22. #define each(i, c) FOR(i, c)  
23.   
24. typedef long long int lli;  
25.   
26. using namespace std;  
27.   
28. int main(int argc, char *argv[])  
29. {  
30.   int n;  
31.   while (cin >> n) {  
32.     int m[n];  
33.     for (int i = 0; i < n; ++i) {  
34.       cin >> m[i];  
35.     }  
36.   
37.     const string S = "Still Rozdil";  
38.   
39.     const int *mn = min_element(m, m + n);  
40.     if (count(m, m + n, *mn) == 1) cout << mn - m + 1 << endl;  
41.     else cout << S << endl;  
42.   }  
43.   return 0;  
44. }  

#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

typedef long long int lli;

using namespace std;

int main(int argc, char *argv[])
{
  int n;
  while (cin >> n) {
    int m[n];
    for (int i = 0; i < n; ++i) {
      cin >> m[i];
    }

    const string S = "Still Rozdil";

    const int *mn = min_element(m, m + n);
    if (count(m, m + n, *mn) == 1) cout << mn - m + 1 << endl;
    else cout << S << endl;
  }
  return 0;
}

B

view plainprint?

1. #include <algorithm>  
2. #include <complex>  
3. #include <iostream>  
4. #include <map>  
5. #include <numeric>  
6. #include <queue>  
7. #include <deque>  
8. #include <set>  
9. #include <sstream>  
10. #include <stack>  
11. #include <vector>  
12.   
13. #include <cassert>  
14. #include <cmath>  
15. #include <cstdio>  
16. #include <cstdlib>  
17. #include <cstring>  
18.   
19. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
20. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
21. #define ALL(c) (c).begin(),(c).end()  
22. #define each(i, c) FOR(i, c)  
23.   
24. typedef long long int lli;  
25.   
26. using namespace std;  
27.   
28. int main(int argc, char *argv[])  
29. {  
30.   lli n;  
31.   while (cin >> n) {  
32.     lli m[n];  
33.     for (int i = 0; i < n; ++i) {  
34.       cin >> m[i];  
35.     }  
36.   
37.     lli x[n];  
38.     x[0] = m[0];  
39.     for (int i = 1; i < n; ++i) {  
40.       x[i] = max(x[i - 1], m[i]);  
41.     }  
42.   
43.     lli diff[n];  
44.     for (int i = 0; i < n; ++i) {  
45.       diff[i] = x[i] - m[i];  
46.     }  
47.   
48.     lli sum = 0;  
49.   
50.     lli y = 0;  
51.     for (int i = 0; i < n; ++i) {  
52.       if (diff[i] <= y) y = diff[i];  
53.       else {  
54.         sum += diff[i] - y;  
55.         y = diff[i];  
56.       }  
57.     }  
58.   
59.     cout << sum << endl;  
60.   }  
61.   return 0;  
62. }  

#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

typedef long long int lli;

using namespace std;

int main(int argc, char *argv[])
{
  lli n;
  while (cin >> n) {
    lli m[n];
    for (int i = 0; i < n; ++i) {
      cin >> m[i];
    }

    lli x[n];
    x[0] = m[0];
    for (int i = 1; i < n; ++i) {
      x[i] = max(x[i - 1], m[i]);
    }

    lli diff[n];
    for (int i = 0; i < n; ++i) {
      diff[i] = x[i] - m[i];
    }

    lli sum = 0;

    lli y = 0;
    for (int i = 0; i < n; ++i) {
      if (diff[i] <= y) y = diff[i];
      else {
        sum += diff[i] - y;
        y = diff[i];
      }
    }

    cout << sum << endl;
  }
  return 0;
}

C

view plainprint?

1. #include <algorithm>  
2. #include <complex>  
3. #include <iostream>  
4. #include <map>  
5. #include <numeric>  
6. #include <queue>  
7. #include <deque>  
8. #include <set>  
9. #include <sstream>  
10. #include <stack>  
11. #include <vector>  
12.   
13. #include <cassert>  
14. #include <cmath>  
15. #include <cstdio>  
16. #include <cstdlib>  
17. #include <cstring>  
18.   
19. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
20. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
21. #define ALL(c) (c).begin(),(c).end()  
22. #define each(i, c) FOR(i, c)  
23.   
24. typedef long long int lli;  
25.   
26. using namespace std;  
27.   
28. const int D = 20;  
29.   
30. vector<int> v;  
31.   
32. lli memo[D][11][11][12];  
33. lli rec(int d, int last, bool small, int first)  
34. {  
35.   lli &ret = memo[d][last][small][first];  
36.   if (ret != -1) return ret;  
37.   if (v.size() == d) return ret = (last == first);  
38.   
39.   lli sum = 0;  
40.   
41.   if (small) {  
42.     for (int i = 0; i <= 9; ++i) {  
43.       sum += rec(d + 1, i, true, (first == 11 && i ? i : first));  
44.     }  
45.   } else {  
46.     for (int i = 0; i <= v[d]; ++i) {  
47.       sum += rec(d + 1, i, i < v[d], (first == 11 && i ? i : first));  
48.     }  
49.   }  
50.   
51.   return ret = sum;  
52. }  
53.   
54. lli f(lli n)  
55. {  
56.   v.clear();  
57.   while (n) {  
58.     v.push_back(n % 10LL);  
59.     n /= 10LL;  
60.   }  
61.   reverse(v.begin(), v.end());  
62.   
63.   fill(&memo[0][0][0][0], &memo[D][0][0][0], -1);  
64.   return rec(0, 10, false, 11);  
65. }  
66.   
67. int main(int argc, char *argv[])  
68. {  
69.   lli small, large;  
70.   while (cin >> small >> large) {  
71.     cout << f(large) - f(small - 1) << endl;  
72.   }  
73.   return 0;  
74. }  

#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

typedef long long int lli;

using namespace std;

const int D = 20;

vector<int> v;

lli memo[D][11][11][12];
lli rec(int d, int last, bool small, int first)
{
  lli &ret = memo[d][last][small][first];
  if (ret != -1) return ret;
  if (v.size() == d) return ret = (last == first);

  lli sum = 0;

  if (small) {
    for (int i = 0; i <= 9; ++i) {
      sum += rec(d + 1, i, true, (first == 11 && i ? i : first));
    }
  } else {
    for (int i = 0; i <= v[d]; ++i) {
      sum += rec(d + 1, i, i < v[d], (first == 11 && i ? i : first));
    }
  }

  return ret = sum;
}

lli f(lli n)
{
  v.clear();
  while (n) {
    v.push_back(n % 10LL);
    n /= 10LL;
  }
  reverse(v.begin(), v.end());

  fill(&memo[0][0][0][0], &memo[D][0][0][0], -1);
  return rec(0, 10, false, 11);
}

int main(int argc, char *argv[])
{
  lli small, large;
  while (cin >> small >> large) {
    cout << f(large) - f(small - 1) << endl;
  }
  return 0;
}

D

view plainprint?

1. #include <algorithm>  
2. #include <complex>  
3. #include <iostream>  
4. #include <map>  
5. #include <numeric>  
6. #include <queue>  
7. #include <deque>  
8. #include <set>  
9. #include <sstream>  
10. #include <stack>  
11. #include <vector>  
12.   
13. #include <cassert>  
14. #include <cmath>  
15. #include <cstdio>  
16. #include <cstdlib>  
17. #include <cstring>  
18.   
19. #define REP(i, n) for(int i=0; i<(int)n; ++i)  
20. #define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)  
21. #define ALL(c) (c).begin(),(c).end()  
22. #define each(i, c) FOR(i, c)  
23.   
24. typedef long long int lli;  
25.   
26. using namespace std;  
27.   
28. int main(int argc, char *argv[])  
29. {  
30.   int n;  
31.   while (cin >> n) {  
32.     map<lli, lli> F, B;  
33.     pair<lli, lli> p[n];  
34.   
35.     for (int i = 0; i < n; ++i) {  
36.       cin >> p[i].first >> p[i].second;  
37.       ++F[p[i].first];  
38.       if (p[i].first != p[i].second) ++B[p[i].second];  
39.     }  
40.   
41.     const lli H = (n + 1) / 2;  
42.   
43.     const lli inf = 1LL << 60;  
44.     lli mn = inf;  
45.   
46.     for (int i = 0; i < n; ++i) {  
47.       if (H <= F[p[i].first] + B[p[i].first]) {  
48.         lli cost = (H - F[p[i].first]);  
49.         mn = min(mn, cost);  
50.       }  
51.       if (H <= F[p[i].second] + B[p[i].second]) {  
52.         lli cost = (H - F[p[i].second]);  
53.         mn = min(mn, cost);  
54.       }  
55.     }  
56.     mn = max(mn, 0LL);  
57.     cout << (mn == inf ? -1 : mn) << endl;  
58.   }  
59.   return 0;  
60. }  

#include <algorithm>
#include <complex>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <deque>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

typedef long long int lli;

using namespace std;

int main(int argc, char *argv[])
{
  int n;
  while (cin >> n) {
    map<lli, lli> F, B;
    pair<lli, lli> p[n];

    for (int i = 0; i < n; ++i) {
      cin >> p[i].first >> p[i].second;
      ++F[p[i].first];
      if (p[i].first != p[i].second) ++B[p[i].second];
    }

    const lli H = (n + 1) / 2;

    const lli inf = 1LL << 60;
    lli mn = inf;

    for (int i = 0; i < n; ++i) {
      if (H <= F[p[i].first] + B[p[i].first]) {
        lli cost = (H - F[p[i].first]);
        mn = min(mn, cost);
      }
      if (H <= F[p[i].second] + B[p[i].second]) {
        lli cost = (H - F[p[i].second]);
        mn = min(mn, cost);
      }
    }
    mn = max(mn, 0LL);
    cout << (mn == inf ? -1 : mn) << endl;
  }
  return 0;
}