hat-tun https://blog.hatena.ne.jp/hat-tun/ hat-tunの日記 https://hat-tun.hatenadiary.org/ アルゴリズム C ある辞書が与えられていて、その辞書の中の単語でしりとりをする時、 しりとりの単語数が一番長くなる時の長さは？？？ という、おもしろい問題あったので、解いてみた。 もちろん「ん」で終わるので、逆から考えるのもアリやとは思うけど、 何で始めようと、最初に「i→あ」の単語で始めたと考えると、1ステップで すべて「あ」スタートの問題に還元できるので、「あ」スタートとして考える。 まず辞書のすべての単語を単語の最初と最後の文字で分類して、それぞれその分類に含まれる数を数える。 例えば「あ」で始まって「い」で終わる単語は「あ」→「い」と表し、これを「あ」から「い」への遷移と呼ぶ。 これを縦軸と横軸に「あ〜… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhat-tun.hatenadiary.org%2Fentry%2F20090211%2F1234323993" title="最長しりとり問題 - hat-tunの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-02-11 12:46:33 rich https://hat-tun.hatenadiary.org/entry/20090211/1234323993 1.0 100%