SRM671 Div2(Easy,Med)

いったいいつぶりの投稿だろうか..

Medで少し学ぶことがあったのでいい機会だと思って復活しました。hard時間内で解こうと意気込んでたら全然出来んかった..クマさんにいじめられる回です。

Easy (250) : BearPaints

問題文の要約

幅 $W$ マス, 高さ $H$ マスの直方体のマス目が与えられる。直方体を成すようにマスをぬるとき、 $M$ マス分のインクで最大何マスをぬることができるか？

制限

時間 : 2秒, メモリ : 256MB

制約

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

解法

全探索をしてしまうと最悪計算量が $10^6 * 10 ^6 = 10^{12}$ かかってしまうので幅の方だけ探索を行います。塗る直方体の片方の辺の長さを $i (1 \leq i \leq W)$ に固定すると、ぬることができる直方体のマス目は

$i * H \leq M$ のとき　 $i*H$
そうでないとき　 $i*(M / i)$ (" $/$ "は小数を切り捨てる除算)

となるので、iを動かしていけば最大値が見つかります。

実装

実際の実装では幅と高さのうち小さい方を動かすようにしてます。

class BearPaints:
    def maxArea(self, W, H, M):
        l = min(W,H)
        h = max(W,H)
        return max([i*h if i*h <= M else i*(M/i) for i in xrange(1,l+1)])

Med (500) : BearDartsDiv2

問題文の超要約

長さNの自然数列 $w$ が与えられる。 $w_i * w_j * w_k = w_l (0 \leq i \lt j \lt k \lt l \lt N)$ なる $(i,j,k,l)$ の取り方は何通りあるか？

制限

時間 : 1秒, メモリ : 256MB

制約

$4 \leq N \leq 500, 1 \leq w_i \leq 10^6$

解法

もちろん、全組み合わせを確かめようとすると $_NC_4$ 通り、最悪で $_{500}C_4 = 2573031125 \fallingdotseq 2.6*10^9$ 通りあるので1秒では全探索はキツそう。ってわけでDPを使うことにしました。

DPのためのmapとしてdp1, dp2,dp3の三つを用意し、 $w$ を左から順にチェックして更新します。 $w_l (0 \leq l \lt N)$ をチェックする際に三つのマップは

dp1 : $w_i$ のとる値(key)の組み合わせ数(value) ( $0 \leq i \lt l$ )
dp2 : $w_i * w_j$ のとる値(key)の組み合わせ数(value)( $0 \leq i \lt j \lt l$ )
dp3 : $w_i * w_j * w_k$ のとる値(key)の組み合わせ数(value)( $0 \leq i \lt j \lt k \lt l$ )

という状態になっており、dp3[ $w_l$ ]の値を答えに加えたあと、dp3, dp2, dp1の順番で更新します。これなら掛け算の組み合わせがまとまるので多分行けるはず。

実装

今回は制約が厳しそうだったのでC++で実装することにしました。超シンプルに書けたので満足。

class BearDartsDiv2 {
    public:
    LL count(vector<int> w) {
        LL ans = 0, N = w.size(), wi = 0;
        map <LL, LL> dp1, dp2, dp3;
        map <LL, LL> :: iterator it;
        for(int i = 0; i < N; i++){
            wi = (LL) w[i];
            ans += dp3[wi];
            for(it = dp2.begin(); it != dp2.end(); it++) dp3[(it->first)*wi] += it->second;
            for(it = dp1.begin(); it != dp1.end(); it++) dp2[(it->first)*wi] += it->second;
            dp1[wi] += 1;
        } 
        return ans;
    }
};

だがしかし..

「hardは解けなかったけど、med綺麗に解けたから満足！」っとか言ってたら、落ちましたorz。TLEでした。行けると思ってたんですがどうやら1秒は思ったより厳しかったらしい.. しかしこの方針自体は気に入ってるのでどうにか通したい..

解法(その2)

