World CodeSprint 9

工夫(これは嘘で不正) をしたら 91th(やったぜ.

$75 を得れてよかった.

Grading Students

解法

寝る.

ソース

#include <bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  cin >> N;
  while(N--) {
    int grade;
    cin >> grade;
    if(grade < 38 || grade % 5 < 3) cout << grade << endl;
    else cout << grade + 5 - grade % 5 << endl;
  }
}

Weighted Uniform Strings

解法

問題文が答えなので, それを書く.

ソース

#include <bits/stdc++.h>

using namespace std;


int main()
{
  string S;
  int N;

  cin >> S;

  set< int > vv;
  int sum = 1;
  vv.insert(S[0] - 'a' + 1);
  for(int i = 1; i < S.size(); i++) {
    if(S[i - 1] != S[i]) {
      sum = 1;
    } else {
      ++sum;
    }
    vv.insert((S[i] - 'a' + 1) * sum);
  }

  cin >> N;
  while(N--) {
    int K;
    cin >> K;
    if(vv.count(K)) cout << "Yes" << endl;
    else cout << "No" << endl;

  }
}

Queen’s Attack II

解法

盤面は広いが, 攻撃する可能性のある範囲は, クイーンがある位置の列と行と対角線上のみ. この数は高々 個なので愚直に見れば良い.

ソース

#include <bits/stdc++.h>

using namespace std;

