今朝は一応6時台に起き、ラジオ体操までやったが、午前中に寝まくってしまった。
今日解いた競プロの問題。
ABC250-E 解説AC。水diffなので悔しい。
最初セグ木に集合を乗せてみるなどしたのだが、当然$O(N(\log N)^2)$になり(いや、$O(N^2)$くらいになってるかもしれん)TLE。クエリ先読みしたりしてソートしたりしても特に有用な方針は立たず、まったく発想が出ないので解説を読んだら1行目で察した。
左からx個とった集合の要素数は前計算すれば求められるので、要素数が違う場合は容易にNoと確定できる。負け惜しみだがこれは正直自力で気付いていた。が、Yesの判定にはつながらないだろうということでその方針の考察をやめていた。実際には、左端から取っていくというルールがある都合上要素数が決まれば集合自体も確定する。そのため各i=0…Nについて、Aの左端からとった集合の要素数とBの左端からとった集合の要素数が両方iだった場合に等しいかどうかを前計算することで求めることができる。
「必要条件を集めていくと十分条件になってしまう」典型の亜種と言っていいのだろうか。二択問題なら確定できるものは確定するアルゴリズムを考えてみれば良かった。
ここ最近「とにかく時間とメモリが無制限にあるなら解けるか」→「それの計算量は落とせるか」という順序で考察する問題に慣れていたのもあるかもしれない。「特定の条件を満たすケースで通る解法は作れるか」→「他のケースも通るように拡張できるか」「他の解法と組み合わせれば通らないか」などを考える、というパターンも見据えた方が良いかも。
WordPressのエクスポートデータをZolaにぶっこめるmdファイルに変換するプログラムを書いた。Rustの勉強も兼ね。
xmlのパースに使えるクレートとしてserde_xml_rsというクレートがあったのでありがたく使わせていただいた。クレートという時点でRust用なんだからrsなどという接尾辞は基本つけないと聞いたのだが思いっきりつけている。なぜ。
とりあえず
- 書き物(https://k.foolslab.net/writing)
- やっていくシリーズ(https://foolslab.net/do)
- 日報(https://k.foolslab.net/dailyreport)
あたりは適宜やれば割とすぐ移行できそうだ。画像周りが面倒そうだが。
lablogはコメント欄が一応あるのでそれは移したい。なんだかんだ自分の記事に書かれたコメントはいとおしい。
ZolaはSSGなのでコメント機能など望むべくもないが、埋め込み型のコメント機能をZolaと関係なく作ってZolaの自作テーマに埋め込むのは技術的にはそこまで変な話にはならないはずだ。
今日摂取したコンテンツ。
昔のアニメのそれっぽさがすごい。
Categories: 未分類