読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2016 - Round 1B

4/30(土) 25:00〜27:30
C-smallまで取れて70点596位。1000位以内に入れたのでRound 2(+ Distributed Code Jam) 進出決定!
(C-largeも諦めずに書き続けて27:39にpractice roomでAC出せたので、あと9分あれば全完でした)

A. Getting the Digits

電話番号の各桁を ZERO ONE TWO みたいに読んだのをシャッフルした OZONETOWER みたいな文字から元の012を復元する問題。電話番号の数字は昇順。

'Z'は"ZERO"にしか使われてない、みたいな文字が5つあって、0,2,4,6,8はすぐに分かる。残りの1,3,5,7,9も同様に絞っていくと全てが一意に定まる。

small/large共通コード。(AC)

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

string solve(string& s) {
  vector<int> st(256, 0);  // 256とか取ってるのは添字の可読性のため。(それでも'Z'+1で十分)
  rep(i, s.size()) {
    ++st[s[i]];
  }
  vector<int> ct(10, 0);

  int zero = st['Z'];
  if (zero) {
    ct[0] = zero;
    st['Z'] -= zero; st['E'] -= zero; st['R'] -= zero; st['O'] -= zero;
  }
  int two = st['W'];
  if (two) {
    ct[2] = two;
    st['T'] -= two; st['W'] -= two; st['O'] -= two;
  }
  int four = st['U'];
  if (four) {
    ct[4] = four;
    st['F'] -= four; st['O'] -= four; st['U'] -= four; st['R'] -= four;
  }
  int six = st['X'];
  if (six) {
    ct[6] = six;
    st['S'] -= six; st['I'] -= six; st['X'] -= six;
  }
  int eight = st['G'];
  if (eight) {
    ct[8] = eight;
    st['E'] -= eight; st['I'] -= eight; st['G'] -= eight; st['H'] -= eight; st['T'] -= eight;
  }
  int three = st['R'];
  if (three) {
    ct[3] = three;
    st['T'] -= three; st['H'] -= three; st['R'] -= three; st['E'] -= three*2;
  }
  int seven = st['S'];
  if (seven) {
    ct[7] = seven;
    st['S'] -= seven; st['E'] -= seven*2; st['V'] -= seven; st['N'] -= seven;
  }
  int five = st['V'];
  if (five) {
    ct[5] = five;
    st['F'] -= five; st['I'] -= five; st['V'] -= five; st['E'] -= five;
  }
  int one = st['O'];
  if (one) {
    ct[1] = one;
    st['O'] -= one; st['N'] -= one; st['E'] -= one;
  }
  int nine = st['E'];
  if (nine) {
    ct[9] = nine;
    st['N'] -= nine; st['I'] -= nine; st['N'] -= nine; st['E'] -= nine;
  }
  stringstream ss;
  rep(i,10) {
    if (ct[i]) {
      rep(j,ct[i]) ss << i;
    }
  }

  return ss.str();
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    string s; cin >> s;
 answer:
    cout << "Case #" << (1+_t) << ": " << solve(s) << endl;
  }
}

B. Close Match

2つの整数c,jがあって、隠されてる桁がいくつかあって、(abs(c-j), c, j) が最小な (c, j) を答える問題。
smallは3桁まで、largeは18桁まで。

smallは愚直に c, j 総当たり。

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

bool match(string& S, int n) {
  int L = S.size();
  for (int i=L-1; i>=0; --i) {
    if (S[i] != '?') {
      int c = S[i] - '0';
      if (c != n % 10) return false;
    }
    n /= 10;
  }
  return true;
}

string pad(int n, int l) {
  vector<char> tmp(l, '0');
  for (int i=l-1; i>=0; --i) {
    tmp[i] = '0' + (n % 10);
    n /= 10;
  }
  return string(all(tmp));
}

pair<string,string> solve(string& C, string& J) {
  int L = C.size();

  int p = 1; rep(i,L) p *= 10;
  pair<string,string> ans;
  set<int> sc, sj;
  rep(i,p) if (match(C,i)) sc.insert(i);
  rep(i,p) if (match(J,i)) sj.insert(i);
  vector< vector<int> > tmp;
  tr(it,sc){
    int c = *it;
    tr(jt,sj){
      int j = *jt;
      vector<int> o(3);
      o[0] = abs(c-j);
      o[1] = c;
      o[2] = j;
      tmp.push_back(o);
    }
  }
  sort(all(tmp));
  int c = tmp[0][1], j = tmp[0][2];
  return make_pair(pad(c, L), pad(j, L));
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    string c, j; cin >> c >> j;
    pair<string,string> ans = solve(c,j);
 answer:
    cout << "Case #" << (1+_t) << ": " << ans.first << " " << ans.second << endl;
  }
}

