komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ TopCoder 問題概要 10桁以下の整数が与えられる。各桁の数字を1増やすか減らすのに1単位のコストがかかる。コストの総和が一定量以下となるようにして11の倍数をたくさん作りたい。このとき、Σ(初期コスト-必要なコスト)を求める問題。 考えたこと 10進数で11の倍数かどうかは偶数桁の和と奇数桁の和の差が11の倍数かどうかで判定できる。これは10≡-1 (mod 11)であることから簡単に示される。 なので偶数桁と奇数桁に分けて考えればよさげ。でもちょっと面倒くさいか？ 偶数桁だけ集めたら、各桁の合計値も必要なコストも高々50以下なのでどうとでもなりそう。 一番素朴にやろうとしたら、dp[i番目まで見た][… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20110826%2F1314289919" title="SRM 372 500pt: RoundOfEleven - 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 2011-08-26 01:31:59 rich https://komiyam.hatenadiary.org/entry/20110826/1314289919 1.0 100%