【ゆっくり解説】プログラミング未経験者にいきなり難問解説: GoTo回文

競技プログラミングというゲームの問題の解説を、小学生でもわかる(?)ただの算数・数学系コンテンツに仕上げてみました。
問題(自作)の初出: codeforces.com/contest/506/pr...
0:00 前座
2:14 第0部
4:44 第1部
9:38 第2部
20:25 第3部
28:05 第4部
33:11 余談
34:49 蛇足
(2023/04/21追加)
Twitterもやってます: / evima0
※2022/09/18追記: タイトルの末尾を変更しました。回文祭り → GoTo回文

[@user-yi8sq3vr4h]

まさかこの文章が回文になるなんて吃驚だろう！でも現にンゲ！モデウロダリクッビ！点なる何、ンブいかが？うょしん部のコカ様～

[@cammelllia]

入力候補にあるタイプの人?

[@over_beginner]

これを見に来た

[@user-pi1zy3ys7l]

現にンゲ！(豹変)

[@nokemoyajuu]

コカ様すき

[@-MAJAGO-]

すげー面白いしわかりやすい
なんでこんなに有名じゃないんだよ

[@zouo-from-Taikonotatsujin]

18:36
ほぼ行列じゃないですかﾔﾀﾞｰ!

[@npsum-tm8ly]

対角化が頭をよぎるッ!

[@catupper-kyopro]

自分用
問題概要 2:15
全部試す 4:50
回文だけ見る 6:10
作れるか判定 7:30
オートマトン 9:40
DPで数え上げ 13:30
遷移行列にする 14:35
繰返し自乗法 16:50
問題特有考察開始 20:26
問題分割 22:35
右 26:40
左 28:11
定数倍 29:45
天才 31:05
FPS 33:13

[@user-pv2rp2jk5c]

1:57
僕はストロベリーよりクリスプチップチョコレートがいいでs(殴

[@tozansoutherpacksredcoder5996]

kitayutaセットで草

[@Kino0000]

理解するためのIQが足りない…

[@user-yz3fz5cn1t]

こんな遅い時期で申し訳ないのですが、29:50でなぜ青い式で大体のステップ数が分かるのですか？そこだけどうしても理解できません。

[@evimalab]

初期文字列長を N、ターン数を T とすると、赤の個数の選択肢が N 通り程度で、そのそれぞれに行列累乗で N^3 log(T) 程度の時間がかかるので、合計で N^4 log(T) 時間程度です。

[@cmplstofB]

こういう話を学びたいんだけど、分野的にはどの辺なんだろう。計算機科学か?

[@Naitoritobe]

28:05 曲の出典が知りたい...

[@evimalab]

MusMus様の「プラスチックアドベンチャー」(musmus.main.jp/music_img2_02.html の一番下) です。

[@Naitoritobe]

@@evimalab ありがとうございます！（コメントが内容と関係なくすみません。内容もとても面白いです）

[@QJRT]

作者は完全に理解してることとこの動画がめちゃくちゃ分かりやすいことは事実
だが俺の脳が理解を拒む……！難しい……！

[@todaetayumenotsuduki]

小学生ではなく中学生ですが理解できました 😁