n-knuu's logs

憧れ駆動。だいたい競プロ

SRM509 div.2 500 LuckyRemainder

div.1 250と同じ問題。

問題

TopCoder Statistics - Problem Statement
あるn桁の数字Xに対してsuper(X)を定義する。
super(X)=(Xからm桁(0 <= m < n)取り除いてできる数字の集合の総和)
例:super(123) = 123 + 12 + 13 + 23 + 1 + 2 + 3 = 177
Xが与えられるので、super(X)を9で割った余りを求めよ。


解法

  • ある数を9で割った余りは各桁を入れ替えても変わらない
  • さらに、ある数を9で割った余りは各桁の総和を9で割った余りに一致する。
  • よってsuper(X)に各桁の値が何回出て来るか考えて、その総和を求めて9で割ればよい。
  • 数字Xがn桁のときにsuper(X)には各桁の値が2^(n-1)回ずつ現れる

感想

数学ゲーだった。と言っても、難しい数学を使っているわけでもなくて、中学受験の小学生でも知ってそうなことだけれども、思いつかなかったから結構面倒臭い解法でやって時間がかかってしまった。
こういう整数に関する素養というか知識があんまりない気がする。大学受験で整数問題が出たら捨てていたのがダメだったのだろう。

圧倒的に面倒な別解法

自分がやった方法。
123でもいいのだけれども、X=1234のときを考えてみる。
各桁がsuper(X)において、一の位から千の位までに何回出て来るか考えてみる。

数字 一の位 十の位 百の位 千の位
4 8
3 4 4
2 2 4 2
1 1 3 3 1

パスカルの三角形を各桁によって2^x(0 <= x < 4)している。
これによって、super(X)を直接出してやることができる。

コード