potetisensei https://blog.hatena.ne.jp/potetisensei/ 生きたい https://potetisensei.hatenablog.com/ 本質的な補題を証明してから解いたら3時間ぐらいかかった。 解説見たらその部分「周期の最小性より」で省略されてたけど、そんな単純に成り立つものだと僕は思えてないんだよね、そんな簡単に証明できる？？？ ということで補題と証明を以下に書きます。 補題 最小周期 の長さ の文字列 を考え、 であるとする。 とする。 この時、 の 最長borderは 。すなわち最小周期は 。 証明 は明らかに のborderであるから、これ以上長いborderがないことを示せば良い。 とおけば、正整数を用いて、 である。 以下、3ケースに場合分けする。 a) として、↑がborderであると仮定する。 に注意すれば、こ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpotetisensei.hatenablog.com%2Fentry%2F2019%2F11%2F30%2F022850" title="AtCoder Regular Contest 077 F. SS - 生きたい" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%5Crequire%7Bcancel%7D Hatena Blog https://hatena.blog 2019-11-30 02:28:50 rich https://potetisensei.hatenablog.com/entry/2019/11/30/022850 1.0 100%