Codeforces Round #350 (Div. 2) E. Correct Bracket Sequence Editor

問題概要
"("と")"の２種類の文字からなる文字列がある。
この文字列は括弧表現として正しい。
以下の何れかのクエリが与えられる。

• L: カーソルの左に動かす
• R: カーソルを右に動かす
• D: カーソルが指している括弧とそれに対応する括弧の閉区間をすべて削除する

すべてのクエリ処理を行った後の文字列を求めよ。

解法
頑張っていろいろ実装してもいいけど、双方向リストを使って書くのが簡単。
C++の場合は、STLのlistが使える。list.erase()の戻り値は、削除された要素の一つ後ろのiteratorなので、それをそのまま使える。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int n, m, p;
char s[500000+1];
char op[500000+1];
int pr[500000];

void set_pairs() {
  stack <int> stk;
  for (int i = 0; i < n; i++) {
    if (s[i] == '(')
      stk.push(i);
    else {
      int j = stk.top();
      stk.pop();
      pr[i] = j;
      pr[j] = i;
    }
  }
}

void solve() {
  set_pairs();
  
  list<int> lst;
  for (int i = 0; i < n; i++)
    lst.push_back(i);

  --p;
  auto itr = lst.begin();
  while (*itr != p)
    ++itr;

  for (int i = 0; i < m; i++) {
    if (op[i] == 'L')
      --itr;
    else if (op[i] == 'R')
      ++itr;
    else {
      auto ltr = itr;
      auto rtr = itr;

      if (s[*itr] == '(') {
        while (*rtr != pr[*itr])
          ++rtr;
      } else {
        while (*ltr != pr[*itr])
          --ltr;
      }

      itr = lst.erase(ltr, ++rtr);
      if (itr == lst.end())
        --itr;
    }
  }

  string ret;
  for (auto &x: lst)
    ret += s[x];
  printf("%s\n", ret.c_str());
}

int main() {
  scanf(" %d %d %d", &n, &m, &p);
  scanf(" %s", s);
  scanf(" %s", op);
  solve();
  return 0;
}

SRM 644 Div2 1000 TreeCutting

問題概要
木がある。
木のノードのいくつかには数字が書かれている。
木を以下の条件を満たすように、いくつかのコンポーネントに分割することは可能か？

• 各コンポーネントの中に数字が書かれたノードは一つだけ存在する
• 各コンポーネント内のノード数と、コンポーネント内のノードに書かれた数字は等しい

解法
枝(v, w)で木を分断するとする。
このとき、v側のコンポーネントとw側のコンポーネントに分かれる。
各コンポーネント内のノード数と、各コンポーネント内の数値の合計が等しければ、そこで分断してもいいことがわかる。
このような分断の個数は、解状態におけるコンポーネント数 - 1個だけあるはず。
よって、分断数 + 1 = 数字が書かれたノードの数をチェックすればいい。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

vector<int> nums;
vector<int> g[50];

class TreeCutting {
  int cnt(int v, int par) {
    int ret = 1;
    for (auto &w: g[v])
      if (w != par)
        ret += cnt(w, v);
    return ret;
  }

  int sum(int v, int par) {
    int ret = max(0, nums[v]);
    for (auto &w: g[v])
      if (w != par)
        ret += sum(w, v);
    return ret;
  }

public:
  string can(vector<int> par, vector<int> num) {
    int n = num.size();
    int m = 0;
    nums = num;
    REP (i, n) if (num[i] != -1) ++m;
    REP (i, n) g[i].clear();
    REP (i, par.size()) {
      g[par[i]].push_back(i+1);
      g[i+1].push_back(par[i]);
    }
    
    int split = 0;
    REP (i, par.size()) {
      int v = par[i];
      int w = i+1;
      if (cnt(v, w) == sum(v, w) && cnt(w, v) == sum(w, v))
        ++split;
    }

    if (split+1 == m)
      return "POSSIBLE";
    else
      return "IMPOSSIBLE";
  }
};

SRM 642 Div2 1000 TallShoes

問題概要
n個の都市が道路ネットワークで結ばれている。
王様は、都市0から都市n-1まで移動したい。
各道路には高さが設定されており、その値以下の高さの靴を履いている場合のみ、道路を通行することができる。
王様はできるだけ高い靴を履いて移動したい。
移動を開始する前に王様は各道路の高さを上げることができる。道路の高さをx上げるためにはx*xのコストがかかる。予算が与えられるので、移動時に使用できる靴の高さの最大値を求めよ。

解法
靴の高さで二分探索。
靴の高さが決まれば、ノード=都市、エッジのコスト=(靴の高さ - 道路の高さ)^2のようにしてグラフを構築できる。あとは構築したグラフでダイクストラすればいい。
ドワンゴのコンテストでも「二分探索 + ダイクストラ」の問題が出たけど、この組み合わせは面白い。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const long long oo = 1LL<<60;
vector<pair<int, int> > g[50];
long long d[50];

