titiaのノート: bit DP

ラベル bit DP の投稿を表示しています。すべての投稿を表示

2024年1月28日日曜日

AtCoder Beginner Contest 338

　Eまで五完。

コンテスト後のツイート

AtCoder Beginner Contest 338 Eまで。Fの解説見たら確かに、となった。
B Counter
C 料理Aを何個作れるか全探索。N<=10。
D 平面走査っぽくやると差分計算に持ち込める。難しい。
E 円形じゃない場合での、区間同士が重ならないか判定したら通った（未証明）。解説を開いたら証明略と書いてあった。
— titia (@titia_til) January 27, 2024

F - Negative Traveling Salesman

　解説AC。

　ワーシャルフロイド法により、二点間の最短距離を全て求めておく。その距離を使って、全点を巡る距離をbit DPで求めれば良い。

　x→zよりx→y→zが短いとき、前者で計算してしまうのが問題になる気がするが、結局後者でも計算することになり、通った集合が後者の方が優れているのでこれで答えが求まる。

G - evall

　解説放送を見てAC。

　解説放送を見たときは実装が大変に思えたが、そこまで大変な実装ではなかった。なお、再帰で書いたらPyPyではTLEになり、Pythonで提出したらACした。

2021年9月25日土曜日

yukicoder contest 315

　コンテスト中はCまでしか終わらず、コンテスト後に自力でEまで。　

　最初Bが分からなくなってぼーっとしてしまったせいなんだけど、CDEは典型なんだからそっちを見るべきだったよね。こういう感じでやる気をなくすのは良くない。

コンテストへのリンク

コンテスト後のツイート

No.1689 Set Cards

　bit DPが自然だと思う。

　ただ、想定解法は包除原理だった。

　以前も、bit DPで解ける問題の想定が包除原理だった問題を見たことがあったと思う。どちらも部分集合を扱うから当然といえば当然なのかもしれないけど、この二つが結構似ているというのは頭に入れておきたい。

2021年4月26日月曜日

AtCoder Beginner Contest 199（Sponsored by Panasonic）

　久々にRatedなABCで非常に緊張した。良い出来とは言えないけど、なんとか黄色に復帰出来てほっとした。

コンテストへのリンク

コンテスト後のツイート

D - RGB Coloring 2

　全部の色を試そうとすると$3^20$必要そうに見える。

　が、連結成分ごとに見て、隣が塗られているようなノードを試していけば、二個ずつしか試さなくていいため、全探索しても計算量が減る。

　……と、そこまではコンテスト中に気付いていたが、上手い実装が思いつかなかった。

　そもそも、全探索を再帰で行う方法がピンと来ていなかったと思う。今まで塗った色の集合を持って、次のノードで何を塗るかを決めれば良い。

　「どういう順番に塗るか」は、DFSの順番で良い。そうすれば、同じ連結成分内で二個目以降に見るノードでは、隣のどこかが既に塗られている。

E - Permutation

　三十分以上悩んだ上、bit DPを思いつかず、怪しい解法（結局、時間計算量的にはそんなに悪くなかったが、Hack caseはあった）を投げてしまった。

　コンテスト中考えたのは、

・何を使うか決めたら、N-1要素の場合に帰着できる

　ということ。

　N要素の場合に対応するM個の条件たちも、N-1要素の場合へ変わる。ので、条件たちを状態と見て、DP（実装はメモ化再帰）をした。

　計算量はよく分かっていなかったが、投げたら通った。

　が、ここで何をまとめているか、というと、たとえば、

・2→4→1と使った場合

・1→2→4と使った場合

　は同じ状態に遷移することが分かる。

　つまり、使う順番は関係なく、集合として同じ要素を消費した場合は同じ状態になる、ということ。

　これはbit DPですね。

　制約からもまずbit全探索やbit DPを疑うべきなのに気付かなかった（bit全探索は考えたけどbit DPは考えなかった）のはひどい。

　でも、After_contestで落ちたとはいえ、ACできて救われた。

F - Graph Smoothing

　これはすんなり解けた。

　「平均を取る」という操作を二回行って平均を取るのは、いかにも、「平均を取る」という操作の平均を取る、というのを二回繰り返したものと同じになりそう。

　それで良いと分かったら、「一回操作して平均を取る」というのは行列で表せるので、行列累乗すればOK。

2021年1月30日土曜日

C - Bowls and Dishes

　最初、この前のARCのBみたいにUnion-findを使う問題に見えた。

　が、ちょっと考えるとそれでは上手くいかず、Kの制約を見てbit DPに気付いた。

D - Staircase Sequences

　とりあえず立式！

　lからrまでの数の和の公式を使って立式すると、条件が分かる。

E - Magical Ornament

　Kの制約からbit DPっぽい……とは思ったけれど、最初それをどう使えば良いか分からなかった。

　$C_i$達同士の距離を求め、どう進むか順番（Kの順列）を決めたら答えは求まるけれど、それだとK!の計算量がかかってしまう。

