今日解いた競プロの問題。

ABC146-F: 期待値DP。いい感じに自力で詰めて解けた。Sugoroku 3とEDPC-Jも経験したので、もうちょい場数をこなせば手早くできるようになりそう。

$p_i=(マスiからマスNへ到達するまでの手数の期待値)$と定義する。$p_k=0\ (k\geq N)$であり、求める答えは$p_0$になる。

振出しに戻るマスでないならば$p_i=\sum_{k=i+1}^{i+m}(1+p_k)/M$が成り立つ。$p_i$は$p_j\ (i<j)$のみを用いて求められることになるので後ろから求めていくことが出来る。

問題は振出しに戻るマスの扱いだがこれは$p_k=p_0$とする。そうすると当然ループが生じるので、これは気合で何とかする。具体的には、各$p_i$を計算していくにあたって単なる数値を管理するのではなく$p_i=c_i+b_i p_0$という一次式の形で管理する。この形で計算していくことによって最終的に$p_0=c_0 + b_0 p_0$という形になり、$p_0=c_0/(1-b_0)$として答えが求まる。

これ$K\leq 10$である意義がよく分からんかったな…適切に累積和を用いて高速化すれば$O(N)$になってKには依らないと思うんだが。

---

自作コメントシステムがだいぶ良くなってきた。

• 返信の件数を表示
• 返信の数が0ならば「返信一覧」のボタンは表示しないように変更
• 特定のコメントに対する返信でないのならば「文脈を読む」のボタンは表示しないように変更
• 返信先のコメントへ移動できるようにした
• 新しいコメントを下に表示するように変更、Twitter式をやめた
• Atcoderライクな二分探索可能なペジネーション

返信の件数の表示周りの実装のためにSQLをがっつり勉強することになった。今まで取得クエリと言えばSELECT、WHERE、OFFSET、ORDER BYくらいしか分かっていなかったのだが、テーブル結合というものを勉強した。今までそういうものがあること自体知らなかった。さらにWITH/DISTINCT/GROUP BY/サブクエリといった知識を新たに仕入れた。SQLの世界がだいぶ広がった気分だ。こんな複雑な知識を駆使して書いたクエリは重いんじゃないかみたいな懸念もあるが。

さしものdieselもさすがにそんな複雑なクエリの構築には対応していないので、結局生SQLをソースコードに書くことになった。sql_queryマクロを用いてやっていくのだが、これを使ったクエリを送ってload()する際はモデルにQueryableではなくQueryableByNameトレイトを実装しなければならないらしい。情報が少なすぎて参った。

i64はBigInt、i32はIntegerと対応させなければならないみたいなルールにもかなりハマった。あんまり暗黙的な変換を期待してはいけない。自分はその辺の感覚は持っているものと高をくくっていたのだが、どうやらi32→BigIntのようなアップキャストすらもあまり期待しない方が良いらしい。これにはかなり面食らって苦しめられてしまった。

• sql_queryのプレースホルダを使うためにbind::<BigInt, i32>としたらエラーが出た。
• モデルに追加のカラムを定義する際、#[sql_type = "Integer"] pub count_replies: i64としたらエラーが出た。

load()を呼ぶ段になって謎のエラーが出ることになるので、どこを解決すればいいのかも分かりづらい。C++のテンプレートのエラーを彷彿とさせる。Rustはコンパイルエラーが親切なのが売りなんじゃなかったのか。