komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ codechef 問題概要 数字からなる部分列が与えられる。長さ1~4の部分列でdigit rootが9になるものの個数を求める問題。 解法 digit rootが9となることは各桁の和が9の倍数かつ0でないことと同値。なので、長さと和を9で割った余りを状態としてDPすればO(N*5*9)位で求められるがこれだとTLEする。別の方法を考える。4つの数字で和が9の倍数となる組み合わせはそんなに多くないので全部真面目に数え上げればよい。これだと各数字の出現回数を数え上げるだけでよい。 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20120903%2F1346598799" title="Codechef-LUKYDRIV : Lucky Driving - komiyamの日記" 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 2012-09-03 00:13:19 rich https://komiyam.hatenadiary.org/entry/20120903/1346598799 1.0 100%