ei1333の日記

ぺこい

天下一プログラマーコンテスト2016 予選B

20 位までがTシャツで, そんなの無理だよなあって思ってたらこの結果. 本戦参加権まで得てしまった... f:id:ei1333:20160828104108p:plain

問題概要は問題文が日本語なので略.

A - 天下一合成関数

tenka1-2016-qualb.contest.atcoder.jp

解法

書くだけ.

一般のプログラミング言語では, 何も書かないとfloor()になるのでシンプルに書ける.

ソース

f(20)とかf(f(20))とかやっても, 画面には {1} しか出てこなかったのでこれ {1} では？とか思って5分くらい戦ってたけど, 関数の戻り値が bool になってただけだった. ダメ.

#include <bits/stdc++.h>
 
using namespace std;
 
int f(int N)
{
  return((N * N + 4) / 8);
}
int main()
{
  cout << f(f(f(20))) << endl;
}

B - 天下一魔力発電

tenka1-2016-qualb.contest.atcoder.jp

解法

括弧列を扱う問題.

{|S| \le 100} と小さいので適当にDPできそう.

{O(|S|^2)} でもできるらしいけど, 妥協して {O(|S|^3)} でやった.

{dp_{i,j,k}:=} {i} 番目まで見た時に開いている括弧の数が {j}で,カーソルの位置が {k} のときの操作回数の最小値とすれば解ける. 遷移は, 文字を変更するとき {+1}, カーソルを移動するとき {+1}. {j} が負になったら対応する括弧がなくなるのでダメ.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1 << 30;
 
int dp[101][101][101];
string S;
int able[101];
 
int rec(int idx, int depth, int last)
{
  if(depth < 0) return(INF);
  if(idx == S.size()) {
    if(depth == 0) return(last - idx);
    else return(INF);
  }
  if(~dp[idx][depth][last]) return(dp[idx][depth][last]);
  int ret = INF;
  if(S[idx] == '(') {
    ret = min(ret, rec(idx + 1, depth - 1, idx) + 2);
    ret = min(ret, rec(idx + 1, depth + 1, last) + 1);
  } else {
    ret = min(ret, rec(idx + 1, depth - 1, last) + 1);
    ret = min(ret, rec(idx + 1, depth + 1, idx) + 2);
  }
  return(dp[idx][depth][last] = ret);
}
 
int main()
{
  cin >> S;
  memset(dp, -1, sizeof(dp));
  cout << rec(0, 0, 0) << endl;
}

D - 天下一数列にクエリを投げます

tenka1-2016-qualb.contest.atcoder.jp

解法

Cがどう見ても苦手だったので, 一瞬で飛ばして先にDをやることにした. ライブラリを貼る問題.

なんかいろいろ与えられてややこしいので簡単そうなところから方針を立てようとすると, 調査クエリの {K_i} だけが一点に対する指定で簡単そうなことが見てとれる.

{K_i} は配列の位置を指定するもの. 調査クエリ全体を {K_i} でソートして, {1} 番目から {N} 番目までずらしていって順に答えていきたい気持ちになる.

{i - 1} 番目から {i} 番目にずらすときの変化を考える.

  • 初期値の分だけ, 全体が増減する.
  • {i} を左端とする加算クエリ {j} があれば, {j} 番目のイベントから {X_j} 増加する.
  • {i} を右端とする加算クエリ {j} があれば, {j} 番目のイベントから {X_j} 減少する.
  • 調査クエリは, {S_i} 番目から {T_i} 番目のイベントのうちの最小値を求める.

この全ては区間加算とRangeMinimumQueryで実現できるので, SegmentTreeの中でもStarrySkyTreeが使えそうなことが分かる.

ソース

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
 
struct SegmentTree
{
  const int64 INF = 1LL << 58;
 
  vector< int64 > small, add;
  int sz;
 
  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    small.assign(2 * sz - 1, 0);
    add.assign(2 * sz - 1, 0);
  }
  inline void Merge(int k)
  {
    small[k] = min(small[2 * k + 1] + add[2 * k + 1], small[2 * k + 2] + add[2 * k + 2]);
  }
  inline int64 RangeMinimumQuery(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return(INF);
    if(a <= l && r <= b) return(small[k] + add[k]);
    int64 L = RangeMinimumQuery(a, b, 2 * k + 1, l, (l + r) >> 1);
    int64 R = RangeMinimumQuery(a, b, 2 * k + 2, (l + r) >> 1, r);
    return(min(L, R) + add[k]);
  }
  void RangeAdd(int a, int b, int x, int k, int l, int r)
  {
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      add[k] += x;
      return;
    }
    RangeAdd(a, b, x, 2 * k + 1, l, (l + r) >> 1);
    RangeAdd(a, b, x, 2 * k + 2, (l + r) >> 1, r);
    Merge(k);
  }
  int64 RangeMinimumQuery(int a, int b)
  {
    return(RangeMinimumQuery(a, b, 0, 0, sz));
  }
  void RangeAdd(int a, int b, int x)
  {
    return(RangeAdd(a, b, x, 0, 0, sz));
  }
};
 
