今日解いた競プロの問題。
ABC283-G: noshi基底を履修した。(noshi氏本人はnoshi基底と呼ばれるのにもにょっているらしいが…)
基底をとるのは良いが、下から何番目というのを順に生成するところをどうにかする必要がある。そこでまず単純な場合を考えてみると、もし基底が単に$(1,2,4,8,…)$となっていた場合は$s_K=K-1$が成り立つ。ここから類推すると、$s_K$を算出するには基底をソートした上でK-1のビットパタンを考え、i番目のビットが1ならばi番目の基底を採用する、みたいな感じで構成できそうな気がする。しかしそうは問屋が卸さない。
例えば$(1,2,5)$みたいな基底が取り出されたとき、先ほどのような方法で$s_i$を生成すると$s=(0,1,2,3,5,4,7,6)$となり正しい順序通りの結果は得られない。何が悪かったのかと考えると、なんかこう、MSBが序列を支配してくれれば順序通りの結果が得られそうなのだが、先の例の場合1という基底がありながら5という基底があり、既に5があるところに1をXORすると値は小さくなってしまう。
要はあるビットをMSBに持つ基底があるならば、他の基底においてそのビットは0でなければならない。このような状態を実現するために、自分はnoshi基底の方法で基底を求めてソートしてもう一回基底を求めなおした。なんか解説だと良くわからん改造を加えていた。
正直使いこなせるようになったとは言えないが、とりあえずパッと書けるくらいには覚えたのでぶんぶん振り回していきたい。
何やら最近Atcoder Problemsの応答が悪い。開発者ツールで見てみるとAPI呼び出しが502とかにちょくちょくなっている。
しばらく前に買って最終面まで行った後放置していたlinelightをあらためて攻略しているのだが、ワールド選択画面で表示をよく見ると、ワールド上にまだ行っていないエリアがあることがちゃんと分かるように作られていることに今更気づいた。なぜ過去の自分は気づかなかったのか。一気に実績が4つくらい増えた。
Vulkan入門をMarkdownにして新サイトに移植する作業を進める。道が長い。
Categories: 未分類