今週の胎界主を読んだ。日奈子、トラウマを克服したという話は分かるが割と攻撃がえげつないぜ！まあ相手が相手だから別にいいか…
秋月でPIC16F193xシリーズがなんか手に入りにくくなってそうな気配を感じたので、microchipのサイトを確かめてみたら代替機種としてPIC16F1915xが推奨されていた。もう古い型番の扱いなのだろうか。生産は続けているようだが。
しかしPIC16F1915xはさらに手に入りにくい。どうにかしろ。
このはカレンダーが8月のままになっていたのでめくった。
10月はハロウィーン仕様でキョンシー。手間のかかってそうな服。
9月はシンプルに散歩中の一コマみたいな感じの絵だった。個人的にはこういうカメラに媚びてない感じの構図のイラストが好きだったりする。
筋トレをした。今日は腹筋。思い出したように雑にやったのでなんかあんまり効かせられなかった感。
昨日は腕立てをしたあとにそこそこ念入りにストレッチをしたせいか、今日は肩回りの筋肉痛がそこまでひどくなかった。
今日解いた競プロの問題。
ARC146-B: なんとか自力AC。怖くて避けてたけど、ARCの水diffもしっかり時間かけて考察すれば解けるくらいの力は今の自分にもあるんだな。本番でスパッと解けるようになりたい。甘ったれなので本番出てないが…
辞書式順序と同じく、数値の大小は上の桁が支配的な意味を持つ。ある桁を決めている最中に「より下の桁で損して最適でなくなる」というようなことは考えなくてよい。ということで最上位bitから順に、全操作回数を使って1に出来るか考えればよい。
具体的な判定方法としては、全ての$A_i$について「(すでに決めたビットを考慮しつつ)現在のビットを1にするために必要な最小の操作数」を計算してソートする。そしてその内の最も小さいK個の和を取り、Mを上回っていたらどうやっても不可能。逆にM以下ならば可能なので即採用。やることはこれだけなのだが、「すでに決めたビットを考慮しつつ」がちょっと曲者。
例えば「1010xxx」という風にすでに上位bitが確定していて、上から5番目のビットを決めるために「10101xx」が達成できるか判定したいとする。このxxを0にした「1010100」を「目標値」と呼ぶことにする。このとき$A_i$が「0」とか「1000101」とかならば必要な最小操作数は簡単に求まる。$A_i$は目標値より小さいので、単に目標値から$A_i$を引けば良いのだ。しかし$A_i$が目標値より大きい数値の場合は話が変わる。
例えばこのとき「1101010」に必要な最小操作数はいくらか。結論から言うと「1110100」から引いた数値が答えになる。この数値はどうやって出すかというと、目標値1010100を上位bitから順に$A_i$と比較していき、$A_i$側のビットを目標値にORしていく。「$A_i$側のビット<目標値側のビット」なるビットが見つかった時点で中断する。ちゃんとした証明は面倒だが、これで「A_iより大きい数値かつ目標値に示されるビットが全て1であるものの中で最小の数」が求められる。
計算量$O(N\log^2 (\max A + M))$。
Categories: 未分類