int main()
{
  int N, A, B;
  vector< tuple< int, int > > add[100005], erase[100005];
  vector< tuple< int, int, int > > qs[100005];
  int64 ans[100005];
 
  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    int x;
    scanf("%d", &x);
    add[i].emplace_back(x, 0);
    erase[i].emplace_back(-x, 0);
  }
 
  scanf("%d", &A);
  for(int i = 1; i <= A; i++) {
    int l, r, x;
    scanf("%d %d %d", &l, &r, &x);
    add[--l].emplace_back(x, i);
    erase[--r].emplace_back(-x, i);
  }
 
  scanf("%d", &B);
  for(int i = 0; i < B; i++) {
    int s, t, k;
    scanf("%d %d %d", &s, &t, &k);
    qs[--k].emplace_back(s, t, i);
  }
 
  SegmentTree tree(A + 1);
  for(int i = 0; i < N; i++) {
    for(auto p : add[i]) {
      int x, y;
      tie(x, y) = p;
      tree.RangeAdd(y, A + 1, x);
    }
    for(auto p : qs[i]) {
      int x, y, z;
      tie(x, y, z) = p;
      ans[z] = tree.RangeMinimumQuery(x - 1, y + 1);
    }
    for(auto p : erase[i]) {
      int x, y;
      tie(x, y) = p;
      tree.RangeAdd(y, A + 1, x);
    }
  }
 
  for(int i = 0; i < B; i++) {
    printf("%lld\n", ans[i]);
  }
}

E - 天下一合体

tenka1-2016-qualb.contest.atcoder.jp

解法

これは本番中には解けなかった.

まず三角不等式より値の数をちょうど {M} にするのが最適.

また値をまとめるので累積和も必要そう.

{\displaystyle s_i = \sum_{ k = 1 }^{ i - 1 } a_n} とする.

{dp_{i,j}:=} {i} 番目までで {j} 個のグループにまとめたときの最小値 とすると,

{dp_{i,j}=\min_{k \le i } {(dp_{k,j-1}} + |s_i-s_k|)} となる. これは {O(N^2M)} だが, 漸化式は見た感じ区間の最小値っぽい. 例によって絶対値部分の符号で場合分けすると, 区間の最小値の形になってSegmentTreeで高速化できる. {O(NM logN)}.

ソース

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

const int64 INF = 1LL << 58;

struct CumulativeSum
{
  vector< int64 > data;

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

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

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

  inline int64 query(int k)
  {
    if(k < 0) return (0);
    return (data[k]);
  }

  inline int64 range(int l, int r)
  {
    return (query(r) - query(l - 1));
  }
};

struct SegmentTree
{
  vector< int64 > small;
  int sz;

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

  void Update(int k, int64 x)
  {
    k += sz - 1;
    small[k] = min(small[k], x);
    while(k > 0) {
      k = (k - 1) >> 1;
      small[k] = min(small[2 * k + 1], small[2 * k + 2]);
    }
  }

  int64 RangeMinimumQuery(int a, int b, int k, int l, int r)
  {
    if(a >= r || b <= l) return (INF);
    if(a <= l && r <= b) return (small[k]);
    int64 L = RangeMinimumQuery(a, b, 2 * k + 1, l, (l + r) >> 1);
    int64 R = RangeMinimumQuery(a, b, 2 * k + 2, (l + r) >> 1, r);
    return (min(L, R));
  }

  int64 RangeMinimumQuery(int a, int b)
  {
    return (RangeMinimumQuery(a, b, 0, 0, sz));
  }

};

int main()
{
  int N, M, A[20000];

  cin >> N >> M;
  CumulativeSum array(N + 1);
  for(int i = 0; i < N; i++) {
    cin >> A[i];
    array.add(i + 1, A[i]);
  }
  array.build();

  vector< int64 > nums(N + 1);
  vector< int > idx(N + 1);
  for(int i = 0; i <= N; i++) nums[i] = array.query(i);
  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));
  for(int i = 0; i <= N; i++) {
    idx[i] = lower_bound(begin(nums), end(nums), array.query(i)) - begin(nums);
  }

  vector< SegmentTree > tree1(M + 1, SegmentTree(nums.size()));
  vector< SegmentTree > tree2(M + 1, SegmentTree(nums.size()));
  tree1[0].Update(idx[0], 0);
  tree2[0].Update(idx[0], 0);

  int64 ret = INF;

  for(int i = 1; i <= N; i++) {
    for(int j = M; j > 0; j--) {
      int64 val = min(tree1[j - 1].RangeMinimumQuery(0, idx[i] + 1) + array.query(i),
                      tree2[j - 1].RangeMinimumQuery(idx[i], nums.size()) - array.query(i));
      tree1[j].Update(idx[i], val - array.query(i));
      tree2[j].Update(idx[i], val + array.query(i));
      if(i == N && j == M) ret = val;
    }
  }

  cout << ret << endl;
}