SRM329 D1M LogCutter

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

長さ$L$の丸太が与えられて，$((A * i) mod (L - 1)) + 1$$(i \in [1, …, K])$の場所を切ることができる．$C$回切れるときに，切った丸太の最大の長さを最小化したい．最大値の最小値と最も左側の切る場所を答える．

切った丸太の最大の長さを二分探索．長さを決め打ちするとこれより長い丸太は無いはずで，切る場所を出来るだけ左にしたいので，右から見ていき，この長さを超えるまでは切らないで，超えたら切れば良い．この切った回数が$C$回以下であるかどうかを見る．切った回数が$C$回よりも小さい場合は，余分に切ってもよいので，最もの左の場所を切ってしまう．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define reach(it,v) for(__typeof((v).rbegin()) it=(v).rbegin();it!=(v).rend();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

set<int> st;
bool ok(int x, int L, int C) {
  int sum = 0, now = L, cnt = 0;
  reach(it, st) {
      if(now - *it > x) return false;
      
      if(sum + (now - *it) <= x) {
          sum += (now - *it);
      } else {
          sum = (now - *it);
          cnt++;
      }

      if(cnt > C) return false;
      now = *it;
  }

  return true;
}

class LogCutter {
  public:
  string bestCut(int L, int A, int K, int C) {
      st.clear();

      rep(i, K) {
          int x = (A * ll(i + 1)) % (L - 1) + 1;
          st.insert(x);
      }
      st.insert(0);

      ll l = 0, r = L;
      while(r - l > 1) {
          ll mid = (l + r) / 2;
          if(ok(mid, L, C)) {
              r = mid;
          } else {
              l = mid;
          }
      }

      int now = L, cut = L, sum = 0, cnt = 0;
      reach(it, st) {
          if(sum + (now - *it) <= l + 1) {
              sum += (now - *it);
          } else {
              cut = now;
              cnt++;
              sum = (now - *it);
          }
          now = *it;
      }
      
      stringstream ss;
      ss << l + 1 << " ";

      if(cnt < C) {
          st.erase(0);
          ss << *(st.begin());
      } else {
          ss << cut;
      }

      return ss.str();
  }
};
Dec 1st, 2016
srm, topcoder, 二分探索