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

naoya_t@hatenablog

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

Google Code Jam 2016 - Round 2

5/28(土) 23:00〜25:30
今年はTシャツ欲しいなあ、と思いながらの参戦。
残り18秒でD-smallを通して oo o- -- o- で29ptsで1112位。Tシャツにあと一歩及ばず…
(TシャツGETのボーダーラインは同じ29ptsで、2時間12分あたりだった)
とりあえず、今までで一番惜しいところまで行けたと思う。

A. Rather Perplexing Showdown

じゃんけんトーナメント。各参加者は自分の持ち手以外を出さない(ので例えばグーの人とグーの人が対戦したら永遠に終わらない)。参加者の持ち手の分布が与えられている時に、トーナメントがちゃんと終わるような組み合わせが可能か、可能ならどう組むべきか(辞書順で一番早いのを頼む)。

とりあえずsmallを通す。
1<=N<=3、ってことは参加者は高々8人。全permutationを試しても高々8!=40320通り。愚直にnext_permutation()で辞書順に組み合わせを試して、トーナメントが終わる最初のやつを返す。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#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())

int winner[3][3] = { { -1, 0, 2 }, { 0, -1, 1 }, { 2, 1, -1 } };

bool possible(vector<int>& t) {
    int N = t.size();
    vector<int> a(all(t));
    while (N > 1) {
        rep(i, N/2) {
            a[i] = winner[ a[i*2] ][ a[i*2+1] ];
            if (a[i] == -1) return false;
        }
        N /= 2;
        a.resize(N);
    }
    return true;
}
string to_str(vector<int>& t){
    stringstream ss;
    for (int i=0; i<t.size(); ++i) {
        ss << ("PRS"[t[i]]);
    }
    return ss.str();
}

string solve_s(int N, int R, int P, int S) {
    int M = 1 << N;
    vector<int> t;
    rep(i,P) t.pb(0);
    rep(i,R) t.pb(1);
    rep(i,S) t.pb(2);
    do {
        if (possible(t)) return to_str(t);
    } while (next_permutation(all(t)));
    return "IMPOSSIBLE";
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
  int N, // 1-3, 1-12
      R,P,S; // 0..2^N
      cin >> N >> R >> P >> S;

 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << solve_s(N,R,P,S) << endl;
  }
}

smallが通ったところでlargeを考えてみる。
優勝するのがグーだとしたら、決勝の対戦カードはグーとチョキ(でグーが勝って優勝)でしかあり得ない。
準決勝は、グーとチョキ(でグーが勝ち上がる)、チョキとパー(でチョキが勝ち上がる)でしかあり得ない。
とすると、何回戦だろうが組み合わせはいつも1つ。並べ方の問題でしかない。
優勝がチョキの場合、パーの場合も同様なので、全部で3通りしかない。(何も考えずにランダムに作った分布ではほとんどIMPOSSIBLEになる)
与えられたP/R/S分布で行けるか、行けるなら辞書順で一番早いやつを返す。
英語の辞書順は P(Paper=パー)、R(Rock=グー)、S(Scissors=チョキ)で、それぞれを0,1,2と置いてるけど別に'P','R','S'でも問題ないはず。
0 -> 01=10, 1 -> 12=21, 2 -> 20=02 で、辞書順で早いやつだけ辿っていけばいいのか?と思ったら、1 -> 12 -> 1202 となってしまう。1 -> 21 -> 0212 の方が早いからこっちがいい。世代ごとに必要なら前後を入れ替えていく処理が必要。(というかそれだけでいい)。
テストケースを作って計算時間もほとんどかからない事を確認してsubmit→AC。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#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())

string to_str(vector<int>& t){
    stringstream ss;
    for (int i=0; i<t.size(); ++i) {
        ss << ("PRS"[t[i]]);
    }
    return ss.str();
}

string solve_l(int N, int P, int R, int S) {
    string s = "X";
    rep(seed, 3) {
        vector<int> p(1, seed), q;
        rep(i, N) {
            q.clear();
            rep(j, p.size()) {
                switch (p[j]){
                    case 0: q.pb(0); q.pb(1); break;
                    case 1: q.pb(1); q.pb(2); break;
                    case 2: q.pb(0); q.pb(2); break;
                }
            }
            int QS = q.size();
            for (int span=2; span<QS; span*=2) {
                rep(j, QS/span/2) {
                    // compare
                    int base = span*(2*j);
                    bool do_swap = false;
                    rep(k, span) {
                        int a = q[base + k];
                        int b = q[base + span + k];
                        if (a < b) break; // ok
                        if (a > b) { do_swap = true; break; }
                    }
                    rep(k, span) {
                            swap(q[base+k], q[base+span+k]);
                        }
                    }
                }
            }

            swap(p, q);
        }
        vector<int> st(3, 0);
        rep(i, p.size()){
            st[p[i]]++;
        }
        if (st[0] == P && st[1] == R && st[2] == S) {
            string s1 = to_str(p);
            if (s1 < s) s = s1;
        }
    }

    if (s == "X") return "IMPOSSIBLE";
    else return s;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
  int N, // 1-3, 1-12
      R,P,S; // 0..2^N
      cin >> N >> R >> P >> S;

 answer:
    cout << "Case #" << (1+_t) << ": ";
    cout << solve_l(N,P,R,S) << endl;
  }
}

