brly.github.io
ARC
C++
03 Feb 2015

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

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

当日は２問しか解けなかった（◞‸◟）

のでときなおし。

結果

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 がとれないので諦めた（◞‸◟）