バーチャルコンソールなどをいっぱいダウンロードしたらWiiUの容量がカツカツになってしまったので、USBメモリを購入してデータを移した。14GB移すのにちょうどぴったり1時間程度かかった。
14GBの内12GBはバイオハザードリベレーションズだった。デカすぎんだろ…
Vulkanの記事を更新した。説明の仕方に迷ったためモチベが下がっていたが、これまでの記事を読み返したら頭の中で道筋が定まったため、モチベが回復した。
「これまでの流れ」を見ると「(期待される)これからの流れ」も見えるようになる。文学にしろ音楽にしろ、大体のコンテンツには「流れ」というものがなんとなくあるというか自然に出来る。それに乗れればいいのだが、コンテンツを作っている最中はコンテンツを辿る動きが遅すぎて、流れが見えなくなってしまう。
まあ、一度「流れ」が出来てしまうと軌道修正も大変なのだが。今のところはそう大きくダメな流れは出来ていないと感じたので気分よく続行。
今日解いた競プロの問題。
ABC235-E 自力AC。クラスカル法とクエリ先読みを念頭に置けばそう難しくはないが、ちょっとした応用ではあるので歯ごたえはあった。こういう、「アルゴリズムを振り回す」だけでなく「アルゴリズムの性質自体を考察して利用する」タイプの問題は若干の苦手意識があるが、バッチリ決まると気持ちいい。
ABC220-F 自力AC。簡単な類の全方位木DPだが、全方位木DP自体にあまり慣れていないのでやや時間がかかった。この問題をやってたらようやく考え方のコツがつかめた気がする。
全方位木DP(ReRoot)は、ある根付き木$A$に対して何らかの値$f(A)$が決まる時に、ある木の全頂点についてその頂点を根としたときの$f$の値を求めるものだ。この時、求めたい値は以下のような性質を満たしている必要がある。
$A$を根付き木、$root(A)$を$A$の根となる頂点、$B_1…B_m$を$A$の直下の子ツリーとする。
$f(A)=g(root(A), f(B_1)\oplus f(B_2) \oplus … \oplus f(B_m))$
ただし$\oplus$はなんらかのモノイドである。
つまり、「根ノードの情報」および「子ツリーにおけるfの値の総和(的なもの)」だけで決まる必要がある。
もっとかみ砕いて言うと、まず根単体の時でもなんらかの値を持ち、そこに子ツリーをガシガシ加えていくとその子ツリーにおけるfの値がなんかどんどん足されていくイメージである。
ReRootの考え方としては、まず適当な頂点を深さ0として深さを定義して、DFSで全ての部分木における値を計算する。そのあと上向きでカウントされてない分を加えて完成させる。この「上向きでカウントされてない分」を計算するときにその部分木自体を含んだ値を使うと支障がでるので、良い感じに取り除く。
この「子ツリーを足す」「子ツリーを取り除く」動作が今まで上手くイメージできていなかったのだが、要するに各頂点が「子ツリーのfの値の総和」を持っており、子ツリーを加えたりもぎ取ったりするとそれが変動するというイメージがついてようやく感覚的に納得できた。
文章で説明すると意味不明だな。図を書くほどの気力もないしこれでいいや。
自室のSFC環境が整ったので、ジャンク屋でカセットをいくつか安く買った。
ロックマンX2, X3, カービィボウルを購入。ちょっとずつやるぞ～。
初代ぷよぷよがやたら多く売られていた。なんかこういうところで沢山売られているとちょっと悲しい。
自室のケーブルがだいぶこんがらがっているので整理した。多少マシになったかも。
ダイソーで買った、ケーブルの先端をいつでも外せる形でまとめるやつがなかなかいい。ブランブランしていたHDMIケーブルなどの類が使っていない時でも居場所を持っている。
モニタアームにくっつけているのはちょっとどうかとは思うが。(他に場所がなかった)
ここ2,3日、レトロゲームの買い占めをやっていて作業が進んでいない。今日はVulkanの記事が進んだので良かったが。
イラストとサークル内での講習会とツール開発と他にもいろいろあるのだからのんびりはしてられない。
しばらく前に試しに買ってみたラズパイピコの使い道に悩んでいる。演算性能を生かしてmidi音源でも作るか。
ここ2日筋肉体操と鬼トレをさぼってしまった。
筋トレはどうせ5分なのでただの怠慢だが、鬼トレは毎回それなりの時間を食うのでルーティーンの見直しを少し考えている。
Categories: 未分類