　そうやってしばらく考えた後、この問題は巡回セールスマン問題に似ていると気付いた。それでもどう解くか分からなかったけれど、巡回セールスマン問題がbit DPで解けるということは聞いたことがあったので検索。このページを見て、なるほど、と思い実装した。

　最初気付かなかったのは仕方ないとしても、巡回セールスマン問題をbit DPで解く方法は頭に入れておかないと。

F - Shift and Inversions

　とりあえず転倒数は求められる。

　あとは、最初の数字を抜いたとき&それを最後に入れたときについて差分計算すれば良い。

2021年1月3日日曜日

AtCoder Beginner Contest 187

　年も変わったし、コンテストへの参加記録を書いていきます！

　……といっても、コンテスト後、既に一日経っている。いつまで続けられるんでしょうか。

コンテストへのリンク

コンテスト後のツイート

D - Choose Me

　何もしないと全員が青木氏に投票する。

　高橋氏が演説を行うと票がどれだけ動くか、と考えると、2*A+Bでソートすれば良いと分かる。

E - Through Path

　最初、全方位木DPが必要だと思い一旦飛ばした。

　Fを解いた後、やりたくないし書き終える自信がないけど、全方位木DPを書くかー、と書き始めたら、通常の木DPでいけることに気付いた。

　自然に書けば全方位木DP、「全体にxを足して、逆側からxずつ引く」ことを思いつけば普通の木DPでいける。

　とはいえ、全方位木DPでも書けるべき問題ですよね。

F - Close Group

　Nが小さいのでbit系を色々考えたが、しばらく思いつかず苦労した。

　「まず、完全グラフになっているものを列挙」を思いつけば、$4^N$のDPにはたどりつける。

　それが実は$3^N$になるというのは、この問題のsnukeさんの解説動画で覚えていた。難しい問題を解説ACしておいたのが役に立った！　と嬉しかったのですが、Educational DP Contestのこの問題もそうだったのですね。解いたはずなのに全く覚えていなかった……。

2020年5月28日木曜日

2020 Humbleool Cup Prelims

　オンサイトか何か（？）の予選で、Div.1、Div.2混合回。
　Div.2の難易度で、全完しないとまずいセットだったのに、Hardをミスして落とす。
　それでも、緑から青に戻ったけれど、これは出なくても良かったかなぁ、という気持ちになりました。

　なお、MedはPython最速だったらしく公式ページに自分の実装が載っています。

CardDrawPoints

　カードの枚数の制約が少ないことからも分かる通り、bit DPをする問題。

　どのカードを使った/使ってないか、の期待値をbit DPで計算すればOK。

　floatで割り算して誤差が大丈夫か不安だったけれど、それも問題なかった。

　コンテスト中は、残り枚数が0枚のときに、0除算して落としてしまった。ちゃんと気を付けないと！

　一応、システムテストを通ったコードを載せておきます。

class CardDrawPoints():
    def expectedScore(self, count):
        LEN=len(count)
        if max(count)==0 or len(count)==1:
            return 0

        LIST=[-1]*(1<<LEN)
        def calc(A):
            if LIST[A]!=-1:
                return LIST[A]
            
            rest=[0]*LEN
            NOW=0

            for i in range(LEN):
                rest[i]=count[i]
                if A & (1<<i)!=0 and count[i]>0:
                    NOW+=i
                    rest[i]-=1

            SUM=sum(rest)

            if SUM==0:
                return NOW

            ANS=float(0)

            for i in range(LEN):
                if A & (1<<i)!=0:
                    continue
                else:
                    ANS+=float(calc(A|(1<<i)))*rest[i]/SUM

            if NOW>ANS:
                LIST[A]=NOW
                return NOW
            else:
                LIST[A]=ANS
                return ANS

        for i in range((1<<LEN)-1,-1,-1):
            calc(i)

        return LIST[0]

2020年5月23日土曜日

CodeCraft-20 (Div. 2)

　Dまで四完でした。Bで手間取ったため順位はイマイチ。
　日本語の解説記事があったので、復習のときはEやFもACしよう、と思ったらかなり時間がかかってしまった……。

コンテストへのリンク

B. String Modification

　実験してみれば、操作後のSがどうなるか分かるので、それらの最小値を見れば良い。

　ただ、PyPyだと、それらをソートするとTLEになると思う。普通に、一回一回最小値を取っていけばOK。

　自分は、コンテスト中これが思いつかず、一文字目で枝狩りをしてソートしたらACした。

　なんか、最小値だけ求めれば良いところでList→ソートを使ってしまったり、上限の値が小さい正整数の、重複しない要素の個数を求めたいときにsetを使ってしまったり（上限の値までのListでOK）、本質的ではないところで遅い実装に走ってしまう癖がある気がする。気を付けたい。

C. Primitive Primes

　一見難しいけど、実は簡単。Codeforcesでレートを上げたいならこういう問題を落とさないのが結構重要。

　A, Bの係数のgcdが1でないので、素数pで割り切れない係数がA, Bのどちらにも必ず存在する。

　それらの最小のものを足せばOK。

