書き物(https://k.foolslab.net/writing/)をZolaで置換してみた。Slimというテーマが割とシンプルで良さそうだったので採用してみたが、非日本語圏で作られたものだからかちょっとフォント周りに問題があるな。明らかに中国語の漢字が入っている。
今日解いた競プロの問題。
競プロ典型90問
031 VS AtCoder: Grundy数を履修したら解けた。
今まで「遷移先のGrundy数のmexとして定義される」の部分しか知らなかったが、「複数のゲームが並立する場合は各ゲームのGrundy数のxorとして求まる」という重要な定理を今日知った知った。これまで完全に片手落ちの知識しかなかったんだな…
このブログはちょいちょい読んでいたのだが、一番最後の段落までは目を通していなかったのだ。これはひどい。
Grundy数が力技で求まるのは状態数が小さい場合に限られるが、並立するそれぞれのゲームの状態数が十分小さければ、並立するゲームが多くてもこの定理によって求められる。これはいいことを学んだ。
実装についても色々学びがあった。まず、各状態のgrundy数を求めるためにforループで各状態を探索していたが、ある状態のgrundy数は遷移先の状態のgrundy数に依存するため、どちらかというとメモ化再帰の方が実装の筋が良い。
それからmexを求めるためにsetを用いていたが、vectorを用いた方が遥かに速かった。mexは「ある集合に登場しない最小の非負整数」なので、その集合の要素数より大きい数字になることはない。(例: {0, 1, 2, 3}のmexは4)なので、ある状態のGrundy数が遷移先の状態数よりも大きなGrundy数になることはありえない。なのである状態のGrundy数を計算するときには、遷移先の状態数+2くらいのサイズのvector<bool>配列さえ確保しておけば事足りるのである。遷移先の状態のGrundy数が大きく配列範囲外になることはあるかもしれないが、それは端でclampしてしまえば問題ない。遷移先のGrundy数に範囲外になるような大きさのものがあるならば、より小さい数字に抜けが出来てそちらがmexということになるからだ。
lablogで下書き状態になっていた記事その2を投稿した。
これで前々から放置していたdraftはもうない。
あとはConoha用の証明書自動更新プログラムの記事を出したい。
副産物として出来たConoha API用のバインディングをちゃんと整備してみたい気持ちもちょっとあるが、労力のわりに需要が無さそうな気もする。トークン発行とDNSだけでも需要はあるだろうか。
筋トレやった。今日はスクワット。
その日やることを決めない感じの日々が流石にアレに感じてきた。
しかしやることを決めた時間を詰め込みまくってもあれなことが分かり切っている。決めた時間とそうでない時間をいい感じに配分した方が良いのか。
なんにせよ今日は眠いので寝る。
Categories: 未分類