さきほどの解法では, $w_i * w_j * w_k = w_l (0 \leq i \lt j \lt k \lt l \lt N)$ について、先に $w_i * w_j * w_k$ の組み合わせを作っておき、それと $w_l$ が一致するかどうか確かめていく方法でした。しかしこの方法では掛け算の組み合わせが爆発するらしい..

そこで少し考え方を変えてみます。 $w_i * w_j * w_k = w_l (0 \leq i \lt j \lt k \lt l \lt N)$ というのは即ち、

$w_i = w_l \div w_k \div w_j (0 \leq i \lt j \lt k \lt l \lt N , w_l \% w_k = 0, (w_l \div w_k) \% w_l = 0)$

と言い換えることが出来ます。この考え方で、 $w_l \div w_k \div w_j$ を先に作っておき、 $w_i$ と一致するか確かめるよう dp1,dp2,dp3を変更し、 $w$ を右からチェックしていきます。 $w_i (0 \leq i \lt N)$ をチェックするときの各mapの状態は、

dp1 : $w_l$ のとる値(key)の組み合わせ数(value) ( $i \lt l \lt N$ )
dp2 : $w_l \div w_k$ のとる値(key)の組み合わせ数(value)( $i \lt k \lt l \lt N$ )。ただし、 $w_l \% w_k = 0$
dp3 : $w_l \div w_k \div w_j$ のとる値(key)の組み合わせ数(value)( $i \lt j \lt k \lt l \lt N$ )。ただし、 $w_l \% w_k = 0$ かつ $(w_l \div w_k) \% w_j = 0$

となっており、dp3[ $w_i$ ]の値を答えに加えたあと、dp3, dp2, dp1の順番で更新します。最初の解法だと掛け算の取りうる値は全てmapに記録されましたが、この解法だと割り切れないものは弾かれるので計算量が大幅に減少します。

実装

実装自体はほとんど一緒です。右からチェックするのと、割り切れるかのチェックが加わっているだけなので。

class BearDartsDiv2 {
    public:
    LL count(vector<int> w) {
        LL ans = 0, N = w.size(), wi = 0;
        map <LL, LL> dp1, dp2, dp3;
        map <LL, LL> :: iterator it;
        for(int i = N-1; i >= 0; i--){
            wi = (LL) w[i];
            ans += dp3[wi];
            for(it = dp2.begin(); it != dp2.end(); it++) if ((it->first) % wi == 0) dp3[(it->first)/wi] += it->second;
            for(it = dp1.begin(); it != dp1.end(); it++) if ((it->first) % wi == 0) dp2[(it->first)/wi] += it->second;
            dp1[wi] += 1;
        } 
        return ans;
    }
};

結果

ちゃんと通りました！やったね！最初の解法だとTLEだったcaseもこの解法なら数十msぐらいで行けるという。割り算って偉大だ。

ちなみに、もしかしたらこの方針ならpythonでも行けるかも？と思ってやってみると..

class BearDartsDiv2:
    def count(self, w):
        ans = 0
        dp1 = collections.defaultdict(int)
        dp2 = collections.defaultdict(int)
        dp3 = collections.defaultdict(int)
        for wi in reversed(w):
            ans += dp3[wi]
            for k,v in dp2.iteritems():
                if k % wi == 0:
                    dp3[k/wi] += v
            for k,v in dp1.iteritems():
                if k % wi == 0:
                    dp2[k/wi] += v
            dp1[wi] += 1
        return ans

通りました！こちらも最悪ケースが数十msぐらい。割り算すげえ..

まとめ

本番ではTLEしちゃいましたが、掛け算の取りうる値の通り数をチェックするときに割り算で攻めるのはとてもいい知見だと思いました。何らかの機会に生かしたい。あと、左から $w_i*w_j$ 、右から $w_l \div w_k (w_l \% w_k = 0)$ の値を作っておいて..といった手法も出来そうな気がしますが、mapが $2N$ 個必要になるので、今回の手法の方が好きかな。 hardについては..そのうち..多分..