SRM 671 Div2 （練習） - tshitaの備忘録Ⅱ

[結果]

SRM 671 Div2: xo-
練習で解きました．easyが落ちて笑えない．

[Easy 250: BearPaints ]

問題

H行W列の格子上で面積がM以下で最大の矩形の面積を求めよ．

$1 \le W, H \le 10^6$
$1 \le M \le 10^{12}$

方針

矩形の縦または横の長さを固定すると，面積を最大にする片方の長さは簡単に求まります．例えば縦をhで固定した場合の横wは min(M/h, W) となります．
縦と横は最大で $10^6$ 以下なので，各々すべての長さの場合を計算して最大の面積を求めればよいです．

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class BearPaints {
public:
	long long maxArea(int W, int H, long long M) {
        ll res = 0;

        for (int w = 1; w <= W; ++w) {
            ll h = min((ll)M / w, (ll)H);
            res = max(res, w * h);
        }
        for (int h = 1; h <= H; ++h) {
            ll w = min((ll)M / h, (ll)W);
            res = max(res, w * h);
        }

        return res;
	}
};

[Med 500: BearDartsDiv2 ]

問題

N個の要素からなるwが与えられる．
a < b < c < d で w[a] * w[b] * w[c] = w[d] となる組合せ数を求めよ．

$4 \le w.size() \le 500$
$1 \le w_i \le 10^6$

方針

SRM671 Div1のMedと同様の方法で解きます．
式変形をして，
$w_a \times w_b = \frac{w_d}{w_c}$
としたときにcを基準に全探索します．
a < b < c を満たすすべてのaとbに対して，a * bの値の出現回数をmapで管理して，c < d を満たすすべてのdに対して w[d]/w[c] となる値の出現回数を求める答えに足していきます．

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

class BearDartsDiv2 {
public:
	long long count(vector <int> w) {
        const int n = w.size();
		map<ll, ll> cnt;

        ll ans = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j)
                ++cnt[w[j] * w[i]];
            for (int j = i + 2; j < n; ++j)
                if (w[j] % w[i + 1] == 0)
                    ans += cnt[w[j] / w[i + 1]];
        }

        return ans;
	}
};

[Hard 1000: BearDestroysDiv2 ]

問題

H行W列の格子状の森を考える．始めそれぞれのセルには1本の木がある．
次に，それぞれのセルを右（East）に倒すか下（South）に倒すかの情報が与えられたとする．左上のセルから右に向かってセル内の木を倒すかどうかの操作をしていく．一番右のセルが終了したら次の行の左から同じ操作を続ける．すべてのセルの操作を終えたら終了．
- 木が倒されていたら次のセルへ．
- 情報通りに倒せるなら倒す．倒せないなら逆の操作で倒せれるなら倒す．どっちでも倒せないなら何もしない．終わったら次のセルへ．

情報通りに倒すとは，情報がEastなら現在のセルが右端でなく，右のセル内の木が倒されていない時に，現在のセルと右のセル内の木を倒す．
情報がSouthなら現在のセルが下端でなく，下のセル内の木が倒されていない時に，現在のセルと下のセル内の木を倒す．

すべての操作を終えた時に倒された木の総数 / 2を倒した木の数とする．
すべてのどの方向に倒すかの情報（2^(H*W)）の場合の倒した木の総数を求めよ．

$1 \le W \le 7$
$1 \le H \le 40$

方針

分からなかったのでkmjpさんの解法を見て解きました．
TopCoder SRM 671 Div2 Hard BearDestroysDiv2 - kmjp's blog

kmjpさんの解法を見ての反省点を書きます．
全列挙をすると O(2^(H*W)*H*W) となり間に合いません．ここで，シュミレーション内で重複してカウントしている部分を考えます（dpで解けないか）．

ある行に着目します．どの方向に切るのかの情報が与えられたときに，どの部分がこの行を切るシミュレーション結果に影響を与えるのかを考えます．
ある列の木を倒すことを考えると，その前の行の同じ列の結果によって倒し方が変わることに気付きます．すなわち，前の行の同じ列がSouthに倒した（現在着目している木が倒された）かによって変わります．
したがって，現在の行のすでに倒されている木の情報とどの方向に倒すのかの情報が同じならばシミュレーション結果は同じです（2つ前の行以前の倒され方やどの方向に倒すかの情報は必要ない）．
今回は倒されたか倒されていないかの結果の場合の数ではなく倒された木の数が必要なので，現在まででいくつの木を倒したのかの状態も必要となります．

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;
class BearDestroysDiv2 {

public:
	int sumUp(int W, int H, int mod) {
        const ll MOD = mod;
        const int MAX_NUM = H * W / 2 + 2;
        // dp[処理した行番号][倒れた木の総数][次の行に向けて倒れたbitmask]
        //  := その状態になる組合せ数
        vector<vector<vector<ll>>> dp(H + 1,
                                      vector<vector<ll>>(MAX_NUM + W / 2 + 2,
                                                         vector<ll>(1 << (W + 1), 0)));

        dp[0][0][0] = 1;
        for (int h = 0; h < H; ++h) {
            for (int num = 0; num < MAX_NUM; ++num) {
                for (int s = 0; s < 1 << W; ++s) {
                    if (dp[h][num][s] == 0)
                        continue;
                    for (int sw = 0; sw < 1 << W; ++sw) {
                        // swのiビット目が0 := South
                        // swのiビット目が1 := East
                        int nxt_num = num; // この行までで倒された木の総数
                        int nxt_s = 0; // 次の行に向けて倒された木のbitmask
                        int now = 0; // この行で倒された木のbitmask

                        for (int w = 0; w < W; ++w) {
                            if (s >> w & 1 || now >> w & 1) // すでに倒されている
                                continue;

                            if (sw >> w & 1) { // East
                                if (w < W - 1 && !(s >> (w + 1) & 1)) { // Right
                                    ++nxt_num;
                                    now |= (1 << w) | (1 << (w + 1));
                                }
                                else if (h < H - 1) { // Down
                                    ++nxt_num;
                                    now |= (1 << w);
                                    nxt_s |= (1 << w);
                                }
                            }
                            else { // South
                                if (h < H - 1) { // Down
                                    ++nxt_num;
                                    now |= (1 << w);
                                    nxt_s |= (1 << w);
                                }
                                else if (w < W - 1 && !(s >> (w + 1) & 1)) { // Right
                                    ++nxt_num;
                                    now |= (1 << w) | (1 << (w + 1));
                                }
                            }
                        }

                        dp[h + 1][nxt_num][nxt_s] = (dp[h + 1][nxt_num][nxt_s]
                                                     + dp[h][num][s]) % MOD;
                    }
                }
            }
        }

        ll ans = 0;
        for (int num = 0; num < MAX_NUM; ++num)
            ans = (ans + (num * dp[H][num][0]) % MOD) % MOD;

        return (int)ans;
	}
};

まとめ

Easyをアドホックに解いて間違った．計算機をもっと信用しようという気持ちになった．
Hardは蟻本に乗っているFliptileのdp風でいけるかな思ったけど上手くいかず．