Google Code Jam 2014 Qualification Round

今年も GCJ に参加しているわけですが、無事、Qualification Round は突破した模様です。一応全完。今回も C++11 で書こう、は有効の状態です。あまり活用してないですが。まず最初にテンプレ。

// gcc version 4.8.2 with -std=c++11
 
#include <iostream>
#include <sstream>
#include <iomanip>
 
#include <iterator>
 
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
 
#include <string>
 
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
 
#include <tuple>
#include <initializer_list>
 
#include <cmath>
 
// Boost library can be retrieved from http://www.boost.org/
// 1.52 is used
 
#pragma GCC diagnostic ignored "-Wconversion"
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
#pragma GCC diagnostic warning "-Wconversion"
 
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;
 
#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)
 
using namespace std;
 
template<class Integer>
inline auto
IR(Integer first, Integer  last) -> decltype(boost::irange(first, last))
{ return boost::irange(first, last); }
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        cout << "Case #" << casenum+1 << ": " << endl;
    }
 
    return 0;
}

Range-based for loop 用に IR() を作ってます。元々 REP マクロ(というかマクロ全般)があまり好きではないので基本 Range-based for loop 使用ですが元々のテンプレで使っていた部分から外すほど修正もしていない感じです。では、以下各問題について。

Problem A. Magic Trick

やるだけ。わざわざ set 2 つ作って set 演算してますが、1 つだけ作っといてもう一方は読み込みながら判定、の方が無駄が少ないですね。後、サイズ既知の vector の場合は for(auto &val : v) { cin >> v; } でさくっと読み込めますけどこれくらい簡単に set とかも読み込みたい感じ。inserter みたいな感じでラッパ作ればいけそうではありますが。

set<int> read()
{
    set<int> t;
    int ans; cin >> ans;
    for(int i : IR(1,5)) {
        int n;
        if(i != ans) {
            for(int j: IR(0,4)) { cin >> n; }
        } else {
            for(int j: IR(0,4)) { cin >> n; t.insert(n); }
        }
    }
    return t;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        set<int> s1 = read();
        set<int> s2 = read();
        set<int> sr;
        set_intersection(RNG(s1), RNG(s2), inserter(sr, sr.end()));
        if(sr.size() > 1) {
            cout << "Case #" << casenum+1 << ": " << "Bad magician!" << endl;
        } else if(sr.size() == 0) {
            cout << "Case #" << casenum+1 << ": " << "Volunteer cheated!" << endl;
        } else {
            cout << "Case #" << casenum+1 << ": " << *sr.begin() << endl;
        }
    }
 
    return 0;
}

Problem B. Cookie Clicker Alpha

ループで回した場合のループ回数を確認するのが面倒だったのでへたれて不等式を解いて一撃にしてしまいました。$$ X/{2+(n+1)F} ≤ C/{2+(n+1)F} + X/{2+(n+2)F} $$ n と n+1 で立式すればよかったんですが、なぜか n+1 と n+2 で立ててしまったので微妙にずれた感じです。一応、累積誤差を考えて数が小さい方から加算するようにしていますが気にしなくても良かったかも。

int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin << cases;
    REP(casenum, cases) {
        long double C, F, X; cin << C << F << X;
        int thr = floor((F*X - 2*C - F*C)/(F*C));
        long double result = 0;
        if(thr <= 0) {
            result += X / (2+(thr+1)*F);
            for(int i : IR(0, thr+1)) {
                result += C / (2 + (thr-i)*F);
            }
        } else {
            result = X / 2;
        }
        cout << "Case #" << casenum+1 << ": " << fixed << setprecision(7) << result << endl;
    }
 
    return 0;
}

Problem C. Minesweeper Master

Cookie Clicker には Orteil does not endorse and has no involvement with Google Code Jam. と書いてあるのに Minesweeper には Microsoft Windows への言及があるのに同様の文言がなかったのは何か意味があるのでしょうか。

DP で解いた人も居るようですが、場合わけでやりました。書いてる時には（コピペ分も多いので）そんなに長く書いたつもりはなかったのですが、結果としては結構長いですね。

