Project Euler 93: Arithmetic expressions
2021年初投稿です。最近はProject Eulerを埋めているのでそこの問題から。
問題概要
集合 {1, 2, 3, 4} の各数字をちょうど一度用い, また四則演算 (+, －, *, /) と括弧を使うことにより, 異なる正の整数を作ることができる.
例えば,
8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) － 1
36 = 3 * 4 * (2 + 1)
12 + 34 のように数字をつなげることは許されないことに注意しよう.
集合 {1, 2, 3, 4} を使うと, 36 を最大とする 31 個の異なる数が得られる. 最初の表現できない数に会うまで, 1 から 28 の各数を得ることができる.
最長の連続した正の整数 1 から n の集合を得ることができる, 4 つの異なる数字 a < b < c < d を見つけよ. 答えを文字列 abcd として与えよ.
(http://odz.sakura.ne.jp/projecteuler/?Problem+93から引用)
解法
1~9の数字から異なる数字を選ぶときの組み合わせは通り, 数字の順番は
通り, 数字間に演算子が入るので
通り, 括弧の組み合わせは
通りあるので, 計967680通りあります。
全列挙しても間に合いそうですが, 括弧の処理が少し面倒なので次のような区間dpをします。
区間
において作ることができる数字の集合
(なお, 集合を扱いたいのでc++のsetを使います)
注意点として, 今回の問題では除算が切り捨てではないので分子と分母をもつ有理数のクラスを定義してそのうえで四則演算を行います。
有理数を扱っているので最終的な集合において, 分子が正数, 分母が1であるような数字だけが欲しい数字になります。
数字の組み合わせはもちろんですが, 集合内の数字の順番によっても得られる結果は変わるため, すべての順番において区間dpをして, その結果をもとに連続する数字列の長さを求めます。
以上の処理を全ての数字の組み合わせについて行うことで答えが求まります。
