今日解いた競プロの問題。
UTPC2011-E: ちょっとだけ解説見てしまったが、半分くらいは自力で考察してACした。
Bでソートするのは自力で思いつけた。区間スケジューリングと似た感じの発想？(似てないか…)
その後はDP高速化だとか挿入DPだとかまごまご考えていたが、そもそも最終形をソート順と仮定して良いということに解説をチラ見して初めて気付いた。というかソートに気付けたのになんでそれに気付けなかった。
下手な貪欲は死ぬというのは身に染みて知っているのでこれもちゃんとDPやらなくちゃという思考が先立っていたような気がする。貪欲+DPみたいな感じの問題でどこまでを貪欲法で確定できるか、みたいな感覚がまだ十分に鍛えられていないのかもしれない。
この後は大体流れで進められた。
- ソート後の前からi番目までを見たときの最適解を調べたいな
- 最適というのはつまり出来るだけ短い時間で出来るだけスコアを上げたいということだな
- 「同じ時間でのスコアを最大化する」と「同じスコアでの時間を最小化する」の2パターンがあるけど時間軸クソ長いから後者の方が良さそうだな
ナップザックDPでも「同じ重量での価値最大化」と「同じ価値での重量最小化」の2パターンがあるが、後者をやることが少ないのでなかなか頭に上らなかったというのもあったかもしれない。これはよろしくない。出来るだけ状態量の少ない軸を見定めてそこに注目するというのはDPをやるときの基本的な思考だ。
Masacarriにコメントモデレーション機能を実装した。久しぶりにRust(というかdieselのコード)を触り、書き方を思い出すのに時間がかかった。
とりあえず最低限スパムとマーク出来る機能を付けたが、もうちょっといい感じのUIにしたい。現状だと管理画面からコメントをスパムとマークした後にその場で表示が更新されないという問題がある。
フロントエンドの設計があまりちゃんと分かっていないせいで微妙なつくりになってしまっている。
筋トレをやった。今日は腕立て。さすがに3日前の腕立ての筋肉痛は収まっていた。
古い薄型PCをタブレットとして活用するために、いろいろごちゃごちゃ入れていたソフトをアンインストールして軽量化する作業に着手した。
ブラウザとイラストソフトだけあればいい。重いソフトや要らないデータを片端から消したらとりあえず50GBくらい空いた。まだまだ消していいものは沢山ある。
Categories: 未分類