B. Red Tape Committee

メンバーがN人いて、それぞれが賛成に票を投ずる確率がわかっていて、賛成と反対が半々になる確率が最も高くなるように(そのN人の中から)K人を選んだときの、賛成と反対が半々になる確率を求める問題。

とりあえずsmallを通そう。
N<=16だし、nCk全通り試しちゃえ。高々2^16=65536通り。
K人選んだときの「賛成と反対が半々になる確率」はDPで求まる。
そりゃこれで通るだろう、と思ってsubmitしてAC。これ以上の考察をせず次へ進む。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#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())

int N, K;
vector<double> P;

double prob(vector<int>& x) {
    vector<double> p, q;
    p.pb(1.0); // 0人 = 1.0
    rep(i, K) {  // ←←これってK/2+1まで回せば良いのでは?
        q.assign(p.size()+1, 0.0);
        double pi = P[x[i]];
        rep(j, p.size()) {
            q[j]   += p[j] * (1.0 - pi);
            q[j+1] += p[j] * pi;
        }
        swap(p, q);
    }
    return p[K/2];
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cin >> N >> K;
    P.resize(N);
    rep(i,N) cin >> P[i]; // 0.0 <= Pi <= 1.0

    int M = 1 << N;
    double xmax = 0;
    rep(p,M) {
        if (__builtin_popcount(p) != K) continue;
        vector<int> X;
        for (int i=0,m=1; i<N; ++i,m<<=1) {
            if (p & m) {
                X.push_back(i);
            }
        }
        double x = prob(X);
        xmax = max(xmax, x);
    }

 answer:
    printf("Case #%d: %.6f\n", 1+_t, xmax);
  }
}

C. The Gardener of Seville

挑戦者数が少ないので後回し(結局読んでない)

D. Freeform Factory

労働者がN人、機械がN台。操作を知ってる機械しか動かせない。どの機械を選ぶかは早い者勝ち(選択肢が複数ある場合にどれを選ぶかはランダム)。全員が機械を当てがわれないと工場はうまく機能しない。労働者に操作を教えればいいんだけど、教えるにはコストがかかるから、そのコストは最小にしたい。労働者の出勤順によらずにいつでも工場が機能するようにするための最小教育コストを求めよ、と。

とりあえずsmallを考えてみる。
1<=N<=4だし、4人の出勤順を全て(4!=24通り)☓教育するしないの組み合わせ2^(4x4)=65536通りを愚直に全部試してしまおう。
前の人がどんな選択をしようが、後の人に必ず自分が操作できる機械が回ってくるかってどう求めたらいい?なんかこれ数独みたいだよね。
これも愚直に行こう。1人目から順に、機械の選択肢をすべてキューに入れて、そのすべての選択肢において次の人が自分の操作できる機械を選べることを確かめながらN人目まで見ていこう。(BFSっぽい)

…とかなんとか考え考え試行錯誤しながらコード書いてたら残りあと2分。デバッグプリントをコメントアウトして、smallのデータをダウンロードして実行して、submitしてAC取れた時には残り18秒だった。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#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())

bool possible(int N, int pat) {
    vector<int> it(N);
    int M = (1 << N) - 1;
    rep(i,N) it[i] = i;
    do {
        queue<int> q;
        q.push(0);
        rep(i, N) {
            vector<int> v;
            while (!q.empty()) {
                v.pb(q.front()); q.pop();
            }
            int wh = it[i];
            int mp = (pat >> (N*wh)) & M; // whさんの扱えるマシン
            rep(j, v.size()) {
                bool ok = false;
                int qi = v[j];
                for (int j=0,m=1; j<N; ++j,m<<=1) {
                    if (m & mp) {
                        if (!(m & qi)) {
                            q.push(qi | m);
                            ok = true;
                        }
                    }
                }
                if (!ok) return false;
            }
        }
        if (q.empty()) return false;

    } while (next_permutation(all(it)));
    return true;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
      int N; cin >> N; // 1-4
      int NN = N * N; // 1-16
      int M = 1 << NN;
      vector<string> S(N);
      int L = 0;
      rep(i,N) {
          cin >> S[i];
          rep(j,N) {
              int of = i*N + j;
              if (S[i][j] == '1')
                L |= (1 << of);
          }
      }

      int pc_min = N*N;
      rep(p, M) {
          if (p & L) continue;
          // bool bad=false;
          int lp = L | p;
          if (possible(N, lp)) {
             int pc = __builtin_popcount(p);
             pc_min = min(pc_min, pc);
          }
      }

 answer:
    cout << "Case #" << (1+_t) << ": " << pc_min << endl;
  }
}