algoNote

プログラミング関連

みんなのプロコン 2018 C - 駆引取引

コンテスト終了間際にACする解法が思いついたのですが、コンテスト中に通すことが出来ませんでした。 無駄の多い解法(考察)ですが、考えたことを順に書いてみようと思います。

問題

C - 駆引取引

考えたこと

Nが18以下と小さいので商品の集合をビットで管理出来そうです。

まず答えを求めるために必要そうな情報を考えました。

  • 高橋君の所持金
  • 高橋君が持っている商品の一覧
  • 青木君が持っている商品の一覧

これくらいの情報があれば充分そうです。

高橋君が購入する操作を行なうとき、 「高橋君はK円持っている。青木君が持っている商品の集合をSとするとき、最大で得ることの出来る得点はいくらか。」 という問題を解ければよさそうです。

少し考えると、

  • 高橋君は商品を前から順に売っていくので、所持金は高々N通りしかない
  • これは累積和で前計算出来る
  • 高橋君が持っている商品の一覧は重要ではない

ということが分かります。よって、

  • 高橋君の所持金
  • 高橋君が持っている商品の一覧
  • 高橋君が何個の商品を売ったか
  • 青木君が持っている商品の一覧

が分かれば良さそうです。

また、高橋君の行える行動は「いくつの商品を売るか」を決めることで、 青木君の行動の自由は「各ターンどの商品を捨てるか」を決めることです。

さらに言うと高橋君の行える行動は「毎ターン(次の商品を売るか、青木君から商品を購入して取引を終了するか)」を決めること、なのですが僕はここまで詰められずに嘘解法に行ってしまいました...

ここで、嘘解法を書き始めます。

sum[i] := x[0]からx[i]までの和
ans = 0
S = (全ての商品)  // 青木君が持っている商品 

// 高橋君がi個売る場合 (所持金はsum[i]円)
repeat(i | 0 to N-1) {
    tmp = (無限大)  // 得点

    // 青木君が商品jを捨てる場合
    repeat(j | 0 to N-1) {
        if (Sにjが残っている場合) {
            (Sから商品jを捨てたと仮定)

            // 高橋君がsum[i]円持っていて残っている商品がSのときに得られる得点の最大値を求める

            tmp2 = 0  // 得点
            foreach(k | Sの部分集合) {
                // 高橋君がkに属する商品をすべて購入する場合
                yen = 0  // kに属する商品全ての値段の合計
                val = 0  // kに属する商品全ての価値の合計
                repeat(l | 0 to N-1) {
                    if (l番目がkに含まれる場合) {
                        yen += y[l]
                        val += v[l]
                    }
                }
                if (y <= sum[i]) {
                    tmp2 = max(tmp2, val)  // 高橋君は得点が最大になるように購入する
                }
            }
            tmp = min(tmp, tmp2)

            (Sに商品jを戻す)
        }
    }

    (tmpが最小値をとる商品をSから捨てる)
    ans = max(ans, tmp)
}

ansを出力

まず、計算量が{O(N^3 \cdot 2^N)}なのでTLEしますね。(僕はこの嘘解法を高速化した時点でコンテストが終了してしまいました。) この嘘解法はサンプルの1から3までは通りますが、サンプル4で落ちます。 これは、「高橋君は得点を最大化するように動き、青木君は得点を最小化するように動く」に反しているためです。 青木君の動きに着目すると、次のターンで終了する場合しか考えられていません。

高速化について書きます。 高橋君がsum[i]円持っていて残っている商品がSのときに得られる得点の最大値を求めるの部分を前計算しておければよさそうです。

  • 高橋君の所持金(N通り)
  • 青木君が残している商品(2^N通り)

なので、状態数は{O(N \cdot 2^N)}個です。

dp[i][S]:=高橋君の所持金がsum[i]円で青木君が残している商品がSのときの得点の最大値

というDPを考えます。Sはビットで管理します。このDPがスムーズに書けなくて悩みましたが、最終的に次のようにDPしました。

//////////////// これらを適当に前計算 O(N*2^N) ////////////////
yen[S] := Sに含まれる商品を全て購入するときに必要な金額
value[S] := S含まれる商品を全て購入するときに得られる価値(得点)
dp[i][j] := 0  // すべて0で初期化
////////////////////////////////////////////////////////////////

repeat (s | 0 to (2^N)-1) {
    repeat (i | 0 to N-1) {
        if (sum[i] >= yen[s]) {
            // 商品集合sを全て購入したときの得点
            dp[i][s] = max(dp[j][s], value[s])
        }
    }
}

// ビットDPの要領で、dp[i][s]の状態からsに含まれていない商品を追加した状態へ遷移する
// (これから追加する商品を買わなければよいので、少くともdp[i][s]得られる。)
repeat (s | 0 to (2^N)-1) {
    repeat (i | 0 to N-1) {
        if (sにiが含まれていないとき) {
            repeat(j | 0 to N-1) {
                dp[j][s|(1<<i)] = max(dp[j][s|(1<<i)], dp[j][s]) // 少くともdp[j][s]得られる
            }
        }
    }
}

これで高橋君がsum[i]円持っていて残っている商品がSのときに得られる得点の最大値の部分を求めることが出来ました。

あとは「高橋君は得点を最大化するように動き、青木君は得点を最小化するように動く」の部分を修正すればOKです。 これはゲームの問題でよくあるDPを行うことで解決できます。といっても愚直に実装してメモ化するだけです。

// 高橋君が既にi個売った、p(0:青木君,1:高橋君)が操作を行なう、青木君が残している商品はS、の状態の得点(の最大)
int rec(int i, int p, int S) {
    if (i >= N) return 0;
    if (p == 1) {
        // 高橋君の操作
        int ret = 0;
        ret = max(ret, rec(i+1, p^1, S));  // 売却する
        ret = max(ret, dp[i][S]);  // 購入して終了
    } else {
        // 青木君の操作
        int ret = 無限大
        repeat (j | 0 to N-1) {
            if (Sのjビット目が1) {
                ret = min(ret, rec(i, p^1, S^(1<<j)));  // 商品jを捨てる
            }
        }
        return ret;
    }
}

これをメモ化すれば終了です。

配列に余裕をもたせていたらMLEしてしまいましたが、少し削ったらACしました。

コード

https://beta.atcoder.jp/contests/yahoo-procon2018-qual/submissions/2083300

2017年の振り返り

もうすぐ2017年が終わりますね。今年もあっという間でした。

ということで、2017年のことを振り返ってブログに書いておこうと思います。

続きを読む

Codeforces Round #448 (Div. 2) C - Square Subsets

コンテスト中にAC出来ませんでしたが、解けたので好きな問題です(オイ)

問題

codeforces.com

N 個の要素から成る数列 {a_i} が与えられます。
要素の積が k^{2} の形で表せるような部分集合の取り出し方は何通り存在しますか。109 + 7で割った余りを求めてください。

制約

  • {1 \leq N \leq 10^{5}}
  • {1 \leq a_i \leq 70}
続きを読む

Codeforces Round #433 Div.2D / Div.1B . Jury Meeting

問題文

codeforces.com

続きを読む

セグメントツリーを勉強した

セグメントツリーを勉強したのでメモとしてコードを載せておきます。

続きを読む