SRM671 Div2(Easy,Med)
いったいいつぶりの投稿だろうか..
Medで少し学ぶことがあったのでいい機会だと思って復活しました。hard時間内で解こうと意気込んでたら全然出来んかった..クマさんにいじめられる回です。
Easy (250) : BearPaints
問題文の要約
幅マス, 高さマスの直方体のマス目が与えられる。直方体を成すようにマスをぬるとき、マス分のインクで最大何マスをぬることができるか?
制限
時間 : 2秒, メモリ : 256MB
制約
解法
全探索をしてしまうと最悪計算量がかかってしまうので幅の方だけ探索を行います。塗る直方体の片方の辺の長さをに固定すると、ぬることができる直方体のマス目は
- のとき
- そうでないとき (""は小数を切り捨てる除算)
となるので、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の自然数列 が与えられる。なるの取り方は何通りあるか?
制限
時間 : 1秒, メモリ : 256MB
制約
解法
もちろん、全組み合わせを確かめようとすると通り、最悪で通りあるので1秒では全探索はキツそう。ってわけでDPを使うことにしました。
DPのためのmapとしてdp1, dp2,dp3の三つを用意し、を左から順にチェックして更新します。をチェックする際に三つのマップは
という状態になっており、dp3[ ]の値を答えに加えたあと、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)
さきほどの解法では, について、先にの組み合わせを作っておき、それとが一致するかどうか確かめていく方法でした。しかしこの方法では掛け算の組み合わせが爆発するらしい..
そこで少し考え方を変えてみます。というのは即ち、
と言い換えることが出来ます。この考え方で、を先に作っておき、と一致するか確かめるよう dp1,dp2,dp3を変更し、を右からチェックしていきます。をチェックするときの各mapの状態は、
- dp1 : のとる値(key)の組み合わせ数(value) ()
- dp2 : のとる値(key)の組み合わせ数(value)()。ただし、
- dp3 : のとる値(key)の組み合わせ数(value)()。ただし、 かつ
となっており、dp3[ ]の値を答えに加えたあと、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しちゃいましたが、掛け算の取りうる値の通り数をチェックするときに割り算で攻めるのはとてもいい知見だと思いました。何らかの機会に生かしたい。 あと、左から、右からの値を作っておいて..といった手法も出来そうな気がしますが、mapが個必要になるので、今回の手法の方が好きかな。 hardについては..そのうち..多分..