TopCoder SRM 529 Div2

TopCoder

oox
906→963
上昇期到来？

250

intの配列 "start" が与えられる。

start[i - 1] = start[i] / 2;
start[i] = 0;

という操作が任意の回数行える時、start[0]の最大値はいくつか。


全く同じコード書いてる人がいっぱいいて面白かった。

500

"王様の名前 ローマ数字"という書式のstring配列が与えられる。

  1. 王様の名前を辞書順に
  2. ローマ数字は小さい順に

という方法で並べ替えよ。


計算量的に余裕があったので、パースはistringstreamでやってみた。

優先順位付きの並べかえは

  1. STLのpairを使う
  2. 自分でクラスを作って operator < を定義

というやり方が楽。

ローマ数字をどうやって変換するかで書き方が分かれるところですが、「ローマ数字は50まで」と書いてあったので、コピペして全部埋め込んでみた（←
また、ローマ数字の変換はfindを使ってO(N)にしても大丈夫。与えられる配列の要素は50個しか無く、文字の長さも20文字までなので。

1000

long long な整数Nが与えられる。
bag[5] = {N, 0, 0, 0, 0};
に対し、怪しい操作を行い、終了した時のbag[4]の値を計算せよ。ただし操作が終了しない場合は-1を返せ。


とりあえず怪しいコードをC++で書きなおして、無駄なところを省いたりしてみた。
最大ケースを投げてみると、見事にTLEしたので、数学的解法っぽいなぁと目星をつける。

何かしらの数列の可能性もある、ということで、数列大辞典で調べてみたけれど、引っかからなかった。（後でwriterの方が "oeisには載ってないですよ :-)" と言っていたので、調べ方が悪かったわけではなさそう）

100%落ちるコードを提出するわけにもいかないので、最大ケースをクリップボードにコピーしてchallenge phaseを待つ。

challnge phaseが始まって、一番最初に開いたコードが、シミュレーションコードだったので、ｷﾀ━(ﾟ∀ﾟ)━!ということで最大ケースを投げてみたら、「もう撃墜されてるよー^^」と返ってきて、とっても悲しくなった。

250

struct PairingPawns {
    int savedPawnCount(vector <int> start) {
        int N = start.size();
        for(int i = N - 1; i > 0; i--) {
            start[i - 1] += start[i] / 2;
        }
        return start[0];
    }
};

500

int roman_number(string s) {
    string roman[] = {"I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX", "X",
        "XI", "XII", "XIII", "XIV", "XV", "XVI", "XVII", "XVIII", "XIX", "XX",
        "XXI", "XXII", "XXIII", "XXIV", "XXV", "XXVI", "XXVII", "XXVIII", "XXIX", "XXX",
        "XXXI", "XXXII", "XXXIII", "XXXIV", "XXXV", "XXXVI", "XXXVII", "XXXVIII", "XXXIX", "XL",
        "XLI", "XLII", "XLIII", "XLIV", "XLV", "XLVI", "XLVII", "XLVIII", "XLIX", "L"
    };
    return find(roman, roman + 50, s) - roman;
}

struct Node {
    string act, orig;
    Node(string act, string orig) : act(act), orig(orig) {}

    bool operator <(const Node &t) const {
        if(act != t.act) return act < t.act;
        else return roman_number(orig) < roman_number(t.orig);
    }

    string toString() const {
        return act + " " + orig;
    }
};

struct KingSort {
    vector <string> getSortedList(vector <string> kings) {
        vector<Node> names;
        each(it, kings) {
            istringstream is(*it);
            string act, orig;
            is >> act >> orig;
            names.pb(Node(act, orig));
        }
#if 0
        each(it, names) {
            cerr << it->act << "," << it->orig << endl;
        }
#endif
        sort(all(names));
        vector<string> ret;
        each(it, names) {
            ret.pb((*it).toString());
        }
        return ret;
    }
};