なんかすごい早起きできたが、すごい昼寝してしまった。意味ナッシング。睡眠不足は良くないが、生活リズムを調整するためにも寝ないと決めたら寝ない能力が欲しい。
歩いてればさすがに寝ないから、特に予定のない日は午前中に外を出歩く予定とか雑に入れとけばいいのかなあ。でも結局帰ってきたあと寝そうだなあ。散歩は好きだけど歩いてる最中は進捗は出せないから、あんまり長時間やりたくはない。
眠気が溜まってるときは座ってるだけで眠くなってくるし、立って作業できる自習室とか近場にないもんか。
冬休み明けまでの課題と病院予約などのTODOを処理した。
今日解いた競プロの問題。
ABC214-F: 一応自力AC。この問題は「一個飛ばしで選ぶ際の部分列のパターン数」を数える問題だが、ただの「部分列のパターン数」を数える問題すら解けないことに気付き、部分列DPを履修した。
「重複して数えてしまう場合、なんらかのルールを敷いてその中の一通りだけを数えるようにする」というのが部分列DPの基本的な発想。これは広い範囲の数え上げ問題で使えそうな考え方だと思った。ただ、部分列DPはそれに加えて「i文字目以降で最初のある文字の位置」という補助線を引く工程があるので、上記の考え方を持っていたとしても今の自分の実力だと自力で部分列DPを編み出すのは苦しかった気がする。「重複するものをどうにかして一通りに縛る」「DPテーブルと別に補助線を引いても良い」この辺は抽象的な発想法として要復習。
部分列DPを履修した後もだいぶ苦戦した。色々迷走したが、最終的にはキレイなDP遷移が出来た。
DP[i]:=(i文字目で終わるような部分列のパターン数、ただしインデックスの選び方は辞書順最小)とする。ここは普通の部分列DPと同じで良い。
普通の部分列DPであればi+1文字目以降で最前の文字について遷移していくが、1個飛ばしなのでi+2文字目以降で最前とする。これは割と直観的な発想だ。
問題はDP初期化部分で、これにだいぶ迷ったのだが、正解は「DP[-1]=1」とする。もちろん0未満のインデックスは許されないので実装時は適宜ずらす。
仮にDP[0]=1としてしまうとDP[1]に遷移できない。文字列Sが「ab」とかだったとき、「b」はカウントできるが「a」をカウントできない。かといってDP[0]=DP[1]=1などとしてしまうとこれもダメで、Sが「aa」とかだった場合に、先頭のaを取り出した「a」と2文字目のaを取り出した「a」で二重にカウントしてしまう。DP[0]から遷移したものとDP[1]の両方をカウントしてしまうからだ。そこでDP[-1]=1とすれば、-1からなら1にも2にも飛べるため、S=”ab”なら”a”も”b”もカウントできるし、S=”aa”なら同じDP[-1]からの遷移なので二重にカウントする心配はない。2文字目のaは1文字目から最前のaではないためはじくことが出来る。
部分列DPという武器を手に入れられてよかった。まだまだ知らない典型がたくさんあり、黄色への壁を感じる。
散歩をした。凧揚げをしている子供などが見れた。
今日摂取したコンテンツ。
https://ja.wikipedia.org/wiki/銀河団ガス
https://ja.wikipedia.org/wiki/銀河間星
銀河間の空間といえばダークマターくらいしかないんじゃないのというイメージだったが、銀河団全体に高温のガスが満ちているというのは初めて知った。しかも宇宙全体において銀河が占める質量よりも多いときている。面白い。
ちなみに、何がきっかけでこんな話に辿り着いたのか覚えていない。
Categories: 未分類