class TallShoes {
  long long calc(long long h, long long l) {
    if (h >= l) return 0;
    return (l-h) * (l-h);
  }
  
  long long dijkstra(int s, int t, int l) {
    typedef pair<long long, int> PLI;
    priority_queue<PLI, vector<PLI>, greater<PLI> > Q;
    fill(d, d+50, oo);
    Q.push({0, 0});
    d[0] = 0;
    while (!Q.empty()) {
      long long v;
      int p;
      tie(v, p) = Q.top();
      Q.pop();
      if (d[p] != v)
        continue;
      for (auto &e: g[p]) {
        int q;
        int h;
        tie(q, h) = e;
        long long tmp = d[p] + calc(h, l);
        if (tmp < d[q]) {
          Q.push({tmp, q});
          d[q] = tmp;
        }
      }
    }
    return d[t];
  }

  void init(vector<int> xs, vector<int> ys, vector<int> hs) {
    REP (i, 50) g[i].clear();
    int sz = xs.size();
    REP (i, sz) {
      g[xs[i]].push_back({ys[i], hs[i]});
      g[ys[i]].push_back({xs[i], hs[i]});
    }
  }
  
public:
  int maxHeight(int N, vector<int> X, vector<int> Y, vector<int> height, long long B) {
    init(X, Y, height);
    int hi = 1<<28;
    int lo = 0;
    while (hi - lo > 1) {
      int mi = (hi + lo) / 2;
      if (dijkstra(0, N-1, mi) <= B)
        lo = mi;
      else
        hi = mi;
    }
    return lo;
  }
};

SRM 643 Div2 1000 TheKingsFactorization

問題概要
木のノードに色を付ける。
色は赤か緑のどちらかを使わなければならない。
あるノードを色xで塗るときのコストは、そのノード以下の部分木で色xで塗られたノードの数に等しい。
すべてのノードを塗るのに必要な最小コストを求めよ。

解法
よくある 木のDP。
根付き木の場合は、親子関係からトポロジカル順序が決まるのでDPで解きやすい。
今回の場合は、状態数を（ノード, そのノード以下の部分木中の何個のノードを赤で塗るか）という形で持っておくことで、すべての子ノードの部分問題が解ければ、親ノードの問題も解ける。
ここで、親ノードで持っている赤ノードの数を、それぞれの子ノードに分配するパターンを全通り試さなければならないが、ここには古典的なナップサック問題が応用できる。
DP in Tree, DP in DPということで面白かった問題。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const int oo = 1<<28;
vector<int> g[55];
int dp[55][55];
int nums[55];

class TheKingsTree {
  void solve(int v) {
    nums[v] = 1;
    for (auto &w: g[v])
      nums[v] += nums[w];

    int ks[55][55];
    REP (i, 55) REP (j, 55) ks[i][j] = oo;
    ks[0][0] = 0;

    for (int i = 0; i < g[v].size(); i++) {
      for (int j = 0; j <= nums[v]; j++) {
        for (int k = 0; j + k <= nums[v]; k++) {
          ks[i+1][j+k] = min(ks[i+1][j+k], ks[i][j] + dp[g[v][i]][k]);
        }
      }
    }

    for (int r = 0; r < nums[v]; r++) {
      dp[v][r+1] = min(dp[v][r+1], ks[g[v].size()][r] + r + 1);
      dp[v][r] = min(dp[v][r], ks[g[v].size()][r] + nums[v] - r);
    }
  }

public:
  int getNumber(vector<int> parent) {
    int n = parent.size() + 1;
    REP (i, 55) g[i].clear();
    REP (i, 55) REP (j, 55) dp[i][j] = oo;
    REP (i, parent.size()) g[parent[i]].push_back(i+1);
    
    for (int i = n-1; i >= 0; i--)
      solve(i);
    
    int ret = oo;
    REP (i, 55) ret = min(ret, dp[0][i]);
    return ret;
  }
};

Google Code Jam 2016 Round 1B

Round 1Bに参加した。
結果は、oooxoxで見事Round 1Cへの出場権を獲得した。
とりあえず復習したので、ソースをはっておく。

A. Getting the Digits
0-9の数字をアルファベットで書いたときに、Zは"ZERO"にしか出てこない。
よってZの数を数えれば、0の数がわかる。
0は消えたので、1-9のアルファベット表記を考える。Xは"SIX"にしか出てこない。
よってXの数を数えれば、6の数がわかる。
6は消えたので{1,2,3,4,5,7,8,9}のアルファベット表記を考える。Wは"TWO"にしか出てこない。よってWの数を数えれば、2の数がわかる。
....
という方針で解く。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int freq[128];
int cnt[10];
tuple<string, char, int> vs[] = {
  {"ZERO", 'Z', 0}, 
  {"SIX", 'X', 6},
  {"TWO", 'W', 2},
  {"FOUR", 'U', 4},
  {"THREE", 'R', 3},
  {"FIVE", 'F', 5},
  {"ONE", 'O', 1},
  {"SEVEN", 'S', 7},
  {"EIGHT", 'T', 8},
  {"NINE", 'I', 9}
};

