SRM 718 Div1 - ei1333の日記

はじめてDiv1 Med を解けた.

oo- 528.29pts 13th.

1514 -> 1688(+174).

Easy (250) InterleavingParenthesis

TopCoder Statistics - Problem Statement

問題概要

‘(’ と ‘)’ からなる文字列 ${s1, s2(1 \le |s1|, |s2| \le 2500)}$ が与えられる.

${s1, s2}$ のそれぞれの文字は順番を変えずに, 好きなように組み合わせて文字列をつくる.

このうち valid なカッコ列の個数を ${10^9 + 7}$ で割ったあまりで求めよ.

解法

${\mathrm{dp}[x][y] := }$ ${s1}$ の ${x}$ 文字目以降かつ ${s2}$ の ${y}$ 文字目以降の文字列で valid なカッコ列の個数

として, メモ化再帰.

遷移は, ${x}$ か ${y}$ を使うかのどちらか.

カッコがどれだけ開いているかの情報も必要だが, これは ${x}$ と ${y}$ が定まれば一意なので, これを状態に加える必要はないことがわかる.

${O(|s1||s2|)}$ .

ソース

解法も実装も問題概要がわかればはいだった.

典型っぽい.

#include<bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int dp[2555][2555];

class InterleavingParenthesis {
public:

  int rec(int a, int b, int c, string& latte, string& malta)
  {
    if(a == latte.size() && b == malta.size()) return(c == 0);    
    if(~dp[a][b]) return(dp[a][b]);
    int ret = 0;
    if(a < latte.size()) {
      int add1 = latte[a] == '(' ? 1 : -1;
      if(c + add1 >= 0) (ret += rec(a + 1, b, c + add1, latte, malta)) %= mod;
    }
    if(b < malta.size()) {
      int add2 = malta[b] == '(' ? 1 : -1;
      if(c + add2 >= 0) (ret += rec(a, b + 1, c + add2, latte, malta)) %= mod;
    }
    return(dp[a][b] = ret);
  }
  
  int countWays(string s1, string s2) {
    memset(dp, -1, sizeof(dp));
    return(rec(0, 0, 0, s1, s2));
  }
};

Med (500) CircleCity

TopCoder Statistics - Problem Statement

問題概要

${n(2 \le n \le 2000)}$ 個の建物が円環に並んでいて, ${dist_i(1 \le dist_i \le 10^6)}$ は ${i}$ 番目の建物と時計回りに隣接する建物間の距離を表す.

${k(2 \le k \le |dist|)}$ 個のテレポーターを好きな場所に設置でき, ワープ地点間では相互にワープできる.

${d(x, y)}$ を建物 ${x}$ と建物 ${y}$ を移動するときの最短距離とする. また, 街の直径を ${d(x, y)}$ の最大値と定義する.

街の直径の最小値を求めよ.

解法

最大値の最小化なので二分探索したくなる.

${C(x):=}$ 街の直径を ${x}$ にするときの, テレポーターの最小個数

とすれば, 解の二分探索ができるのはそう.

ぐっと睨むと ${C(x)}$ は, すべての建物を長さ ${x}$ の区間で覆うときの, 区間の最小個数と同じことがわかる.

それぞれの区間の中央, すなわち ${\frac x 2}$ の地点にテレポーターを設置する. 別々の区間で覆われた ${2}$ つの建物を考えると, それぞれの建物からテレポーターの距離が ${\frac x 2}$ 以下になっていることより, 建物間の距離が ${x}$ 以下になっていることがわかる.

区間の最小個数というのは ${N}$ 個の始点を決め打ちして, 前から見ていけばできるので解けてしまう(えぇ…

全体の計算量は ${O(n^2 \log \sum dist_i)}$ なのでいえい.

ソース

#include <bits/stdc++.h>

using namespace std;

const int64 INF = 1LL << 55;

int64 N, K, X[4444];

bool beet(int s, int v)
{
  int64 tail = s;
  int64 ret = 0;
  while(tail < s + N) {
    int64 curr = X[tail] + v;
    while(tail < s + N && X[tail] <= curr) ++tail;
    ++ret;
  }
  return(ret <= K);
}

bool C(int v)
{
  for(int i = 0; i < N; i++) {
    if(beet(i, v)) return(true);
  }
  return (false);
}

class CircleCity
{
public:
  int findMin(vector<int> dist, int k)
  {
    N = dist.size();
    K = k;
    
    X[0] = 0;
    int64 L = 0;
    for(int i = 0; i < dist.size(); i++) {
      L += dist[i];
    }
    X[N] = L;
    for(int i = 1; i < dist.size(); i++) {
      X[i] = dist[i - 1];
      X[i] += X[i - 1];
      X[i + N] = X[i] + L;
    }
    int low = -1, high = L;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if(C(mid)) high = mid;
      else low = mid;
    }
    return (high);
  }
};