全体を貫く考え方としては、（1行、あるいは1列の場合でなければ）空きマスが最低2行あるいは2列繋がっていないと広がらない、です。また、c は必ず左上にしています（一般性を失わない）。最初の場合分けとしては、1行の場合、1列の場合、2行の場合、2列の場合、それ以外（3行3列以上）の場合で分けています。行・列を転置してしまえば場合わけは少なくなりますが、転置するのも面倒なんでコピペベースでいいや、という駄目な手抜きです。

1行あるいは1列の場合は、impossible は無しで右端あるいは下端から詰めるだけ。

2行あるいは2列の場合は爆弾が奇数の場合は基本 impossible ですが、1 マスだけ残っている場合は OK。OK の場合は右端あるいは下端から詰めるだけです。

最後、3行3列以上の場合は、さらに場合わけしています。最低2行あるいは2列必要ということから考えると、1) M ≦ (R-2)*(C-2) の場合は、左端および上端2列分を開けておいて右下から詰めていけば良い 2) R*C-M < 9 の場合、R*C-M = 2, 3, 5, 7 の場合 impossible、それ以外の場合は左上の状態は R*C-M の値に合わせて決め打ち、で良いことが分かります。最後、R*C-M ≧ 9 の場合ですが、空きマス8個分は確定、(2,2) の位置で偶奇を調整して、後は右2列を下から1行(2マス)づつ、上2行を右から1列(2マス)づつ埋めていけば良いことになります。

Short input については全入力パターンが (1+2+3+4+5)^2 = 225 通り、制約の数字から全パターンが入力になってそうってことでローカルで全入力作っといて目視で確認してから subumit してます。時間に余裕のある Qualification Round ならではって感じですね。

void c1(int R, int M)
{
    cout << "c" << endl;
    for(int i: IR(0, R - M - 1)) cout << "." << endl;
    for(int i: IR(0, M)) cout << "*" << endl;
}
 
void r1(int C, int M)
{
    cout << "c";
    for(int i: IR(0, C - M - 1)) cout << ".";
    for(int i: IR(0, M)) cout << "*";
    cout << endl;
}
 
void c2(int R, int M)
{
    if(2*R-M == 1) {
        cout << "c*\n";
        for(int i: IR(0, R - 1)) cout << "**" << endl;
    } else if(M % 2 || 2*R-M == 2) {
        cout << "Impossible" << endl;
    } else {
        cout << "c.\n";
        for(int i: IR(0, R - M/2 - 1)) cout << ".." << endl;
        for(int i: IR(0, M/2)) cout << "**" << endl;
    }
}
 
void r2(int C, int M)
{
    if(2*C-M == 1) {
        cout << "c";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
        cout << "*";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
    } else if(M % 2 || 2*C-M == 2) {
        cout << "Impossible" << endl;
    } else {
        cout << "c";
        for(int i: IR(0, C - M/2 - 1)) cout << ".";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
        cout << ".";
        for(int i: IR(0, C - M/2 - 1)) cout << ".";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
    }
}
 
