今日解いた競プロの問題。
ABC226-F: 数え上げ問題。行けそうなのでやったらいけた。順列というワードには苦手意識があったのだが、今回はグラフとして考えることで考えやすい形にできた。
各要素を頂点、順列による移動を有効辺として考えると、全ての頂点の入次数と出次数が1であり、自己ループを許すような有向グラフとなる。これはいくつかのサイクルの形になる。$S(P)$の値は各サイクルのサイクル長の最小公倍数をとれば良い。
グラフ形状が同じならば異なる順列$P$でも$S(P)$の値は同じになる。なので全ての順列の場合を考える必要はなく、全てのグラフ形状の場合について調べれば良い。
今回のグラフの構造を踏まえると、グラフ形状が同じということはN個の頂点の分割の仕方が同じということである。ただし各頂点は区別されない場合の分割である。広義単調増加であって総和がNとなるような数列をDFSで列挙すればよい。これは実際に実験してみると、$N=50$でもせいぜい$2\times 10^5$通り程度でしかないことが分かる。各場合における計算に$O(N)$かけても余裕で間に合う。
最後に、グラフ形状の等しい順列のパターン数を計算する必要がある。サイクル長が$m$種類あって、i番目のものがサイクル長$L_i$、サイクル数が$X_i$個だったとする。まず残りの決めていない頂点から$L_i\times X_i$頂点を取り出すパターン数を数える。これは$_{(残りの頂点数)}C_{L_iX_i}$なので簡単に求まる。次にその中での頂点のつなぎ方を考える。これはガチャガチャやると分かるが、$(L_iX_i)!/\prod_{k=0}^{X_i-1}kL_i$になる。これは$O(N^2)$の前計算で予め求めておけばよい。これでこの問題が解けた。
- グラフでなかったものをグラフとみなし、
- そして次数からグラフ形状の特性を考えて考察を進める
- 見積もりが難しい計算量を実験的に確かめて実際には間に合うことを確かめる
といったポイントを上手く実践できたのでうれしい。
コメントシステムの開発を進める。今日は開発はあまり進まなかったが、こまごまとした調整・修正と今後の実装内容の整理が出来た。
- 同じページ内に返信先コメントがない時に飛べないバグを修正
- 1ページあたりのコメント数を20→7に変更
- 後ろ側に飛べるページ番号が「(現在のページ番号+最後のページ番号)/2」になっていたのを「(現在のページ番号+最後のページ番号+1)/2」にした
今後の実装内容としては
- システム管理ユーザ用のユーザシステムの実装
- ユーザの作成/削除
- パスワード認証/ログイン
- 送信中アニメーションの実装
- 送信したコメントを自動で表示に追加
- 読み込み中アニメーションの実装
- 返信一覧表示、文脈一覧表示におけるペジネーションの実装
- 特定のコメントのページに移動
- URLアンカーで飛べるようにする
特定のコメントのあるページ番号を求めるには各コメントへの採番がほぼ不可欠だが、新たなカラムを増やすのはだるい。そこで調べてみたところSQL関数でROW_NUMBERなる関数があるらしく、これを使うと良さそうだった。
SQLの勉強意外と役立つなあ、となっている。パフォーマンスを求めるならばあまり複雑なクエリを飛ばすべきではないので複雑な機能の勉強は意味がない、みたいに思っていたのだが、SQL側に処理を任せられるのならばものによっては実装難度的にもパフォーマンス的にもその方が良さそうだという風に考えが変わった。
複雑すぎるクエリを飛ばすべきではないというのはやはり変わらないが、本質的に複雑な機能を作ろうとしたならば結局自分のコードで実装することになるため、複雑性をSQLのクエリと処理に任せるか自分のコードでやるかの違いになる。そこで必要に応じてSQL側に任せることを選択するのはパフォーマンス的にも間違いではないはずだ。
シェリー「フランケンシュタイン」を読了した。先手を打って倒してやろうとエリザベスのそばから離れるの、それはフラグだよフランケンシュタイン。火を見るより明らかな結末だろう。
追いかけっこしてるときの怪物めちゃ楽しそうで笑った。
ラストの怪物の生き様が悲しすぎる。復讐は行われなければならなかったという信念を持っているのと同時に、殺した人間への哀れみと悔悟もしっかり持ってるの重いし真面目過ぎる。それでもって最終的に「自分が生まれてきたこと自体が間違いであり、繰り返されてはならない」という同じ結論に達しているのが悲しい。いやもうお前、罪悪感とかかなぐり捨てて「全部フランケンシュタインが悪い」で済ましても良いと思うんだけど。でもそれが出来ないのが「本来この怪物は優しい心の持ち主」ということの証左でもあるんだろうな。最近の漫画とかだったら「生まれてきたこと自体が間違いなんてことはありっこねぇ！」みたいな論理のほうがよくありそうだが。
全編通して結局のところ、この怪物の容姿が悪いのが全ての原因みたいに思えるのだが、もしもフランケンシュタインの怪物の見目が整っていたらというifを妄想せざるをえない。まあ物語論理的には「人間が人間を造りだすこと自体が神の領域に触れる禁忌であり、歪みを生み出す」という話なのだろうからそこは本質ではないのだろうが。聖書の創世記になぞらえて考えれば、神が作った神の似姿は人間であって神ではないのだから、人が作った人の似姿もどうやっても人たりえないという摂理なのかもしれない。
サン・テグジュペリの年譜を見ていたのだが、4回飛行機事故で大怪我してそれでも飛ぶのをやめず、最後飛行機に乗って消息不明になっている。どんだけ飛びたいんだこの人？
歯ブラシを新調したら死ぬほど歯がキレイになるようになった。定期的に交換しないとだめだな。
Categories: 未分類