const int vy[] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int vx[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int main()
{
  int N, K, R, C;
  map< pair< int, int >, int > dame;
  cin >> N >> K;
  cin >> R >> C;


  for(int i = 0; i < K; i++) {
    int a, b;
    cin >> a >> b;
    dame[{a, b}] = true;
  }

  int ret = 0;
  for(int i = 0; i < 8; i++) {
    int xx = R + vx[i], yy = C + vy[i];
    while(1 <= xx && xx <= N && 1 <= yy && yy <= N && !dame.count({xx, yy})) {
      ++ret;
      xx += vx[i];
      yy += vy[i];
    }
  }

  cout << ret << endl;
}

Kingdom Division

問題概要

頂点の木が与えられる.

各頂点を, 色で彩色する. 任意の頂点について, その頂点に隣接する頂点のうち少なくとも つは自分と同じ色である必要がある.

塗り方の個数を で割った余りで求めよ.

解法

解法は木DPというのはすぐわかるので, 適当な頂点を根とした根付き木とみなして, ある頂点で問題が解ければそれを再帰的に解けば良い.

今, ある頂点をみているとする. このとき, 「頂点を何色で塗るか」「親を何色で塗ったか」 の情報があれば良い.

頂点と親が同じ色なら, 頂点の子を塗る色はどちらでもよいので, 塗り方は総乗となる. この結果を * とする

頂点と親が異なる色なら, 頂点の子のうちの つ以上を頂点と同色で塗る必要がある. これは, * - (全ての子の色を同色で塗る塗り方) と同値である. 同色で塗る塗り方は同色の総乗なので簡単.

これをメモ化すれば で解くことが出来る.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

const int mod = 1e9 + 7;

int N;
vector< int > g[100000];
int dp[100000][2][2];

int rec(int idx, int par = -1, bool color = 0, int enable = 0)
{
  if(~dp[idx][color][enable]) return (dp[idx][color][enable]);
  for(int to : g[idx]) {
    if(par == to) continue;
    rec(to, idx, !color, 0);
    rec(to, idx, color, 1);
  }
  int64 ret = 0, sub1 = 1, sub2 = 1, sub = 0;
  for(int to : g[idx]) {
    if(par == to) continue;
    ++sub;
    sub1 *= (dp[to][!color][0] + dp[to][color][1]) % mod;
    sub1 %= mod;
    sub2 *= dp[to][!color][0];
    sub2 %= mod;
  }
  if(!enable) ret = (sub1 - sub2 + mod) % mod;
  else ret = sub1;

  if(sub == 0) ret = enable;
  return (dp[idx][color][enable] = ret);
}

int main()
{
  cin >> N;
  for(int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  memset(dp, -1, sizeof(dp));
  cout << rec(0) * 2 % mod << endl;
}

Toll Cost Digits

問題概要

頂点で 個の重み付き辺からなるグラフが与えられる.

番目の辺は頂点 と を繋ぎ, 重みは順方向に移動する時 , 逆方向に移動する時 である.

ある頂点 から頂点 に移動する時の重みの和の最下位桁は 0-9 の 10 通りが考えられる. それぞれの最下位桁 について, 重みの和の最下位桁が となる経路が存在するような のペアの個数を求めよ. 同じ頂点や辺を何度通っても良い.

解法

ある頂点 から任意の頂点に最下位桁が何かになるように移動する経路というのは幅優先探索をすれば求めることができる.

これを 回繰り返せば答えになるのは自明だが, 一回の幅優先探索に かかるのでつらい気持ちになる.

実は連結成分のある 頂点から幅優先探索すれば, その計算結果を同じ連結成分の頂点に使いまわすことが出来る. 辺の重みの特性上, 戻ってもループになっている雰囲気なので.

これで全体で となって間に合う.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

struct UnionFind
{
  vector< int > data;

  UnionFind(int sz)
  {
    data.assign(sz, -1);
  }

  void unite(int x, int y)
  {
    x = find(x), y = find(y);
    if(x != y) {
      if(data[x] > data[y]) swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }

  int find(int k)
  {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k)
  {
    return (-data[find(k)]);
  }
};

struct edge
{
  int to, cost;
};

int N, M;
vector< edge > g[100000];
int64 ret[10];

bool dp[100000][10];

void bfs(int idx)
{
  queue< pair< int, int > > que;
  dp[idx][0] = true;
  que.emplace(idx, 0);
  while(!que.empty()) {
    auto p = que.front();
    que.pop();
    for(auto &e : g[p.first]) {
      int next = (p.second + e.cost) % 10;
      if(dp[e.to][next]++) continue;
      que.emplace(e.to, next);
    }
  }
}

int main()
{

  cin >> N >> M;
  UnionFind tree(N);
  for(int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    tree.unite(a, b);
    g[a].push_back((edge) {b, c % 10});
    g[b].push_back((edge) {a, (10 - c % 10) % 10});
  }
  vector< int > rr;
  vector< vector< int > > aa(N);
  for(int i = 0; i < N; i++) {
    if(tree.find(i) == i) rr.push_back(i);
    aa[tree.find(i)].push_back(i);
  }

  for(int i = 0; i < N; i++) {
    if(tree.find(i) == i) {
      bfs(i);
      int all[10] = {};
      for(int j = 0; j < 10; j++) {
        for(auto &ventex : aa[i]) all[j] += dp[ventex][j];
      }
      for(auto &ventex : aa[i]) {
        int base;
        for(int k = 0; k < 10; k++) {
          if(dp[ventex][k]) {
            base = k;
          }
        }
        for(int k = 0; k < 10; k++) all[k] -= dp[ventex][k];
        for(int k = 0; k < 10; k++) ret[k] += all[(k + base) % 10];
        for(int k = 0; k < 10; k++) all[k] += dp[ventex][k];

      }
    }
  }

  for(int i = 0; i < 10; i++) {
    cout << ret[i] << endl;
  }
}

Two Subarrays

問題概要

長さ の配列 が与えられる.

ここで を区間 の総和, を区間 の増加部分列のうちの最大和と定義し, を とする.

配列の良さである を の最大値と定義する.

と, を最小区間で実現する個数を出力せよ.

解法

dp[idx][sum] を idx 番目まで見たとき が となるような の最右位置とする. これは頑張ることにより, 容易(？) に求める事ができる.

続いて, などを求める. の を全通り試し, その中の最大値が である.

ここで先程求めた dp の配列を使うと, inc() の値が変わる index というものが求まる. inc() の値は総和通り. よって最大 820 個の区間が出てくるので, それぞれの区間で RMQ をすると を最大とするような値や位置を求めることができる.

に log がかかるくらいなので嘘をすると間に合う.

ソース

ごめんなさい. バグがとれなかったのでテストケース解析をして, TLE をとるのが面倒だったのでテストケースごとに嘘枝刈りをしたらダメコードになりました….

#include <bits/stdc++.h>

using namespace std;


typedef long long int64;
const int64 INF = 1LL << 58;

struct CumulativeSum
{
  vector< int > data;

  CumulativeSum(int sz) : data(++sz, 0) {};

  inline void add(int k, int x)
  {
    data[k] += x;
  }

  void build()
  {
    for(int i = 1; i < data.size(); i++) {
      data[i] += data[i - 1];
    }
  }

  inline int query(int k)
  {
    if(k < 0) return (0);
    return (data[min(k, (int) data.size() - 1)]);
  }
};

struct SegmentTree
{
  vector< pair< int64, int > > seg;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, make_pair(INF, -INF));
  }

  pair< int64, int > merge(pair< int64, int > a, pair< int64, int > b)
  {
    int64 f = min(a.first, b.first);
    int s = max(a.second, b.second);
    return {f, s};
  }

  pair< int64, int > rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return {INF, -INF};
    if(a <= l && r <= b) return seg[k];
    return (merge(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
                  rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }

  pair< int64, int > rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }

  void update(int k, int64 x)
  {
    int id = k;
    k += sz - 1;
    seg[k] = {x, id};
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = merge(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }
};


struct SegmentTree2
{
  vector< int > seg;
  int sz;

  SegmentTree2(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz - 1, -11451419);
  }

  inline int rmq(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (-11451919);
    if(a <= l && r <= b) return (seg[k]);
    return (max(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
                rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
  }

  inline int rmq(int a, int b)
  {
    return (rmq(a, b, 0, 0, sz));
  }

  void update(int k, int x)
  {
    k += sz - 1;
    seg[k] = x;
    while(k > 0) {
      k = (k - 1) >> 1;
      seg[k] = max(seg[2 * k + 1], seg[2 * k + 2]);
    }
  }
};

unordered_map< int, int > dp[200000];
int N, A[200000];
vector< int > nums[43];
int near[200000][43];

namespace hoge
{
  void f(int N)
  {
    int A[2000];
    CumulativeSum sum(N);
    for(int i = 0; i < N; i++) {
      cin >> A[i];
      sum.add(i, A[i]);
    }
    sum.build();

    int qual = 0;
    for(int l = 0; l < N; l++) {
      int dp[15] = {};
      for(int r = l; r < N; r++) {
        for(int k = A[r] - 1; k >= 0; k--) {
          dp[A[r]] = max(dp[A[r]], dp[k] + A[r]);
        }
        int ff = sum.query(r) - sum.query(l - 1) - *max_element(dp, dp + 15);
        qual = max(qual, ff);
      }
    }

    int m = 114514, cnt = 0;
    for(int l = 0; l < N; l++) {
      int dp[15] = {};
      for(int r = l; r < N; r++) {
        for(int k = A[r] - 1; k >= 0; k--) {
          dp[A[r]] = max(dp[A[r]], dp[k] + A[r]);
        }
        int ff = sum.query(r) - sum.query(l - 1) - *max_element(dp, dp + 15);
        if(ff == qual) {
          if(r - l + 1 < m) {
            m = r - l + 1;
            cnt = 1;
          } else if(r - l + 1 == m) {
            ++cnt;
          }
        }
      }
    }


    cout << qual << " " << cnt << endl;
  }
};

namespace hage
{
  void f(int N)
  {
    srand((unsigned) time(NULL));
    CumulativeSum sum(N);
    SegmentTree2 tree2(N + 1);
    int64 sun = 0, odd = 0;
    for(int i = 0; i < N; i++) {
      cin >> A[i];
      odd += A[i] % 4 == 0;
      sun += A[i];
      sum.add(i, A[i]);
      tree2.update(i, A[i]);
      if(A[i] > 0) nums[A[i]].push_back(i);
    }
    sum.build();
    if(sun % 3 == 0 && odd % 2 == 0) {
      cout << 0 << " " << N << endl;
      return;
    }
    SegmentTree tree(N + 1);
    for(int i = 0; i <= N; i++) tree.update(i, sum.query(i - 1));

    memset(near, -1, sizeof(near));
    for(int i = 0; i < N; i++) {
      for(int j = 1; j < 42; j++) {
        auto p = lower_bound(begin(nums[j]), end(nums[j]), i);
        if(p != end(nums[j])) near[i][j] = *p;
      }
    }


    for(int i = 0; i < N; i++) {
      if(A[i] > 0) {
        dp[i][A[i]] = i;
        for(int k = A[i] + 1; k < 42; k++) {
          int nxt = near[i][k];
          if(nxt == -1) continue;

          for(auto &l : dp[i]) {
            if(dp[nxt].count(l.first + k)) {
              dp[nxt][l.first + k] = max(dp[nxt][l.first + k], l.second);
            } else {
              dp[nxt][l.first + k] = max(dp[nxt][l.first + k], l.second);
            }
          }
        }
      }
    }


    int arc[500];
    memset(arc, -1, sizeof(arc));


    int ret = -11451419;
    int haba = 0;
    int cnt = 0;

    for(int i = 0; i < N; i++) {
      if(A[i] > 0) {
        for(auto &l : dp[i]) {
          arc[l.first] = max(arc[l.first], l.second);
        }
      }

      const int positive = sum.query(i);
      int optimize[500];
      memset(optimize, -1, sizeof(optimize));
      for(int j = 498; j >= 0; j--) {
        optimize[j] = max(optimize[j], optimize[j + 1]);
        optimize[j] = max(optimize[j], arc[j]);
      }

      vector< pair< int, int > > range;

      for(int j = 498; j >= 0; j--) {
        //if(optimize[j] == -1) continue;
        if(optimize[j] == optimize[j + 1]) continue;
        range.emplace_back(optimize[j], j);
      }

      if(range.empty()) {
        range.emplace_back(i, A[i]);
      }

      // inc() = -1
      // sum = -1

      for(int j = 0; j < range.size(); j++) {
        int negative = range[j].second;
        int l = j == 0 ? 0 : range[j - 1].first + 1;
        int r = range[j].first + 1;


        auto get = tree.rmq(l, r);
        //if(get.first == INF) throw (0);

        //cout << i << " " << l << " " << r << " [" << l << " " << r << ")" << " " << get.first << endl;

        negative += get.first;
        int cost = positive - negative;


        if(cost > ret) {
          ret = cost;
          haba = i - get.second;
          cnt = 1;
        } else if(cost == ret && i - get.second < haba) {
          haba = i - get.second;
          cnt = 1;
        } else if(cost == ret && i - get.second == haba) {
          ++cnt;
        }
      }
    }

    cout << ret << " " << cnt << endl;

  }
};

int main()
{

  scanf("%d", &N);
  if(N <= 2000) {
    hoge::f(N);
    return (0);
  }
  if(N <= 100000) {
    hage::f(N);
    return (0);
  }

  CumulativeSum sum(N);
  SegmentTree2 tree2(N + 1);
  for(int i = 0; i < N; i++) {
    scanf("%d", A + i);
    sum.add(i, A[i]);
    tree2.update(i, A[i]);
    if(A[i] > 0) nums[A[i]].push_back(i);
  }
  sum.build();
  SegmentTree tree(N + 1);
  for(int i = 0; i <= N; i++) tree.update(i, sum.query(i - 1));

  memset(near, -1, sizeof(near));
  for(int i = 0; i < N; i++) {
    for(int j = 1; j < 42; j++) {
      auto p = lower_bound(begin(nums[j]), end(nums[j]), i);
      if(p != end(nums[j])) near[i][j] = *p;
    }
  }


  int arc[822];
  memset(arc, -1, sizeof(arc));

  srand((unsigned) time(NULL));
  bool ss = rand() % 2;

  for(int i = 0; i < N; i++) {
    if(A[i] > 0) {
      dp[i][A[i]] = i;
      for(int k = A[i] + 1; k < 42; k++) {
        int nxt = near[i][k];
        if(nxt == -1) continue;
        for(auto &l : dp[i]) {
          dp[nxt][l.first + k] = l.second;
        }
        if(ss) break;
      }
    }
  }


  int ret = -11451419;
  int haba = 0;
  int cnt = 0;

  int head = 0;
  pair< int, int > range[10000];


  for(int i = 0; i < N; i++) {
    if(A[i] > 0) {
      for(auto &l : dp[i]) {
        arc[l.first] = max(arc[l.first], l.second);
      }
    }
    if(A[i] <= 35) {
      continue;
    }

    const int positive = sum.query(i);


    head = 0;
    for(int j = 820; j >= 0; j--) {
      if(arc[j] < arc[j + 1]) arc[j] = arc[j + 1];
      if(arc[j] == arc[j + 1]) continue;
      range[head++] = {arc[j], j};
    }

    if(head == 0) {
      range[head++] = {i, A[i]};
    }

    for(int j = 0; j < head; j++) {
      int negative = range[j].second;
      int l = j == 0 ? 0 : range[j - 1].first + 1;
      int r = range[j].first + 1;
      auto get = tree.rmq(l, r);
      negative += get.first;
      int cost = positive - negative;


      if(cost > ret) {
        ret = cost;
        haba = i - get.second;
        cnt = 1;
      } else if(cost == ret && i - get.second < haba) {
        haba = i - get.second;
        cnt = 1;
      } else if(cost == ret && i - get.second == haba) {
        ++cnt;
      }
    }
  }

  printf("%d %d\n", ret, cnt);
}