今日解いた競プロの問題。
競プロ典型90問
080 Let’s Share Bit: 「すべてについて次の条件を満たす～」という問題文と、N≦20というbit全探索が行けそうな制約から包除の匂いを感じた。まずこのままだと問題が考えづらいのでもうちょいましに戦える感じにできないか考えてみる。
「a AND bが0でない」ということは、「aで1となっているビットの内どれかしらのビットがbで1である」ということである。これはちょっと考察しづらい。しかし補集合「a AND bが0である」を考えてみると、「aで1となっているビットの全てがbで0である」になる。これならば考えやすい。「a1 AND b、a2 AND b、… an AND bのすべてが0である」についても、「a1 OR a2 OR … anで1となっているビットの全てがbで0である」になることが分かる。
また、「すべてについて～である」ということの補集合をとると「どれかについて～でない」になる。
これを踏まえると
「すべての$A_i$について$A_i AND x\neq 0$」⇔￢「いずれかの$A_i$について$A_i AND x = 0$」
である。この形式ならば包除原理でさばくことができる。
$A_1 AND x = 0$ かつ $A_2 AND x = 0$ かつ…という条件を満たす数の数え方は先の考察によって簡単にわかる。これでこの問題を解くことができた。
包除は苦手意識があり、今回も微妙にはまった。bit全探索をするfor文のスタートを0にしていたため、空集合まで計算してしまっていた。これは次から気を付ける。
Clangをコンパイルしてみているのだが、一日かけてもまだ終わらない。午前10:30に始めたのに、日付が変わるころになってもまだ40%台でうろうろしている。明日中に終われば良いのだが。
何回かエラーで落ち、そのたびにビルドを再開始したら結局普通にコンパイルが進むので、whileコマンドで無限リトライを仕掛けた。いったん落ちても再開始すればちゃんと進むということはコンパイラがメモリリークなどしているのでは？という気がするのだが。いや、そもそも1GBプランのVPSなのでClangのコンパイルにはスペックに足りていないということなのかもしれない。
コンパイルの負荷のせいでこのブログが落ちるなどした。多分メモリ不足なのだろう。
Siv3Dを教える必要に駆られたので、良い感じのサンプルをちょっといくつか作った。
今日は一日外に出ないで過ごしてしまった。
Categories: 未分類