D. Nash Matrix

　まず、動かない点を処理。

　次に、その点がゴールになっている点をゴールからのDFSで処理。

　その後、無限ループする点が、別の無限ループする点と接していればそちらへ向かわせる。

　これらの処理をして、ちゃんと全ての点が埋まればVALID、ダメならINVALID、とする。

　面倒だけど、やること自体は分かりやすい。

E. Team Building

　けんちょんさんの解説記事、akiradeveloperさんの解説記事を読んで解説AC。

　制約からbit DP（かbit全探索）だろうな、と予想できる。

　問題は、どうやってその枠組みへ落とし込むかだけど、応援力（Aで与えられるもの)をソートしてやると、i人目まで決め、その選手をどのポジションにも選ばないと決めたとき、応援にまわすか/まわさないか、が決まるのでbit DPできる。

　結構自然な解法なんだけど、なぜか正当性が分からなくなって悩んでしまった。この問題の正当性というよりは、bit DP自体の正当性について悩んだ。部分集合で最善？　それを二つに分けたとき、両方最善な必要がある？　とかって。

　そういうことを考える必要はなくて、bit DPの正当性は、「最後にxを選んだとき」を考えて帰納法を回していく感じで言えますね。

　なお、この問題はPython/PyPyでは通せずKotlinでACしました。Kotlin Heroesが近付いているので、久々にKotlinを使ったけど、結構書きやすい！

F. Battalion Strength

　けんちょんさんの解説記事、idsigmaさんの解説記事を読んで解説AC。

　ゆるふわ競プロオンサイト #3のSweets Distribution(Hard)もそうですが、

・値変更などのクエリ→セグメント木

　は定番なんですね。

　ただ、どうやってセグメント木で処理するか、何をセグメント木に乗せればいいかも難しい。idsigmaさんの解説記事にはその辺りも全部書いてあるのですが、それでも理解するのに苦労しました。

　「求めたい値を、セグメント木で自分の下に位置する二つのノードから求めるためには何が必要か？」とちゃんと式を書いて考えれば分かると思います。

　さて。

　解法は理解できたのですが、TLEやMLEのためPyPyでACすることはできず、結局C++でACしました。（AtCoderのコードテストだとランダムケースで三秒ほどの実行時間なので間に合いそうなのですが、Codeforcesだと15秒くらいかかってしまう）

　ただ、pajenegodさんはPyPy2で通しているんですよね。他の人がPyPyで通している問題で、PyPyでのACを断念するというのは悔しいのですが……。仕方ない。

2020年2月14日金曜日

AtCoder Beginner Contest 152

　Fが解けずの五完でしたが、後で見直したらFは難しくなかった。直後にCodeforcesがあったので疲れないようにやろう、とは思っていたけど、実装が大変な問題でもなかったし……。

コンテストへのリンク

A - AC or WA

　N=Mか調べる。

B - Comparing Strings

　小さい数字を繰り返した方がお得。

C - Low Elements

　今までで一番小さい数字を管理

D - Handstand 2

　最初、桁DPのようなことをしなくちゃいけないのか、と思って飛ばした。

　冷静になると、1以上N以下の「最初の数字がiで最後の数字がjとなるような数字の個数」が全探索できるので、それを使って計算できる。

E - Flatten

　Aの最小公倍数を$A_i*B_i$とすれば良い。

　Pythonなら直接最小公倍数を求めて解くことも可能だったらしいけど、私は各素因数を何回使うかを調べて、modを取りながら最小公倍数を求めました。

F - Tree and Constraints

　コンテスト時の書き換えのファイルを見たら、

DP=[0]*(1<<M)

　とか書いて止まってたのですが、ここで止まるのはおかしい。この方針（bit DP）で解けます。

　各制約が満たされているかどうかを状態を持つDPをします。

　各制約のpathに含まれる頂点が何かを前計算しておいて、各辺を白く塗るか/黒く塗るかでDPを更新。

　初期値はDP[0]=1

　辺を見る順番もどうでも良いので（なので、本質的に木であることを使ってない。直線と解き方同じ）、1から順番に見ていくとすると、k番目の更新は、path中にkを含むものの和集合をBとして、各i(0<=i<2^M)について、

DP[i|B]+=DP[i]

　とすればOK。
　1<<Mから0へ、大きい順に見ていけば、DPテーブルを使い回すこともできる。

　これで、（前計算を除いて）計算量は$2^M*M$となるので解けます。（前計算はM回DFSしてO(N*M)でしましたが、もっと速くなるはず）

　今、公式解説を見たら包除原理って書いてあって驚いた（他の解説ブログ等も見たけど、大体包除原理を使ってそう？）のだけど、この方針の方が自然では？

　この後、解説放送を見たりして包除原理の解法を理解しました。いや、でもやっぱりこの解法の方が簡単では？
（youtubeのコメントでこの解法に言及されている方がいました。コメント内では、本質的には包除原理と同じ解法という話になっていたみたいです。うーん、私には違う解法に見えるんですが……。）

登録: 投稿 (Atom)