AOJ DPL_1_G: Knapsack Problem with Limitations

個数制限付きナップザック問題です。

問題概要

原文 → Knapsack Problem with Limitations | Aizu Online Judge

価値 で重さ であるような 種類の品物と、容量が のナップザックがある。

番目の品物は 個まで使用できる。

ナップザックの容量を超えないように品物を入れた時の価値の最大値を求めよ。

解説

各品物について、品物を 個入れたとき、 個入れたとき・・・と愚直に ずつ増やして考えていくと計算量的に間に合いません。

そこで、繰り返し二乗法のように(厳密には少し違うけど)、取る数を 倍ずつ増やしていくことで考えていきましょう。

例えば品物が 個ある場合は、この場合ですと

• 品物を 個入れたとき
• 品物を 個入れたとき
• 品物を 個入れたとき
• 品物を 個入れたとき

をそれぞれ計算するというわけですね。これで計算量が となり間に合います。

ソースコード

for 文の向きに気をつけましょう。

signed main() {
    int N, W; cin >> N >> W;
    int v[110], w[110], m[110];
    rep(i,0,N) cin >> v[i] >> w[i] >> m[i];

    int dp[10010] = {};
    rep(i,0,N) {
        // take key good(s) each
        for(int k=0; m[i]>0; k++) {
            int key = min(m[i], (int)(1<<k));
            m[i] -= key;
            for(int j=W; j>=key*w[i]; j--) {
                // do not take or take
                dp[j] = max(dp[j], dp[j-key*w[i]] + key*v[i]);
            }
        }
    }
    int ans = 0;
    repq(i,0,W) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
}

AOJ 1335: Equal Sum Sets

たとえ簡単な DP でも一発で通ると嬉しいよね。

問題概要

原文 → Equal Sum Sets | Aizu Online Judge

以下の相異なる自然数 個の合計が となる組み合わせの総数を求めよ。

• 
• 
• 

解説

以下の各数字 について、 を使うときと使わないときを考えてみます。

• を使うときは、合計が 増え、使う数字の数は 増える
• を使わないときは、合計は変わらず、使う数字の数も変わらない

これを用いて DP を書きます。計算量 です。

ソースコード

signed main() {
    int N, K, S;
    while(cin >> N >> K >> S, N || K || S) {
        // dp[i][j][k] := i 以下の数字を j 個使って k を作る組み合わせ
        int dp[25][25][255] = {};
        dp[0][0][0] = 1;
        repq(i,1,N) {
            repq(j,0,K) {
                repq(k,0,S) {
                    // i を使うと 合計は i 増える
                    if(k - i >= 0 && j != 0) dp[i][j][k] += dp[i-1][j-1][k-i];

                    // i を使わないと 合計は変わらない
                    dp[i][j][k] += dp[i-1][j][k];
                }
            }
        }
        cout << dp[N][K][S] << endl;
    }
    return 0;
}

にしてもAOJ-ICPCでこれ150点なのかー。・・・と思ってたけどよく考えたら が20までしかないからビットで全列挙できるか。

TopCoder SRM 705 Div2 Med (Div1 Easy): AlphabetOrder

(追記: Div1 Easy と Div2 Med が完全に同じ問題なのでタイトルを変更しました)

今回のSRMは大勝利したので嬉しい。Medが個人的に良問だと思ったので記事を書きます。

問題概要

原文 → TopCoder Statistics - Problem Statement

英小文字のみで構成された文字列がいくつか与えられる。各文字列について、先頭から順に見た時にアルファベットが昇順に並んでいるような文字列は「良い文字列」と呼ばれる。アルファベットの順番を適切に定義したとき、全ての文字列を「良い文字列」にできるならば Possible を、できないならば Impossible を出力せよ。

解説

愚直解法 (アルファベットの順番を全て試す) は、 通りもあるため当然試せません。

そこで、グラフに落として考えてみましょう。文字列の 文字目から 文字目 に向かって、有向辺を張ります。これを全ての の組み合わせについて行います。

例えば、文字列 abcd の場合は、以下のようになります。

常に左側のノードから右側のノードに向かって辺を張っているため、グラフが DAG になっていることがわかりますね。

さて、このグラフに意地悪をしてみましょう。文字列 ba を考えます。この文字列と abcd の1文字目・2文字目を考慮すると、明らかに全ての文字列を「良い文字列」にすることができませんね。実際に辺を張るとどうなるでしょうか？

このように、閉路ができてしまいます。閉路があるということは、アルファベットの順番を指し示していたはずの矢印がぐるぐる回っていることになりますので、Impossible であることと同義ですね。

以上より、この方針で解いていけばよいです。

• 各文字列に対して、 を満たす全ての の組み合わせを考え、( 文字目のアルファベット) ( 文字目のアルファベット) の方向に有向辺を張る
• できたグラフが DAG であれば Possible で、DAG でなければ Impossible

あとは DAG の判定をどうするかですが、これについては過去に @Darsein 先生から教えを受けていたのでした。

@_TTJR_ トポロジカルソートするだけ

— DはD論のD (@Darsein) 2016年12月27日

トポロジカルソートは入次数0のノードと、そのノードから出ている辺をどんどん消していくことで得られます。閉路があると入次数0 のノードがいずれ出来なくなるので、閉路判定は トポロジカルソートの結果のサイズがグラフの頂点数と等しいかどうか でできるというわけです。今回の問題の場合、連結でないグラフができる場合がありますが、閉路さえなければトポロジカルソートのサイズは頂点数と等しくなるので問題ないです。

ちなみに、ワーシャルフロイドでも閉路判定できるのですが、連結でないグラフの場合少し面倒なことに加え、頂点数が多くなると TLE するのでイマイチです。(この問題の場合は TLE しませんが)

ソースコード

トポロジカルソートのソースコードは省略します。

class AlphabetOrderDiv2 {
    public:
    string isOrdered(vector<string> words) {
        Graph(int) G(26);
        set<int> s;
        rep(i,0,words.size()) {
            rep(j,0,words[i].length()) {
                int d = words[i][j] - 'a';
                s.insert(d);
                rep(k,j+1,words[i].length()) {
                    int d2 = words[i][k] - 'a';
                    if(d != d2) {
                        G[d].pb(Edge<int>(d2, 1));
                    }
                }
            }
        }

        vector<int> v = tpsort_Kahn(G);
        if(v.size() != 26) return "Impossible";
        else return "Possible";
    }
};

次で青になれたらいいなあ・・・