largeは左から1桁ずつ、可能な数字を探索してみた。
1) そこまででc, jが一致している場合。C[i]=J[i]=?なら、そこには0か1が入る。一方が0〜9の数字なら、もう一方にはその数字と等しいか±1な数字が来る。
2) そこまででc, jに差がある場合。小さい方は?=9で埋め、大きい方は?=0で埋めていく。
最後の桁まで来たところで配列に (abs(c-j), c, j) を追加しておいて、一番小さいやつの c, j を答える。
queueを使ってBFS的に書いたけど、これ以上の枝刈りはしてないからDFSでも構わないでしょう。

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

vector<int> C, J;
int L;

string pad(ll n) {
  vector<char> tmp(L, '0');
  for (int i=L-1; i>=0; --i) {
    tmp[i] = '0' + (int)(n % 10LL);
    n /= 10LL;
  }
  return string(all(tmp));
}

#define QM 15  // '?' - '0'

typedef pair<int,int> i2;
typedef pair<ll,ll> ll2;

ll2 solve() {
  queue< pair<i2,ll2> > q;
  q.push(make_pair(i2(0,0), ll2(0,0)));

  vector< vector<ll> > tmp;

  while (!q.empty()) {
    int ix = q.front().first.first, cm = q.front().first.second;
    ll c_ = q.front().second.first, j_ = q.front().second.second;
    q.pop();

    if (ix == L) {
      vector<ll> o(3);
      o[0] = abs(c_ - j_);
      o[1] = c_;
      o[2] = j_;
      tmp.push_back(o);
      continue;
    }

    ll c = c_ * 10LL, j = j_ * 10LL;

    ll c0 = 0, j0 = 0;
    if (C[ix] != QM) c0 = C[ix];
    if (J[ix] != QM) j0 = J[ix];

    if (cm == 1) {
      // C < J
      if (C[ix] == QM) c0 = 9;
      if (J[ix] == QM) j0 = 0;
      q.push(make_pair(i2(ix+1,1),ll2(c+c0,j+j0)));
      continue;
    }
    if (cm == -1) {
      // c > j
      if (C[ix] == QM) c0 = 0;
      if (J[ix] == QM) j0 = 9;
      q.push(make_pair(i2(ix+1,-1),ll2(c+c0,j+j0)));
      continue;
    }
    // then cm == 0

    vector<ll2> tmp;
    if (C[ix] == QM) {
      if (J[ix] == QM) {
        // ? ?
        c0 = j0 = 0;
        q.push(make_pair(i2(ix+1,0),ll2(c+c0,j+j0))); // c == j
        c0 = 0; j0 = 1;
        q.push(make_pair(i2(ix+1,1),ll2(c+c0,j+j0))); // c < j
        c0 = 1; j0 = 0;
        q.push(make_pair(i2(ix+1,-1),ll2(c+c0,j+j0))); // c > j
      } else {
        // J[ix] = 0..9
        if (j0 > 0) {
          c0 = j0 - 1;
          q.push(make_pair(i2(ix+1,1),ll2(c+c0,j+j0))); // c < j
        }
        c0 = j0;
        q.push(make_pair(i2(ix+1,0),ll2(c+c0,j+j0))); // c == j
        if (j0 < 9) {
          c0 = j0 + 1;
          q.push(make_pair(i2(ix+1,-1),ll2(c+c0,j+j0))); // c > j
        }
      }
    } else {
      // C[ix] = 0..9
      if (J[ix] == QM) {
        if (c0 > 0) {
          j0 = c0 - 1;
          q.push(make_pair(i2(ix+1,-1),ll2(c+c0,j+j0))); // c > j
        }
        j0 = c0;
        q.push(make_pair(i2(ix+1,0),ll2(c+c0,j+j0))); // c == j
        if (c0 < 9) {
          j0 = c0 + 1;
          q.push(make_pair(i2(ix+1,1),ll2(c+c0,j+j0))); // c < j
        }
      } else {
        int cm;
        if (c0 < j0) cm = 1;
        else if (c0 > j0) cm = -1;
        else cm = 0;
        q.push(make_pair(i2(ix+1,cm),ll2(c+c0,j+j0))); // c == j
      }
    }
  }

  sort(all(tmp));
  return make_pair(tmp[0][1], tmp[0][2]);
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    string c,j; cin >> c >> j;
   L = c.size();
   C.resize(L); J.resize(L);
   rep(i,L) {
     C[i] = c[i] - '0';
     J[i] = j[i] - '0'; // '?' -> 15
   }
    ll2 ans = solve();
 answer:
    cout << "Case #" << (1+_t) << ": " << pad(ans.first) << " " << pad(ans.second) << endl;
  }
}

C. Technobabble

学生が1人ずつ、自分の研究テーマを2ワードで表してリストに書き足して行く。たまに、自分のテーマではなくリストに既に書かれた最初のワードのどれかと二番目のワードのどれかを組み合わせた物を書いていく(fake)奴がいる。シャッフルされたリストから、fakeが最大いくつあるか答える問題。