void solve() {
  string s;
  cin >> s;
  memset(freq, 0, sizeof(freq));
  memset(cnt, 0, sizeof(cnt));

  for (auto &c: s)
    freq[c]++;

  for (auto &v : vs) {
    string x;
    char y;
    int z;
    tie(x,y,z) = v;

    cnt[z] = freq[y];
    for (auto &c: x)
      freq[c] -= cnt[z];
  }

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

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}

B. Close Match
2つの数をA, Bとする。Aの桁数をnとする。
A > Bが確定ならば、Aの後続の?は0で埋め、Bの?は9で埋めればよい。
A < Bが確定ならば、Aの後続の?は9で 埋め、Bの?は0で埋めればよい。

k桁目の値(k=0,1,...,nでループ)が決まると、はじめて上記のいずれかが確定するとする。
すると、i < kまではA[i]とB[i]は完全一致でなければならない。
k桁目の値は全列挙。
k+1桁目以降は、0、または、9で埋めればよい。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

const long long oo = 1LL<<60;
long long diff;
string A, B;
string ra, rb;

void update(const string &a, const string &b) {
  long long d = abs(stoll(a) - stoll(b));
  if (make_tuple(d, a, b) < make_tuple(diff, ra, rb)) {
    diff = d;
    ra = a;
    rb = b;
  }
}

void doit(int k, int p, int q, int r, int s) {
  string a = A;
  string b = B;
  int n = A.size();
  REP (i, k) {
    if (a[i] == '?' && b[i] == '?')
      a[i] = b[i] = '0';
    else if (a[i] == '?')
      a[i] = b[i];
    else if (b[i] == '?')
      b[i] = a[i];
  }
  if (k < n && a[k] == '?') a[k] = '0' + p;
  if (k < n && b[k] == '?') b[k] = '0' + q;
  FOR (i, k, n) {
    if (a[i] == '?') a[i] = r ? '9' : '0';
    if (b[i] == '?') b[i] = s ? '9' : '0';
  }
  update(a, b);
}

void solve() {
  cin >> A >> B;
  diff = oo;
  int n = B.length();

  REP (k, n+1) REP (p, 10) REP (q, 10) REP (r, 2) REP (s, 2) {
    doit(k, p, q, r, s);
  }
  
  cout << ra << " " << rb << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}

C. Technobabble
第一ワードと第二ワードをノードと考えてグラフを構築する。
第一ワードvと第二ワードwがtopicを構成するとき、枝(v, w)をはる。
すると、このグラフは二部グラフになることがわかる。

ある枝集合を選ぶと、すべてのノードが少なくとも1つの枝によってリンクされる
<=>
使わなかった枝はfakeとなる

と考えることができる。fakeの最大値が欲しいので、上記の条件を満たす最小の枝集合を選べばいい。これは最小辺カバーであり、

|最小辺カバー| = ノード数 - |最大マッチング|

という関係から、最大マッチングを求めれば計算できる。

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

class BipartiteMatching {
  int V;
  vector<vector<int> >G;
  vector<int> match;
  vector<bool> used;
  
  bool dfs(int v) {
    used[v] = true;
    for (int i = 0; i < (int)G[v].size(); i++) {
      int u = G[v][i];
      int w = match[u];
      if (w < 0 || (!used[w] && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return true;
      }
    }
    return false;
  }
  
 public:
  BipartiteMatching(int v_size) : V(v_size), G(V), match(V), used(V) {}
  
  void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  int count() {
    int ret = 0;
    fill(match.begin(), match.end(), -1);
    for (int v = 0; v < V; v++) {
      if (match[v] < 0) {
        fill(used.begin(), used.end(), false);
        if (dfs(v))
          ++ret;
      }
    }
    return ret;
  }
};


int n;
string a[1000], b[1000];

map<string, int> s2id(string s[], int n) {
  map<string, int> ret;
  REP (i, n) {
    if (!ret.count(s[i])) {
      int l = ret.size();
      ret[s[i]] = l;
    }
  }
  return ret;
}

void solve() {
  cin >> n;
  REP (i, n) cin >> a[i] >> b[i];
  auto aid = s2id(a, n);
  auto bid = s2id(b, n);

  int an = aid.size();
  int bn = bid.size();

  BipartiteMatching bm(an + bn);
  REP (i, n) bm.add_edge(aid[a[i]], an + bid[b[i]]);
  int edge_cover = an + bn - bm.count();
  cout << n - edge_cover << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }

    return 0;
}