char result[50][50];
void gen(int R, int C, int M)
{
    for(int i: IR(0,R)) { for(int j: IR(0,C)) { result[i][j] = '*'; } }
    if(R*C - M == 1) { // nothing to do
    } else if(R*C - M == 4) {
        result[0][0] = result[0][1] = result[1][0] = result[1][1] = '.';
    } else if(R*C - M == 6) {
        result[0][0] = result[0][1] = result[1][0] = result[1][1] = result[2][0] = result[2][1] = '.';
    } else if(R*C - M == 8) {
        for(int i: IR(0,3)) { for(int j: IR(0,3)) { result[i][j] = '.'; } }
        result[2][2] = '*';
    } else if(R*C - M < 9) {
        cout << "Impossible" << endl;
        return;
    } else if(M <= (R-2)*(C-2)) {
        for(int i: IR(0,2)) { for(int j: IR(0,C)) { result[i][j] = '.'; } }
        for(int i: IR(0,R)) { for(int j: IR(0,2)) { result[i][j] = '.'; } }
        int MM = (R-2)*(C-2);
        for(int i: IR(2, R)) {
            if(M == MM) break;
            for(int j: IR(2,C)) {
                result[i][j] = '.'; --MM;
                if(M == MM) break;
            }
        }
    } else {
        for(int i: IR(0,3)) { for(int j: IR(0,3)) { result[i][j] = '.'; } }
        int MM = R*C - 9;
        if(((R*C-M) % 2) == 0) {
            result[2][2] = '*'; ++MM;
        }
        for(int i: IR(3, R)) {
            if(M == MM) break;
            for(int j: IR(0, 2)) {
                result[i][j] = '.';
            }
            MM-=2;
        }
        for(int i: IR(3, C)) {
            if(M == MM) break;
            for(int j: IR(0, 2)) {
                result[j][i] = '.';
            }
            MM-=2;
        }
    }
    result[0][0] = 'c';
    for(int i: IR(0,R)) { for(int j: IR(0,C)) { cout << result[i][j]; } cout << endl; }
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        int R, C, M; cin >> R >> C >> M;
        cout << "Case #" << casenum+1 << ":" << endl;
        if(R == 1) { r1(C, M); }
        else if(C == 1) { c1(R, M); }
        else if(R == 2) { r2(C, M); }
        else if(C == 2) { c2(R, M); }
        else { gen(R, C, M); }
    }
 
    return 0;
}

Problem D. Deceitful War

War について Ken の戦略は Naomi の戦略に依らないということなので順序は気にしなくとも良いはず。ということで、Ken としては勝つときには最小の余力(Naomi の値以上で最小のものを出す)で勝ち、負けるときは最小で出すという自然な戦略で良いはずです。では、Deceitful War ではどうなのかといことで、とりあえず最初にできるだけ強いカードを捨てさせて（相手の最大に自分の最小をぶつける）、後は先後逆転で計算する形で書いたら結果が合いません（この時点でなんで先後逆転で計算しようと思ったのか細かいことを忘れちゃってます）。入力例の最後をソートして眺めると、勝ちようがない最小の1枚だけ捨てて後は Naomi が全て勝ってるんですよね。ってことで捨てる枚数でループさせて最大値を取る、で一応結果は合うのですが……。ここで天啓。「あれ？相手のカードも戦略も全部分かってるんだから相手の出すカード全部操作できるんじゃね？」これで先後逆転で一発計算すればいいや、となりました。実際には submit 時点では宣言した値と勝敗が異なってはいけないという条件を忘れていたので考えが足りなかったのですが、Ken の最大値より大きな値を言い続ければ最小から出てくるのでそこで勝ち続けて、勝てなくなるところからは最小値より小さな値を言い続ければやっぱり小さい方から出てきてそこで負ければよい、となるので問題ないことになります(仮に本当にこのまま実際にに人間相手にやったら普通ばれるでしょうけれども)。

int calc_war(const set<double> &naomi, set<double> ken)
{
    int ret = 0;
    for(double i : naomi) {
        auto it = ken.upper_bound(i);
        if(it != ken.end()) {
            ken.erase(it);
        } else {
            ken.erase(ken.begin());
            ++ret;
        }
    }
    return ret;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        set<double> naomi, ken;
        int N; cin >> N;
        for(int i: IR(0, N)) { double t; cin >> t; naomi.insert(t); }
        for(int i: IR(0, N)) { double t; cin >> t; ken.insert(t); }
        size_t result_war = calc_war(naomi, ken);
        size_t result_dwar = naomi.size() - calc_war(ken, naomi);;
        cout << "Case #" << casenum+1 << ": " << result_dwar << ' ' << result_war << endl;
    }
 
    return 0;
}

まとめ

TopCoder Open より Google Code Jam の方が相性がいい感じなのですが、なかでも Qualification Round は時間を気にせずに考えたり書けるんで一番楽しいです。本戦考えるとあんまり良くない参加方法ではありますが。今年もどこまでいけるか分かりませんが、Round1 は突破したいなぁ。