2014年4月15日火曜日

TopCoder Open 2014 Algorithm Round 1A

システム不調ということで開始できず1週延期になった TCO R1A ですが、今回は System test に問題ってことで今のところ暫定結果でしかないものの、珍しく 1A で通過できたっぽいです。大体 1C 通過なんですけどね。またテンプレからです。今回から TopCoder も C++11 使用ですが吟味が足りない感じ。提出時には適当に削ってから提出してます。

#include <iomanip>
#include <iostream>
#include <sstream>

#include <iterator>

#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>

#include <string>

#include <map>
#include <set>
#include <queue>
#include <stack>

#include <tuple>
#include <initializer_list>

#include <cmath>
#include <cassert>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned int UI;

#define MP make_pair
#define RNG(v) (v).begin(), (v).end()
#define RRNG(v) (v).rbegin(), (v).rend()
struct irange {
    struct irit {
        int value;
        operator int&() { return value; }
        int operator *() { return value; }
    };
    irit begin() const { return { first }; }
    irit end() const { return { last }; }
    int first, last;
};
inline irange IR(int first, int last) { assert(first <= last); return { first, last }; }
template<typename T> struct rpq { typedef std::priority_queue<T, std::vector<T>, std::greater<T> > type; };

using namespace std;

class $CLASSNAME$ {

    public: $RETURNTYPE$ $METHODNAME$($METHODPARAMS$) {
        return $DUMMYRETURN$;
    }

};

GCJ と基本変わりませんが、TopCoder では boost が使えないので IR() だけ似非 range クラスでごまかしています。早いところ range 標準で入ってくれないですかね……。

250. EllysSortingTrimmer

まず最初に問題の意味を取り違えました。複数回使えるをすっ飛ばしてコード書いて実行して例の結果見てから「ふぁ?」ってなりました。それはともかく。1回のソートで L 文字ソートできる訳ですが、結果を引き継ごうとしてずらして実行する時には最大 L-1 文字しか引き継げないわけで右から順に1つづつずらしていったら最終的には先頭文字と先頭以外で最小の L-1 文字からなる文字列のソートになります。

class EllysSortingTrimmer {
    public: string getMin(string S, int L) {
        sort(S.begin() + 1, S.end());
        sort(S.begin(), S.begin() + L);
        return S.substr(0, L);
    }
};

500. EllysScrabble

左側から可能な範囲内で一番小さな値を探して詰めていきますが、可能な範囲の左端に未使用の文字が残っていて次に可能な範囲から外れてしまう場合はそれ使うしかないので強制的に選択します。'~' は使用済みフラグです。string のコンストラクタの引数順序間違えたり、min_element の終端指定で +1 忘れたりしましたがまぁどうにか。結構 C++ らしいコードで書けた気がしています。

class EllysScrabble {
    public: string getMin(string letters, int maxDistance) {
        string result(letters.size(), ' ');
        for(int i : IR(0, letters.size())) {
            if(i >= maxDistance && letters[i - maxDistance] != '~') {
                result[i] = letters[i - maxDistance];
                letters[i - maxDistance] = '~';
            } else {
                auto it = min_element(letters.begin() + max(0, i - maxDistance), letters.begin() + min<int>(letters.size(), i + maxDistance + 1));
                result[i] = *it;
                *it = '~';
            }
        }
        return result;
    }
};

1000. EllysLamps

いつも 1000 出せない感じですが、Example は通ったので記念半分で提出しました。……正直に言えば、休憩時間に駄目だってのに気付くまでは結構テンション高かったです。結局 Challenge されましたがちゃんと気付くもんですね。まぁ YYYNY で駄目なので Challenge する側の方は簡単かもしれませんが。

実例を紙に書きながら Y が残ってしまって駄目な場合はどうなるのか考えたところ、2スイッチの場合は↓の場合だけ2スイッチが独立で変更できません(縦横転置してます)。この場合、NY か YN だとどちらか 1 つは残ってしまいます。これで Example を確認したところ最後の例だけ数字が合いません。

A|AB
B|AB

ぱっと見 YYY と連続しているところが臭そうということでここで 3 スイッチでも書き下してみたところ例えば↓なんかだとYYYで1個残ってしまいます。

A|AB
B|ABC
C|  C

ということでとりあえず書いたのが以下のコードです。

class EllysLamps { // 間違ってます
    public: int getMin(string lamps) {
        int result = 0;
        for(int i: IR(0, lamps.size() - 1)) {
            if(lamps[i] != ' ' && lamps[i] != lamps[i+1]) {
                ++result; lamps[i] = lamps[i+1] = ' ';
            }
        }
        if(lamps.size() >= 3) {
            for(int i: IR(0, lamps.size() - 2)) {
                if(lamps[i] == 'Y' && lamps[i] == lamps[i+1] && lamps[i+1] == lamps[i+2]) {
                    ++result; lamps[i] = lamps[i+1] = lamps[i+2] = ' ';
                }
            }
        }
        return result;
    }
};

