一週間くらいずっと生活習慣が壊れている気がする。メンタルも優れない。外に出ていないのが大きい。運動も出来ていない。室内でも運動は出来るが、自作PCとVR機器の箱が邪魔でどかすのも億劫になってしまっている。
今日解いた競プロの問題。
ABC258-F: コンテスト中に書いたやつをちゃんと見直したら通った。悔しい。
マンハッタン距離っぽい感じなので、種類の違う道路が関わらない限りはジグザグに動いてもL字型に動いても同じ距離になる。また、普通の道路から大通りに脱出する場合、まっすぐに上下左右のどれかに移動するのが最短になる。大通りに囲まれた違う区画に移動する場合、どっかしらで大通りを使った方が早くなる。こうした辺りの性質から、たぶん「スタート/ゴールのx/y座標」「スタート/ゴールのある区画の大通りのx/y座標」以外は考えなくて良さそうという感じになる。厳密な証明ではないが。
ということで、x/y座標それぞれ最大6通りで計36の状態しかないので、そこの上でダイクストラすれば定数時間で最短距離が求められる。
ABC214-E: 番号の小さい箱から順に見ていく。ボールをしまえるのにしまわないのは損でしかないので、新たなボールをしまえるようになるたびにしまっていく。このとき、より早くしまえなくなってしまうもの(=$R_i$が小さいボール)から順にしまっていく。平衡二分木なり優先度付きキューなりで解ける。すべての箱を順に見ていくと当然TLEなので、$L_i$を見てどうでもいい箱は適宜飛ばしていく。
ABC207-D: 幾何。やるだけといえばやるだけなのだがかなりだるい。S,Tのある2点を対応付ければ変換方法は一意に定まるので、Tのどの2点をSの$(a_1, b_1),(a_2,b_2)$に対応付けるか、というのを$O(N^2)$パターン全探索する。1回の判定に$O(N)$かかって$O(N^3)$になってもN≦100なので余裕で間に合う。あとは数式をこねこねして頑張る。計算誤差が出ないように分母を払うこと、回転と移動は許されているが拡大縮小、鏡像変換、せん断変形などは許されていないことに気を付ける。そしてN=1がありうることに注意。この場合は当然無条件に可能になる。
OpenXRをいじっていたのだが、一向に表示がうまくいかない。正常に動くサンプルプログラムを少しずつ変形して動かない自分のプログラムに近づけていく最終手段に打って出た。道は長い。
深度バッファを入れたがやはり無意味だった。あと違いがあるとすれば、同期にフェンスを使っているかvkQueueWaitIdleを使っているかくらいか。あとは生Vulkanを使っているかVulkan-Hppを使っているかの違いとか。全然本質的な違いではないと思うのだが。
全然動かないせいか、精神状態が良くないせいか、食欲が出ない。
暑いからと冷房ガンガンに効かせた狭い室内に籠っているの体が冷えて良くない気がしたので、エアコンを止めて半裸で過ごした。すごく無意味だった気がする。
Categories: 未分類