smallは愚直に…愚直すぎて、N=16なのにリストに書かれた順番をnext_permutation()しちゃって一投目はTLE。
二投目はもうちょいまともな愚直で、本物がどれとどれなのかをbitで表現する形で2^16個のパターンについて、それが可能かどうかを見ていくスタイル。

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int solve(vector<string>& w1, vector<string>& w2) {
  int N = w1.size(); // 1-16
  int P = 1 << N;

  int max_fake = 0;
  rep(p,P) {
    set<string> s1, s2;
    set<int> cand;
    for (int i=0,m=1; i<N; ++i,m<<=1) {
      if (p & m) {
        s1.insert(w1[i]);
        s2.insert(w2[i]);
      } else {
        cand.insert(i);
      }
    }
    int fake = 0;
    tr(it,cand) {
      int i=*it;
      if (found(s1, w1[i]) && found(s2, w2[i])) ++fake;
      else { fake = -1; break; }
    }
    if (fake > max_fake) max_fake = fake;
  }
  return max_fake;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N; cin>>N;
    vector<string> w1(N), w2(N);
    rep(i,N){
      cin >> w1[i] >> w2[i];
    }

 answer:
    cout << "Case #" << (1+_t) << ": " << solve(w1,w2) << endl;
  }
}

largeの制約(N≦1000)だと、これでは到底無理。
何がしかのグラフ理論的アプローチに違いないけど、残り30分強で解けるかな?
二部グラフとか最大フローとかそういう類のものなんだろうとは思うんだけど。

最大fake数 = N - (first, second全ての名前をfakeなしでカバーするのに必要な最小人数)
おもむろにmaximum flowを取っただけでは駄目だよね。カバーできない名前が出てくる。

first, secondともにオリジナルな名前をカバーしている担当の人数が最大フローで得られて、
それでカバーできてないfirstの名前をカバーする担当と、カバーできてないsecondの名前をカバーする担当の数を足せばfakeなしカバーに必要な最小人数が求められるのでは
(追記:↑求めてるのは二部グラフの最大被覆…ですね。はい)
と気づいた時には残り数分

諦めずに実装して、9分オーバーしたけどpractice roomでAC

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

#define infty 987654321
int maximumFlow(const vector<vector<int> >& capacity, int s, int t) {
  int w = capacity.size();
  // residual networks
  vector<vector<int> > resid(w, vector<int>(w,0));
  for(int j=0; j<w-1; ++j){
    for(int k=j+1; k<w; ++k){
      resid[j][k] = capacity[j][k];
      resid[k][j] = 0;
    }
  }
  // find another way
  for (int total=0; ;++total) {
    bool another_way = false;
    vector<int> prev(w, infty);
    queue<pair<int,int> > q; q.push(pair<int,int>(s,-1));
    while (!q.empty()) {
      pair<int,int> p = q.front();
      int node = p.first, prev_node = p.second;
      q.pop();
      prev[node] = prev_node;
      if (node==t) { another_way = true; break; }
      rep(i,w) {
        if (resid[node][i] == 0) continue;
        if (prev[i] < infty) continue;
        q.push(pair<int,int>(i,node));
      }
    }
    // no more ways
    if (!another_way) return total;
    for (int node=t; node!=s; node=prev[node]) {
      int prev_node = prev[node];
      resid[prev_node][node]--;
      resid[node][prev_node]++;
    }
  }
  return 0;
}

int solve(vector<string>& w1, vector<string>& w2) {
  int N = w1.size(); // 1-16
  int P = 1 << N;

  map<string,int> m1, m2;
  vector<string> n1, n2;
  vector<int> x1(N), x2(N);
  int id1 = 0, id2 = 0;
  rep(i,N) {
    int id;
    if (found(m1, w1[i])) {
      id = m1[w1[i]];
    } else {
      m1[w1[i]] = id = id1++;
      n1.pb(w1[i]);
    }
    x1[i] = id;

    if (found(m2, w2[i])) {
      id = m2[w2[i]];
    } else {
      m2[w2[i]] = id = id2++;
      n2.pb(w2[i]);
    }
    x2[i] = id;
  }

  int nodes = 1 + id1 + N + id2 + 1;
  vector<vector<int> > a(nodes, vector<int>(nodes, 0));
  rep(i,id1) a[0][1+i] = 1;
  rep(i,N) {
    int from = 1+x1[i], here = 1+id1+i, to = 1+id1+N+x2[i];
    a[from][here] = 1;
    a[here][to] = 1;
  }
  rep(i,id2) a[1+id1+N+i][1+id1+N+id2] = 1;
  int maxflow = maximumFlow(a, 0, 1+id1+N+id2);
  // printf("maxflow = %d\n", maxflow);

  int over1 = id1 - maxflow, over2 = id2 - maxflow;
  int needed = maxflow + over1 + over2;

  return N - needed;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    int N; cin>>N;
    vector<string> w1(N), w2(N);
    rep(i,N){
      cin >> w1[i] >> w2[i];
    }

 answer:
    cout << "Case #" << (1+_t) << ": " << solve(w1,w2) << endl;
  }
}