作者別: fuqinho

うまいこと全部あってた！
前も予選は良かったんです、予選は。

A. カードシャッフル

Largeの規模からすると全カードの状態は記憶できないので、目的のカードの状態だけ追う。
最後にW番目にあるカードについてだけ知りたいので、そこから逆の操作をしていって最初にどこにいるかを求める。

#include <iostream>
#include <vector>
using namespace std;

int solve(int M, int C, int W, vector<int>& A, vector<int>& B) {
    for (int i = C - 1; i >= 0; i--) {
        if (W <= B[i]) {
            W += A[i] - 1;
        } else if (W <= A[i] + B[i] - 1) {
            W -= B[i];
        }
    }
    return W;
}

int main() {
    int T, M, C, W, tmpA, tmpB;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        cin >> M >> C >> W;
        vector<int> A;
        vector<int> B;
        for (int j = 0; j < C; j++) {
            cin >> tmpA >> tmpB;
            A.push_back(tmpA);
            B.push_back(tmpB);
        }
        int answer = solve(M, C, W, A, B);
        cout << "Case #" << i << ": " << answer << endl;
    }
}

C. ビット数

貪欲法。与えられた数字の下位ビットから順に見て行って、
・0だったら1と1に分割する。元の数字は繰り下げ(?)が起こる(答えは2増える)
・1だったら0と1に分割(答えは1増える)
とやる手順が答えを最大にするはず。証明はわからない。

#include <iostream>
#include <vector>
using namespace std;

int solve(unsigned long long N) {
    int result = 0;
    while (N != 0) {
        if (N & 1) {
            result += 1;
        } else {
            result += 2;
            N -= 2;
        }
        N = (N >> 1);
    }
    return result;
}

int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        unsigned long long N;
        cin >> N;
        int answer = solve(N);
        cout << "Case #" << i << ": " << answer << endl;
    }
}

B. 最高のコーヒー

これすごい苦しんだ…
まず解法を思いつくまで手こずってた。
初日から順に何らかの基準でコーヒー選びたいんだけど、パラメータ多すぎてがわけが分からない。ナップサック問題的な感じ？とか右往左往。
で、おやつ食べてトイレ行ってたら、あれ逆から埋めればいいんじゃね？って気付いた。これも貪欲法か。
未来になればなるほど賞味期限の関係で飲めるコーヒーが狭まるので、未来の方から順に、その日に飲めるコーヒーの中から一番いいコーヒーを飲んで行ったらトータルでMAX満足になるはず。
証明はわからない。
で、それが分かったはいいけど実装が重い…
バグりまくったけどなんとか通した。

#include <iostream>
#include <vector>
using namespace std;

struct Coffee {
    long long c; // このコーヒーの残りのカップ数
    long long t; // 賞味期限
    int s; // 満足度
    Coffee(long long c, long long t, int s) :
        c(c), t(t), s(s) {}
};

bool GreaterT(const Coffee& lhs, const Coffee& rhs) {
    return lhs.t > rhs.t;
}

// {days}日間で、{coffee}配列の先頭{availableNum}個の種類の中から、
// 満足度が高い順に飲んでいってトータルの満足度を返す
long long consume(int availableNum, vector<Coffee>& coffee, long long days) {
    long long score = 0;
    long long remainDays = days;
    long long remainigCups = 0;
    for (int i = 0; i < availableNum; i++) remainigCups += coffee[i].c;
    // コーヒー飲んでない日が無くなるか、コーヒーが無くなるまで
    // 満足度MAXのコーヒー探して飲めるだけ飲む
    while (remainDays != 0 && remainigCups != 0) {
        int maxS = 0;
        int indexForMaxS = 0;
        for (int i = 0; i < availableNum; i++) {
            if (coffee[i].c != 0 && coffee[i].s > maxS) {
                maxS = coffee[i].s;
                indexForMaxS = i;
            }
        }
        long long cupsToDrink = min(remainDays, coffee[indexForMaxS].c);
        remainDays -= cupsToDrink;
        remainigCups -= cupsToDrink;
        coffee[indexForMaxS].c -= cupsToDrink;
        score += coffee[indexForMaxS].s * cupsToDrink;
    }
    return score;
}

// 貪欲法。期間内のおしりの方から順に満足度高いコーヒーを埋めていく。
long long solve(int N, long long K, vector<Coffee>& coffee) {
    long long score = 0;
    // 期限が遠い順にコーヒーのリストをソート
    sort(coffee.begin(), coffee.end(), GreaterT);

    // 未来の方から、「n日間はi種類のコーヒーが飲める」
    // という区間を取り出して、その期間内でどれだけ満足
    // できるかをconsume()関数で計算する
    long long curT = coffee[0].t;
    int startIndex = 0;
    int availableNum;
    for (int i = 0; i < coffee.size(); i++) {
        // i番目のコーヒーは期限が違う場合、
        // i-1番目までのi種類のコーヒーを飲めた期間を計算して、
        // その期間内でいいやつから飲んだ場合の満足度を足しこむ
        if (coffee[i].t != curT) {
            curT = coffee[i].t;
            long long days = coffee[startIndex].t - coffee[i].t;
            score += consume(i, coffee, days);
            startIndex = i;
        }
        // 初日を含む期間も同じ要領
        if (i == coffee.size() - 1) {
            long long days = coffee[startIndex].t;
            score += consume(coffee.size(), coffee, days);
        }
    }
    return score;
}

int main() {
    int T;
    cin >> T;
    for (int i = 1; i <= T; i++) {
        // read parameter from standard input
        int N;
        long long K;
        cin >> N >> K;
        vector<Coffee> coffee;
        for (int j = 0; j < N; j++) {
            long long c, t; int s;
            cin >> c >> t >> s;
            Coffee cof(c, t, s);
            coffee.push_back(cof);
        }
        // solve and print answer to standard output
        long long answer = solve(N, K, coffee);
        cout << "Case #" << i << ": " << answer << endl;
    }
}

いつものことだけど、ほんと上位陣ハンパない。
問題Bが10分とか、どうなってんの…
10分経過時点なんて、ようやく問題文読み終わってコーヒーカップの落書きしてる頃。
答え知ってる状態でもう一回実装するだけでも倍はかかる自信ある。頭の中見てみたいな

最近、Googleの検索結果に意味不明な機械翻訳ページがやたらひっかかってうざかった。
たとえば、ここ (w3support.net)。Stack Overflowの内容を持ってきてるみたい。

なんとかならんかと思ったら、任意のサイトをブロックできるChrome Extensionでてた。
https://chrome.google.com/webstore/detail/nolijncfnkgaikbjbdaogikpmpbdcdef

この類のサイトは「コンテンツファーム」っていうらしい。
このExtensionでブロックしたサイトはGoogleに送信されるらしいので、せめて大元のサイトより前に引っかからなくなることを祈りつつ…