徹夜と寝落ちで土、日と日報を書き損ねてしまったため、今日思い出せる範囲内で書いた。
一応毎日Twitterであいさつをすることで生存報告としているつもりなのだが、こんな感じになっているとちゃんと機能していないことになりそうだ。寝落ちはもうどうしようもないが、徹夜するなら徹夜するでその報告くらいはしても良いかもしれない。
もろもろで買う動機ができてしまったのでPICO4をポチッてしまった。明日にはおそらく届く。
スタンドアロン型HMDでのOpenXR動作実験がどうしてもしたいのに加え、文化祭のネタとして使えそうだなという動機。高い買い物だしValve Indexの方もまだまだ使いこなせてないが、こういうのは機を見て敏に動かなければならないと思ったのだ。今のところこれ以上の高い買い物をする欲求はないので、まあずるずると出費がかさむ要素はない、はず…
高い買い物と言えば双眼実体顕微鏡とかWacomの液タブとかNintendo Switchとか買いたいといえば買いたいのだが、直ちに必須ではない。あとは本棚あたりかな…
運よくラズパイ4の入荷通知に一早く気付けて購入できた。ようやく最新のラズパイにありつける。一応家に一台あるのだが、チップが古いせいでブラウザが立ち上がらず、PC的な用途ではあまり遊べないのだ。
購入後に在庫の推移を見ていたのだが、4GB/8GBはすぐに売り切れたものの2GBは結構残っていた。少なくとも30~40分くらいはもっていたように思う。ラズパイの魅力は安価さであって、2GBは一番安いのだから一番早くに売り切れると思っていたのだが、逆のようだった。ワンボードコンピュータにそんなにスペック求めることある？という気持ち。あるいは5千円程度の差はある程度財力のある大人ならばそこまで気にならないのか？
今日解いた競プロの問題。
ARC132-C: 自力AC。ARCの青diffを久々に解けて気持ちよかった。
個人的に苦手意識のある順列問題だが、制約を見てみると$d\leq 5$という制約が目を引く。この時点で実はだいぶ状態数少ないのでは？という考えが出てくる。ある未決定の$p_i$を決定するとき、選択肢として選べるのは$2d$通りしかない。
順列を考える時の難しさのコアは「既に選んだものを選んではいけない」ことにある(と個人的に思っている)が、この問題の場合はそもそも選択肢が高々10個くらいしかないので、全てについて「既に選んだかどうか」を十分管理できる。さらに言えばこの問題はパターン数を数える問題であって、順列を具体的に構築しろという問題ではない。
ということで、端から順に決めていくDPを行えばよい。i番目を決めるとき、$i-d, i-d+1,… i+d$のどれを既に採用したかが分かればいいので、状態としてそれだけ持てば良い。$2^{2d+1}$通りは十分に小さい。状態として管理する範囲は1つずつずれていくわけだが、選ばれないまま範囲外に行ってしまう場合は順列として成立しない訳なのでパターン数として数えない。
こんな方針で上手くいくのか？と思いながら実装してみたが、なんか一発ACしてしまった。$O(N2^{2d}d)$。
Categories: 未分類