脳log[20230614]

2023年06月14日 (水) [AtCoder] 精進。先週の ABC305-G「Banned Substrings」(青 diff)。終了後に４か所で行列累乗というキーワードを見ていた。でも難しい。何×何の行列を用意するのか。その中身は。■提出 #42254964 (AC / 639 Byte / 1622 ms)。まずダメ文字列を表すビット列を１文字から６文字まで DP みたいにして用意した。N が６以下ならこの時点で答えが出せる。次に６文字のダメ文字列を元にして１文字延長を表す 64×64 の行列を作った。ここまでは一歩一歩手探りしながら順調に来たけれど、サンプルの答えが全然合わなくて袋小路に入り込んでしまった。どの部分か。主として 28 行目と 29 行目にあたる部分を延々書き換えながら、なんで掛け算を繰り返すとダメ文字列が答えに現れてくるのか理解に苦しんでいた。私は、行列の掛け算を正しく書くことができません。そこは考えるとことちゃうやん？ ただ定義通りに書くだけよ。■計算量。行列の掛け算は３乗なのかな。64^3≒26万。それに累乗部分が logN≒60。行列の列あたりの非ゼロの数が０か２個なので、ゼロだけの行と列がそれなりにありそうだし、疎らなのをいかした効率化もありそう。でも定数倍の改善なら競プロでは評価されないね。■対角化と Jordan 標準形のキーワードを得た！ 名前だけでもうおなかいっぱいです。ネタもとは『プログラミングのための線形代数』なんだけど、今まさに読んでいる「【第5回】「型」はウェブシステム開発に「エンドゲーム」をもたらすか | GeeklyMedia(ギークリーメディア)」にタイトルが出てきてびっくりしたよ。■最大ケースが 1000000000000000000 0 なのかな。64×64 のうちダメ文字列に対応する行と列を省いたとしても M=0 のケースでは良くならない。それよりも行列のサイズを 32×32 に抑える方が良くなるだろう。32×32 で十分みたいなんだけどわかんない>#42246448。■提出 #42262239 (AC / 769 Byte / 257 ms)。32×32 で足りるというのでとりあえず 32×32 を基本にしてみてダメ文字列の行と列を省いたりもしてみたら１桁早くなった。なんで 64×64 だったり 32×32 だったり行列のサイズがまちまちになるんだろう。１文字分の冗長さはどこから生じてて、なんでお構いなしで答えが合うんだろう。参照する必要のない６文字前を使って入出力を無駄に細かく分類してもそれが理由で間違えるわけではない。なんなら７文字前８文字前まで利用してさらに細分化しても手間が増えるだけで答えが違ってくるわけではない。ということ？