TopCoder SRM 648 Div1

Tatsuya Yatagawa
Programming Contest

こんにちはtatsyです。本日もSRMの解説いきます。

Easy (250点)

問題

長さがNでAとBの2種類の文字からなる文字列Sがあるとする。このときある2つのインデックスi, j (i < j)に注目した時、S[i] = A, S[j] = Bとなるような組がK個あるような文字列をどれでも良いので出力せよ。ただし、そのような文字列がない場合には空の文字列を返せ。

解法

この問題の条件を言い換えると、文字列に含まれる各Aについてその右側にあるBの数を合計したものがKになれば良いといえます。

したがって、文字列の前半分が全てAで文字列の後ろ半分が全てBとなるようなものが長さNの文字列に対して最大のKを返してきます。

ですのでM = N / 2としたときM * (N – M)がKより大きいなら、そのKを与える文字列を作ることはできません。

一方、もし作ることが出来るのならば、その文字に含まれるAの数はM個としてよいです。

なぜなら、Aの文字のうち右側にBがあるものを1つ右に動かすと、Kが1減少し、この操作を繰り返していけばK以下の数はいずれも作成可能だからです。

AAAABBBB (K = 16) → AAABABBB (K = 15)

この際、前半にAが連続した状態から一番右のAを最後尾まで移動すると、KはN – M個減少します。

AAAABBBB (K = 16) → AAABBBBA （K = 12)

ですので、この操作を繰り返していって、目的のKまでN – Kを切ったら今、先頭に連続して現れているAのうち一番右にあるものを残りの数分だけ右に動かしてやればいいです。

AABBABBAA (最終的にはこんな感じになる)

これをコードにすると計算量はO(N)です。今回は制約条件が小さいですので、他にもいろいろやり方があると思います。

class AB {
public:
    string createString(int N, int K) {
        int na = N / 2;
        int nb = N - na;
        int ma = na * nb;
        if (ma < K) return "";

        int g = ma - K;
        int last = 0;
        int step = -1;
        while (g > 0) {
            if (g >= nb) {
                last++;
                na--;
                g -= nb;
            }
            else {
                na--;
                step = g;
                g = 0;
            }
        }

        string ret = "";
        for (int i = 0; i < na; i++) ret += "A";
        if (step >= 0) {
            for (int i = 0; i < step; i++) ret += "B";
            ret += "A";
            for (int i = 0; i < nb - step; i++) ret += "B";
        }
        else {
            for (int i = 0; i < nb; i++) ret += "B";
        }
        for (int i = 0; i < last; i++) ret += "A";

        return ret;
    }
};

Medium (550点)

問題

あるスーパーではK種類のリンゴが売られており、各リンゴの値段は1, … , Kである。あなたはこのスーパーでN個のリンゴが買いたいのだが、このスーパーでは値段がiのリンゴをj個買うとj個目のリンゴの値段がi * 2^(j-1)になる。あなたがN個のリンゴを買ったとき、1つのリンゴに払う最大の値段を最小にしたときの金額はいくらか？

解法

まず単純な観察として、リンゴを買うときは確実に値段が安いほうのリンゴから買っていきます。このときに値段がkk円のリンゴまで買うとします。

するとその時に変えるリンゴの数は、kk + kk/2 + kk/4 + … となります。これはプログラムならO(log(kk))で計算可能です。

もし、全てのリンゴを買わなければならないとして、K円払うことにしましょう。このとき払う値段を倍にすると、新しくK個のリンゴを買うことが出来ます。

ですので、K円払った時に買えるリンゴの数をnn個とすると、N-nn個をK個ずつ買っていけばいいことになります。

問題は最後に残った(N – nn) % K個です。これをいくらか払って購入したのですが、この個数を買うために倍の値段を払わなくてはならないリンゴは必ずしも下から順ではないため、二分探索はできません。

さらに払う金額は必ず1, … , Kのいずれかに2の累乗をかけたものになるはずなのでK以上の値段を払うことを許して二分探索するのもあまりうまく行かなさそうです。

そこで、最初に考える値段を(K + 1) / 2円にします。このときも値段を倍々にしていくとKずつ購入できるリンゴが増えていくのは変わりません。

さらに、K個ずつ買っていったときの余りであるrr = (N – nn) % Kは

nn + rr個が最大K円払えば買えるならその時に必要な金額を倍々にしていけばよく、もしnn + rr個がK円払っても買えないのであれば、その時にはK+1円払って値段を倍々にしていけば良いです。

かなり言葉で説明するのは難しいのですが、コードは以下の通りです。

typedef long long lint;

const lint mod = (lint)1.0e9 + 7;

class KitayutaMart {
public:

    lint mod_pow(lint a, lint x) {
        lint ret = 1;
        while (x > 0) {
            if (x % 2 != 0) {
                ret = (ret * a) % mod;
            }
            a = (a * a) % mod;
            x /= 2;
        }
        return ret;
    }

    lint calc(lint n) {
        lint ret = 0;
        while (n > 0) {
            ret += n;
            n /= 2;
        }
        return ret;
    }

    lint binsearch(lint n, lint k) {
        lint lo = 0;
        lint hi = k + 1;
        while (lo < hi) {
            lint mid = (lo + hi) / 2;
            if (calc(mid) < n) {
                lo = mid + 1;
            }
            else {
                hi = mid;
            }
        }
        return lo;
    }

    int lastPrice(lint N, lint K) {
        lint kk = (K + 1) / 2;
        lint nn = calc(kk);
        if (nn >= N) {
            return (int)binsearch(N, K);
        }

        lint pp = (N - nn) / K;
        lint rr = (N - nn) % K;

        lint bb = binsearch(nn + rr, K);
        if (bb == K + 1) {
            return (int)(kk * mod_pow(2, pp + 1) % mod);
        }

        return (int)((bb * mod_pow(2, pp)) % mod);
    }
};

まとめ

今回はEasyは結構素直な問題でやりやすかったです。定数も小さかったので、正解率も高めだったように思います。

Mediumは二分探索でどうにか出来そうというところで、方針的には結構いいところまで来ていたのですが、最初に考える金額を(K + 1) / 2にするというのが思いつかなくて、時間切れでした。

個人的に今回のMediumの解法は結構スマートなんじゃないかと思います(自画自賛)。

というわけで、今回の解説を終わります。最後までお読みいただき、ありがとうございました。