Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2014-04-12

2014 TCO Round 1A

03:14 | 2014 TCO Round 1A - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 2014 TCO Round 1A - TopCoder煮ブログ

初の TCO 参加。予習で前回の SRM 616 といたら DIV 1 250 が解けたので気分をよくして開始。

14021603 1182.47 pt (39位/2424人)

○○○ (challenge: 0勝0敗)

EllysSortingTrimmer (250)

文字列のうちの一部分 L 個をソートして、後ろを削る関数がある。何度呼び出してもいいから、一番辞書順で手前になる文字を作りましょう、という問題。

何も考えずに、順番に「後ろから L 個をソートして、最後の 1 個を取り除く」という処理を L 個になるまでやったらいけた。

    string getMin2(string S, int L) {
        int N = S.size();
        for (int i = N - L; i >= 0; i--) {
            sort(S.begin() + i, S.end());
            if (i > 0) {
                S = S.substr(0, S.length() - 1);
            }
        }
        return S;
    }

sort と substr の順番を入れ替えたら、if も不要。

EllysScrabble (500)

文字列のうち、各文字を最大 maxDistance 個横の位置にずらすことができるので、辞書順で手前になるやつを作りましょう、という問題。

先頭の文字は 0~maxDistance のうち、辞書順で一番手間になるやつで決定。

同じように 2 番目は 1~maxDistance + 1 のうち、辞書順で一番手間になるやつ (ただし、さっき選んだやつ以外) でよさそう。おっと、maxDistance が 2、かつ、さっき 1 番目を選んだ場合は、必然的に 0 番目を選ばなきゃいけない。

といったことをコードにした。

    string getMin(string letters, int maxDistance) {
        string S = "";
        int N = letters.size();
        int Used[50];
        memset(Used, 0, sizeof(Used));

        for (int i = 0; i < N; i++) {
            if (i - maxDistance >= 0 && !Used[i - maxDistance]) {
                Used[i - maxDistance] = 1;
                S += letters[i - maxDistance];
                continue;
            }

            char c = 'Z' + 1;
            int index = -1;
            for (int j = -maxDistance; j <= maxDistance; j++) {
                if (i + j < 0 || i + j >= N) continue;

                if (!Used[i + j] && letters[i + j] < c) {
                    index = i + j;
                    c = letters[i + j];
                }
            }
            S += letters[index];
            Used[index] = 1;
        }
        return S;
    }

Challenge で見てたら、フラグの代わりに '*' に置き換えてる人がいて、それならもうちょっとシンプルに書けそう。

EllysLamps (1000)

ランプを全部消したいんだけど、スイッチが壊れてるやつがあって、隣を道連れにするケースがある。

最初の点いている状態は分かっているけど、壊れ方は分からない。最悪の壊れ方をしたときに、消えずに残るスイッチの個数を求めよ、という問題。

なんとなく、YN か NY の塊の個数を求めればいけるかとおもったけど、最後の example が通らない。

よくよく考えると、YYY が最悪の壊れ方をしたとき、1個残ることがある (前2つがそれぞれを道連れにして、最後の1つが手前を道連れにするケース)。

ってことで、先頭から YN、NY、YYY のブロックの個数を数えていけばおしまい。

    int getMin(string lamps) {
        int N = lamps.length();
        int ret = 0;
        for (int i = 0; i < N; i++) {
            if (i + 1 < N && lamps[i] != lamps[i + 1]) {
                ret++;
                i++;
                continue;
            }
            if (i + 2 < N && lamps[i] == 'Y' && lamps[i + 1] == 'Y' && lamps[i + 2] == 'Y') {
                ret++;
                i += 2;
            }
        }
        return ret;
    }

なんとなく動きそうなので submit したら、System Test 通った。

https://docs.google.com/document/d/1O5v5d_iY9zV0slI8fgKhZosDsYDNSZVsOXeL2Cui0DM/pub によると DP で解く必要あるらしいが、DP 苦手なので無理矢理かいてしまった。