/ 最近 .rdf 追記 編集 設定 本棚

脳log[20230303]



2023年03月03日 (金) [AtCoder] 精進。ふか杯 5th Contest-D「Bintree」。制限時間が5秒だけど、ちょっと油断していたよね。■最初の提出 #39379910 (TLE×4)。ビット列で集合を管理する。重さもビット列ごとにメモしておく。ビット集合から根にする1ビットを選ぶのは BIT を参考に i&-i で。部分集合の列挙は b = bits と初期化してから b = bits&b-1 で。メインはメモ化再帰。やりやすいからこういう方法でやったけど、必要以上にテクニカルなことをしているつもりだった。しかし TLE。■2番目の提出 #39380194 (TLE×1)。これのアイディアは1つで、左の子集合(L)と右の子集合(R)に L<R という大小関係を仮定して L>R の場合の再帰呼び出しを省いた。省いた分は ×2 で辻褄が合う。■提出 #39381113 (AC / 4266 ms)。これのアイディアは2つ。1つ目は前の提出のアイディアの改善。L<R を仮定しているのだから最初から列挙回数を半分にすればいい。2つ目はコードテストで数百 ms の効果があった(けれど単体では TLE 解消に少し足りなかった)チューニング。ビット列に対応した重さを予めメモする部分のコードで、いちいち各ビットが立っているかどうか調べるのをやめた。■(オーバーヘッドが大きい) Hash を使うメモ化再帰をやめて Array を使うボトムアップの DP に書き換えるとさらに改善するだろうけど、それは遷移がわからなくて書けない。