2つ以上の自然数の集合の積かつ和として表すことのできる数を積和数と呼ぶ。
集合の大きさkに対し、最小の積和数Nを最小積和数と呼ぶ。
2≦k≦12000について最小積和数の集合の和(集合なので重複は除く)を求めよ、という問題。
とりあえず答えは出たもののたっぷり30分はかかった。やはりRは再帰を使うと時間がかかる。かといってほかの方法も思いつかない。フォーラム覗けるようになったのでまた考えようと思う。
Problem 89
ローマ数字を書き直し、文字数をどれだけ減らせるかという問題。
390ms。Problem 88に比べたら全然簡単。
Problem 90
0-9までの数字のうち、互いに異なる6つの数字が6面のそれぞれに書かれた立方体がある。
立方体を2つ用意して数字を上手く選べば、100までの全ての平方数{01, 04, 09, 16, 25, 36, 49, 64, 81}を2つの立方体の一面ずつを使って表すことができる。なお、6と9は回転させることで9または6とみなすことができるものとする。
このとき、全ての立方数を表すことができる立方体の数字の組み合わせは何通りあるか、という問題。
ただ問題のフォーラムでも言われているのだが、問題文がなかなか理解しにくい。問題文を正確に理解できるかが鍵となる。「6と9は回転により変換できる」というところは「6と9は区別しない」とも読めてしまう(例がまるで区別していないかのようなのでなおさら)が、そのようには書いてない。6と9は区別するが、でも9や6としても使えるということ。ややこしい。
とはいえ問題の内容さえ分かれば組み合わせも少ないのでそれほど難しくない。というか考えられる解釈のパターン分試してもどうということはない。4秒。