先に一通り YN/NY を消してしまってから YYY を調べていますが同じループ内で調べていれば実は通っていたようです。それで良いことが言えていないのであまり意味はないですが。足りないのはこれらのパターンだけでいいのかと、取り方が左から greedy でいいのか、でしょうか。greedy の方は NY, YYY, YN は(これらだけであれば)被っても 1 文字だけで内包もされないのでできるだけ片方に寄せた方がたくさんとれる、でいいかもしれません。これらのパターンだけでいいのかはうーん、2+2とかに分解した場合にその境界を超えるところがあっても高々左右1スイッチしか広がらなくて境界内では逆に独立性があがる、みたいな。あるいは結局これらの最小パターンに帰着できる、ということになるんでしょうか。はっきりこれだと言えない感じです。

まとめ

今回珍しく簡潔に書けちゃったもので、Challenge 中に他の人のコード見てると「なんでこんなややこしいの」って感じになってしまいました。Challenge するには気力が足りなくなってる感じです。今回たまたま R1A で通ってしまいましたが、どう考えてもリハビリが足りない感じなので Parallel Round にはできるだけ参加したいと思っています。

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 は突破したいなぁ。

2014年4月8日火曜日

EclipseCoder C++ プラグインの拡張

競技プログラミング界の雄 TopCoder では競技環境でプラグインの使用が可能ですが、それを利用して Eclipse 上でコーディングできるようにしてしまおうというのが EclipseCoder です。実際便利ではあるのですが、C++ でやっている場合に特に面倒なのが以下 2 点です。

  1. 例えば、Windows 上で VC++ が入っている状態だけど Cygwin GCC を使いたい場合などに、毎回ツールチェインの設定が必要だったりする(環境依存)。
  2. C++11 有効にしたりオプション変えるのも毎回設定が必要。

ということで、これらの設定が可能なように C++ プラグインを修正しました。GitHub のリリースページから net.fornwall.eclipsecoder.ccsupport_0.2.5y1.zip をダウンロード、中の net.fornwall.eclipsecoder.ccsupport_0.2.5.jar で Eclipse インストール先フォルダの同名ファイルを上書きしてください。Window -> Preferences -> EclipseCoder -> C++ の設定下側に、コンボボックスが 2 つ増えています。上がツールチェインの設定、下が設定のコピー元プロジェクトです。

設定コピー元プロジェクトについては EclipseCoder で作成されたプロジェクトを元にした方が無難なので、まずはツールチェインについては自分の使用するものを選び(選択必須)、プロジェクトについては空白にしておきます。この状態でいつものように TopCoder に接続、Practice にでも入って問題を開くと新規プロジェクトが作成されます。この時、特に必須ではありませんが作成されたプロジェクトを設定コピー元プロジェクトだと分かるようリネームしておいてもいいかもしれません。このプロジェクトで EclipseCoder でのプロジェクト作成時に適用しておきたい設定を適当に変更します。例えば (Cygwin GCC で) C++11 有効にする場合だと↓の感じになります。

これで再度 Window -> Preferences -> EclipseCoder -> C++ を開いて、今度は下側のコンボボックスで先ほど設定を変更したプロジェクトを選びます。上側コンボボックスで選択しているツールチェインと整合していなかったりすると OK 時にメッセージが表示されて適用できません。SRM 615 Div2 250 で作成したプロジェクトを設定コピー元プロジェクトにした場合、↓のようになります。

後は、普通に問題を開いていくと先ほどの設定コピー元プロジェクトの設定内容が反映されているはずです。注意点として、設定を取得する際にはプロジェクトがオープンされている必要があるため、設定コピー元プロジェクトは必要があればオープンされます。そしてプラグイン側ではクローズしません。毎回オープン・クローズ繰り返すのもどうかな、と思ったのでこういう仕様になっています。

よろしければ使ってみてください。とりあえずしばらくして問題がなさそうであれば upstream に pullreq を出すつもりです。実のところ 1. については pullreq がすでに upstream にマージ済みでリリースバージョンまで更新されているのですが、にも関わらずサイトでリリースされていません。作者さんが忘れているだけなんじゃないかな、という気もしますが、pullreq 出したときに「Java 初心者なんでチェックしてね」みたいなことを書いてしまったので確認するのもなんだかなと思っているうちに 1 年が経ってしまいました。

なお、本プラグインを使用したせいで Eclipse が落ちて rating 下がった等、いかなる結果についても責任を負いかねますのでその辺は承知の上でお願いします。【追記】もし使用されてる方がいらっしゃいましたら「問題なく動いてるよ」でも良いのでコメントを付けて頂けると嬉しいです。pullreq の支えになりますので。