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 $\mathit{C}\mathit{L}\mathit{A}\mathit{S}\mathit{S}\mathit{N}\mathit{A}\mathit{M}\mathit{E}$ {

    public: $\mathit{R}\mathit{E}\mathit{T}\mathit{U}\mathit{R}\mathit{N}\mathit{T}\mathit{Y}\mathit{P}\mathit{E}$ $\mathit{M}\mathit{E}\mathit{T}\mathit{H}\mathit{O}\mathit{D}\mathit{N}\mathit{A}\mathit{M}\mathit{E}$($\mathit{M}\mathit{E}\mathit{T}\mathit{H}\mathit{O}\mathit{D}\mathit{P}\mathit{A}\mathit{R}\mathit{A}\mathit{M}\mathit{S}$) {
        return $\mathit{D}\mathit{U}\mathit{M}\mathit{M}\mathit{Y}\mathit{R}\mathit{E}\mathit{T}\mathit{U}\mathit{R}\mathit{N}$;
    }

};

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 にはできるだけ参加したいと思っています。