電子工作のプロジェクトを完遂したので次なにやるか思案中。自作コメントシステム(Masacarri)とVRゲームフレームワーク(VRaster)をそれぞれ整えたいが、サイトのWordPress→Zola移行も考えたい。
今日解いた競プロの問題。
ABC268-F: 順列の最適化には苦手意識があったが、ちゃんと考察を進めたらまるで教科書のような典型問題だった。いい加減順列への苦手意識は克服したい。
既にいくつかの$S_i$をくっつけていたとして、ある$S_i$を後ろに1つくっつけた場合にいくらスコアが増えるかを考える。それぞれの数字について「その数字×その数字の前にあるXの数」になるので、既に完成した部分の文字列に含まれるXの数をkとするとkの一次式になる。例として「X9X5X」という文字列を考えると
$(k+1)\times 9 + (k+2)\times 5 = 14k+19$
になる。それぞれの文字列が為す貢献はこの際の「kの係数」「切片」「Xの数」の3つの整数だけで表せることになる。文字列$S_i$のそれをそれぞれ$p_i,b_i,x_i$と表すことにする。
Xが$k$個、スコアが$s$の文字列に文字列$S_i$をくっつけると、Xが$k+x_i$個のスコア$s+kp_i+b_i$になる。
順列の最適化と言えば貪欲法か挿入DPあたりが基本だが、制約からしてこれはもう貪欲法しかないので、順序を貪欲で決める時の基本「入れ替えて得をしない」条件について考える。
$S_i$と$S_j$を順に付けたとする。
$(k, s)\rightarrow (k+x_i, s+kp_i+b_i)\rightarrow (x+x_i+x_j, s+kp_i+b_i +(k+x_i)p_j+b_j)$
$s+kp_i+b_i +(k+x_i)p_j+b_j=s+k(p_i+p_j)+b_i+b_j+x_ip_j$で、$S_i$と$S_j$を入れ替えた場合のスコア差は$-x_ip_j+x_jp_i$である。これが正にならなければよいので、$p_i/x_i$でソートすれば良い。$b_i$は順序決めに影響しない。
愚直に数式を立てればそれぞれの文字列の特性を3つの数値で代表させられることが分かり、そして愚直に「入れ替えて得をしない条件」を数式で考えれば解ける。終わってみれば貪欲法の教科書のような問題だった。
部屋の片づけを少しした。セキュキャンで増えた荷物を整理していないままだったので部屋の容積が減っており、さらにこの前段ボールの塔が1つ自重で半壊したので手を付けあぐねていた。
古い段ボールを畳んで新しい段ボールに詰め替えた。ホームセンターで買った段ボール箱は100均の箱と違ってちゃんと重みに耐えている。ダイソーの段ボールBOXは5段も積み重ねていいものではなかったらしい。
とりあえず床に寝っ転がれる程度の隙間ができた。これで筋トレもはかどるだろう。
部屋で片づけたいもの…
- 電子部品の山
- 本の山
- セキュキャンの荷物
- 何かの梱包に使われていた発泡スチロール(捨てる)
- もう使われない空の段ボール箱(捨てる)
- PC部品の空き箱の山(説明書・保証書なども付いているので悩み中)
電子部品の山のなかには仕分けの面倒なジャンク品も結構あるので処分したい気持ちもあるにはあるのだが、せっかく(そのときは)面白そうだと思って買ったので有効活用したい+そもそもどう処分したものかよく分からないので扱いに困っている。
Categories: 未分類