naoya_t@hatenablog

いわゆるチラシノウラであります

〈説明用メモ〉O(3^N)について本気出して考えてみた

n個ある何かの0個以上から成る集合Snビットの整数で表すことにする。
このとき、集合に含まれる要素がk個なら全部でkビット立っている 。
__builtin_popcount(S) == k

この集合Sの部分集合Tをすべて列挙しようとすると、空集合も含め2^k通りある。
集合Sとしてありうる全てのパターンについてこれを列挙することを考えると、
n個からk個選ぶ組み合わせが_nC_k通りで、そのそれぞれについて2^k通りの部分集合があるので全部で \displaystyle\sum_{k=0}^{n}{_nC_k\cdot2^k} 通りについて考えることになる。

ここで驚くべきことは、任意の非負整数nについて
$$ \sum_{k=0}^{n}{_nC_k\cdot2^k}=3^n $$
が成り立つということである。

各ビットについて

  • SでもTでも立っている
  • Sでのみ立っている
  • SでもTでも立っていない

の3通りの状態がありうるのだから自明ではある。
bitDP回りでよくO(3^N)という数が出てくるのはそのためである。

実際の回し方については
ビットによる部分集合の列挙 - SRM diary(Sigmar) - TopCoder部
の解説がわかりやすい。

意地悪な制約の問題では計算量 O(3^N) では間に合わず、O(N2^N) に下げる工夫が求められたりする。
高速ゼータ変換/高速メビウス変換 - naoya_t@hatenablog
の出番である。

LeetCode Weekly Contest 119

1/13(日) 11:30-13:00
4完140/3334位

開始時にロードが酷く重いので開いた順に解いていく奴
C:累積和modで取って同じ値の箇所の個数のnC2の和
A:並べ替え二乗のままで大丈夫
B:ソートして大きいのから3つ取り、駄目なら順に大きい3つ
D:提出後初めて気づく読み違え。5分とはいえペナルティ痛し

575(77)に揃えてみた
だがしかしDは答えになってないw

レーティングは微増(2271→2279)
f:id:n4_t:20190115143430p:plain:w450

続きを読む

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

1/12(土) 21:00-23:00
3完357位…Cで適当に投げて2ペナ食らったのが痛い
パフォ1777でレート微増(1702→1710)

続きを読む

Educational DP Contest / DP まとめコンテスト

1/6(日)20:00-25:00

始まった時点で家に帰る途中で20:14に参戦。
途中30分弱離席したけれど結局最後までやってて全26問中16完で172位
フル参加できてたら+1〜2問ってところか。

終わってから残りの問題にもひと通り目を通したけれどまだ習ってないテクが必要な問題がある。ぜひ今回持って帰りたい。

続きを読む

〈旧ABC埋め〉旧配点時代のABCで面白かった/手こずった問題メモ

旧配点時代のABCをぷちぷち埋める
(面白かった or 手こずった問題をメモ)

旧配点なのですべて100点*1

*1:時々101点とかあるけど

続きを読む