JOI予選 - ビンゴ
元気でした(過去形)
ここからまあまあ長い前置きです
先日、我が校は中間試験だったわけで、その中にプログラミングの試験があったのです。
その中の問題の一つに、ビット演算を使って8bit整数の正負を判定しなさい、といった問題がありました。
模範解答は "( (n >> 7) & 1)" だとか "(n & 128)" みたいなものでしょうか。
しかし、某が "(n & 10000000)" と書いていて、なんやこれは(驚愕)となっていたのが実際に動くんですよ。
それで教員やら僕やら回答者やらが困惑する、といった事件がありまして。*1
後日調べたところ、10進数 "10000000" を二進数に変換すると "100110001001011010000000" になって、下8bitが "たまたま" 一致した、と夕飯のときに聞いてその時は納得したのですが、この世にたまたまはない。と、かの有名なぼく*2が言っていたので、その時から気になってしまって土日かけて調べました*3
考えたこと : 10 ^ n を二進数表記した時、下 n bitと10進数表記が一致するのではないか
結論から言えばこれは正しいみたいです。
数学的帰納法とかで証明しようとすれば、最終的に奇数の冪は奇数になるか、といった命題に帰着できるはずなので興味があれば考えてみてください
実はこれまでのことは夕飯を食べながらすでにあらかた考察は終わっていたのですが、他の進数での和、積、分配法則、交換法則とかとかがどうなっているのかとかあまり知らないなと思いまして。
基数を変換しただけなのでほとんど自明に成り立つと思うんですけど、そもそも10進数でのこれらのことすら知らないんですよね。
今度時間があったら考えてみようかと思います。
前置きおわり
まあまあ前に解いた問題
問題を読みます
問題を読むと、n * n のビンゴ == 長さ n * n の単調増加列であることがわかるので、何も考えずにO(MSN^2) のdpを書いたのですが -> TLE
本当によくわからなくて死んでいました
わからなすぎてむしろわかりそうになってきたので解説を見ながらコードを書いたのですが、微妙な理解しか出来ませんでした・・・・
どうやら空間計算量を落として高速化すると通るらしい
また忘れた頃に解き直そうかと思います
ただでさえ DP が苦手なのに for で解こうとすると死んでしまうので慣れていきたいです
ぴょんぴょん川渡りを for で解こうと頑張っています(誰か助言とかくれたらうれしいです)
