• ARC
  • C++
  • 03 Feb 2015

    dwangoプログラミングコンテスト

    dwangoプログラミングコンテスト dwangoからの『挑戦状』

    当日は2問しか解けなかった(◞‸◟)

    のでときなおし。

    結果

    B. ニコニコ文字列

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
    #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
    
    typedef long long ll;
    
    ll add(int len) {
      ll elems = len/2;
      return (elems * (elems+1) / 2);
    }
    
    int main() {
      string s;
    
      while (cin>>s) {
    
        ll ans = 0;
        char c = '_';
        ll len = 0;
    
        const int N = s.size();
    
        for (int i = 0; i < N; i++) {
          char load = s[i];
          //printf("len=%d\n", len);
          if (c == '_') {
            if (load != '2') continue;
            c = load;
            len++;
          }
          else {
            if (c == '2') {
              if (load == '5') {
                len++;
                c = load;
              }
              else {
                if (len) {
                  ans += add(len);
                }
                c = '_';
                len = 0;
              }
            }
            else if (c == '5') {
              if (load == '2') {
                c = load;
                len++;
              }
              else {
                if (len) {
                  ans += add(len);
                }
                c = '_';
                len = 0;
              }
            }
    
            if (c == '_' && load == '2') {
              len++;
              c = '2';
            }
          }
        }
        if (len) {
          ans += add(len);
        }
    
        cout << ans << endl;
      }
      return 0;
    }

    C. ゲーマーじゃんけん

    解説スライドから式そのまま。Pijの計算方法がわからなかった。

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
    #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
    
    const double kEps = 1e-9;
    
    typedef unsigned long long ull;
    typedef pair<int,int> P;
    
    double nCr[102][102];
    
    double E[102];
    
    P combination_type(int rock, int scissor, int paper) {
      vector<int> v;
      if (rock)
        v.push_back(rock);
      if (scissor)
        v.push_back(scissor);
      if (paper)
        v.push_back(paper);
      sort(v.begin(), v.end());
      int mn = v[0];
      int mn_cnt = count(v.begin(), v.end(), mn);
      int sum = rock + scissor + paper;
      P ret;
    
      if (v.size() == 1) {
        ret.first = 3;
        ret.second = 0;
      }
      else if (mn_cnt == 1) {
        ret.first = 1;
        ret.second = sum - mn;
      }
      else if (mn_cnt == 2) {
        ret.first = 2;
        ret.second = sum - mn;
      }
      else {
        ret.first = 3;
        ret.second = 0;
      }
    
      return ret;
    }
    
    double solve(int n) {
      const double kDenom = pow(3, n);
      vector<double> pn(102, 0);
    
      for (int r = 0; r <= n; r++) {
        for (int s = 0; (s + r) <= n; s++) {
          for (int p = 0; (s + r + p) <= n; p++) {
            if (s + r + p < n) continue;
            P tmp = combination_type(r, s, p);
            // printf("r,s,p=%d,%d,%d value=%llu f,s=%d,%d\n",
            //   r, s, p, nCr[n][r] * nCr[n-r][s], tmp.first, tmp.second);
            if (tmp.first == 1 || tmp.first == 2) {
              pn[n - tmp.second] += nCr[n][r] * nCr[n-r][s] / kDenom;
            }
            else {
              pn[n] += nCr[n][r] * nCr[n-r][s] / kDenom;
            }
          }
        }
      }
    
      for (int i = 0; i <= n; i++) {
        //printf("pn[%d] = %.3f\n", i, pn[i]);
        //pn[i] /= kDenom;
      }
    
      // expression
      double ret = pn[n];
      for (int i = 1; i <= n - 1; i++) {
        //printf("compute sum at index=%d\n", i);
        ret += pn[i] * (E[i] + 1);
      }
      ret /= (1 - pn[n]);
    
      return ret;
    }
    
    int main() {
      // nCr
      memset(nCr, 0, sizeof nCr);
      nCr[0][0] = 1;
      for (int i = 1; i <= 100; i++) {
        nCr[i][0] = 1;
        for (int j = 1; j <= i; j++) {
          nCr[i][j] = nCr[i-1][j-1] + nCr[i-1][j];
        }
      }
    
      // do
      memset(E, 0, sizeof E);
      E[1] = 0;
      for (int i = 2; i <= 100; i++) {
        E[i] = solve(i);
        //printf("E[%d] = %.3f\n", i, E[i]);
      }
    
      int in;
      while (scanf("%d", &in) != -1) {
        printf("%.7f\n", E[in]);
      }
      return 0;
    }

    D. タクシー

    部分点1

    1 <-> N 間の移動量を探索して、あとは直線の場合で解く。O(N * bの合計)。

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    #include <numeric>
    
    using namespace std;
    
    typedef long long ll;
    
    const int kN = 100002;
    
    int N;
    ll L;
    
    ll A[kN];
    ll B[kN];
    ll C[kN];
    
    ll S[kN];
    ll T[kN];
    
    ll solve() {
      ll sum_b = accumulate(B, B+N, 0LL);
    
      if (N > 5000 || sum_b > 5000) {
        return -1LL;
      }
    
      ll ans = 1LL<<59;
      ll end_to_start = min(A[N-1], L - A[N-1]);
    
      for (ll init_move = sum_b; init_move >= -sum_b; --init_move) {
        vector<ll> tmp;
        for (int i = 0; i < N; i++) {
          tmp.push_back(B[i]);
        }
    
        tmp[N-1] -= init_move;
        tmp[0] += init_move;
    
        ll cost = abs(init_move) * end_to_start;
        for (int i = 0; i < N-1; i++) {
          ll delta = tmp[i] - C[i];
          tmp[i] -= delta;
          tmp[i+1] += delta;
          cost += abs(delta) * (A[i+1] - A[i]);
        }
    
        ans = min(ans, cost);
      }
    
      return ans;
    }
    
    int main() {
      while (cin>>N>>L) {
        for (int i = 0; i < N; i++) {
          cin >> A[i] >> B[i] >> C[i];
        }
        ll ans = solve();
        cout << ans << endl;
      }
    
      return 0;
    }
    部分点2

    移動量を探索するのではなくT-Sから求める(解説スライド)。O(N^2)。

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    typedef long long ll;
    
    const int kN = 100002;
    
    int N;
    ll L;
    
    ll A[kN];
    ll B[kN];
    ll C[kN];
    
    ll S[kN];
    ll T[kN];
    
    ll solve() {
      if (N > 5000) return -1LL;
    
      memset(S, 0, sizeof S);
      memset(T, 0, sizeof T);
    
      S[0] = B[0];
      T[0] = C[0];
      for (int i = 1; i < N; i++) {
        S[i] = S[i-1] + B[i];
        T[i] = T[i-1] + C[i];
      }
    
      ll ans = 1LL<<59;
      ll end_to_start = min(A[N-1], L - A[N-1]);
    
      for (int z = 0; z < N-1; z++) {
        ll x = T[z] - S[z];
        ll cost = 0;
        vector<ll> tmp;
        tmp.assign(B, B+N);
    
        cost += abs(x) * end_to_start;
        tmp[0] += x;
        tmp[N-1] -= x;
    
        for (int i = 0; i < N; i++) {
          ll delta = tmp[i] - C[i];
          tmp[i] -= delta;
          tmp[i+1] += delta;
          cost += abs(delta) * (A[i+1] - A[i]);
        }
    
        ans = min(ans, cost);
      }
    
      return ans;
    }
    
    int main() {
      while (cin>>N>>L) {
        for (int i = 0; i < N; i++) {
          cin >> A[i] >> B[i] >> C[i];
        }
        ll ans = solve();
        cout << ans << endl;
      }
    
      return 0;
    }
    満点

    解説スライド的には部分点2の解法から凸関数であることが分かるので三分探索で解ける、ということだと思われる。 O(N * lg(100k * N))。

    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    #include <numeric>
    
    using namespace std;
    
    typedef long long ll;
    
    const int kN = 100002;
    
    int N;
    ll L;
    
    ll A[kN];
    ll B[kN];
    ll C[kN];
    
    ll S[kN];
    ll T[kN];
    
    ll tmp[kN];
    ll end_to_start;
    
    ll f(ll x) {
      ll cost = 0;
      for (int i = 0; i < N; i++) {
        tmp[i] = B[i];
      }
    
      cost += abs(x) * end_to_start;
      tmp[0] += x;
      tmp[N-1] -= x;
    
      for (int i = 0; i < N; i++) {
        ll delta = tmp[i] - C[i];
        tmp[i] -= delta;
        tmp[i+1] += delta;
        cost += abs(delta) * (A[i+1] - A[i]);
      }
    
      return cost;
    }
    
    ll solve() {
      ll ans = 1LL<<59;
      end_to_start = min(A[N-1], L - A[N-1]);
      const ll sum_b = accumulate(B, B+N, 0LL);
      ll lb = -sum_b, ub = sum_b;
    
      for (int z = 0; z < 100; z++) {
        ll lhs = (lb+lb+ub) / 3LL;
        ll rhs = (lb+ub+ub) / 3LL;
    
        ll lv = f(lhs);
        ll rv = f(rhs);
        ans = min(ans, min(lv, rv));
    
        if (lv < rv) {
          ub = rhs;
        }
        else {
          lb = lhs;
        }
      }
    
      return ans;
    }
    
    int main() {
      while (cin>>N>>L) {
        for (int i = 0; i < N; i++) {
          cin >> A[i] >> B[i] >> C[i];
        }
        ll ans = solve();
        cout << ans << endl;
      }
    
      return 0;
    }

    E. 電波局

    部分点1.
    #include <iostream>
    #include <sstream>
    #include <fstream>
    #include <string>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <set>
    #include <map>
    #include <algorithm>
    #include <utility>
    #include <bitset>
    #include <cmath>
    #include <cstdlib>
    #include <ctime>
    #include <cstring>
    #include <cstdio>
    
    using namespace std;
    
    #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
    #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
    
    const int kM = 1002, kQ = 1002;
    
    int N, M;
    int A[kM], B[kM], C[kM];
    
    int Q;
    int D[kQ], E[kQ], F[kQ];
    
    bool user[202][202];  // by constraints
    bool tmp[202][202];
    
    void solve() {
      if (N > 200 || M > 200 || Q > 200) {
        for (int i = 0; i < Q; i++) puts("-1");
        return;
      }
    
      memset(user, 0, sizeof user);
      for (int i = 0; i < M; i++) {
        int a = A[i], b = B[i], c = C[i];
        for (int j = 1; j <= c; j++) {
          for (int k = 1; k <= j; k++) {
            int la = a + j - 1;
            int lb = b + k - 1;
            if (lb > la) continue;
            user[la][lb] = 1;
          }
        }
      }
    
      for (int i = 0; i < Q; i++) {
        int d = D[i], e = E[i], f = F[i];
        int val = 0;
    
        memcpy(tmp, user, sizeof user);
    
        for (int j = 1; j <= f; j++) {
          for (int k = 1; k <= j; k++) {
            int ld = d + j - 1;
            int le = e + k - 1;
    
            if (!tmp[ld][le]) {
              tmp[ld][le] = 1;
              ++val;
            }
          }
        }
        printf("%d\n", val);
      }
    }
    
    int main() {
      while (cin >> N >> M) {
        for (int i = 0; i < M; i++) {
          cin >> A[i] >> B[i] >> C[i];
        }
        cin >> Q;
        for (int i = 0; i < Q; i++) {
          cin >> D[i] >> E[i] >> F[i];
        }
        solve();
      }
      return 0;
    }
    部分点2.

    なんか TLE がとれないので諦めた(◞‸◟)