017: 「列車が到着する前に」のヒント

問題 / 解答

難易度: ☆☆☆

ヒント1

0から9までの数字から重複を許して4個を選ぶ組み合わせは、itertools.combinations_with_replacement(range(10), 4) で列挙できます。 組み合わせの個数は715個です。

ヒント2

括弧付きの中置記法を直接作る代わりに、逆ポーランド記法の式を作ります。 逆ポーランド記法なら、括弧を文字列として持たなくても計算順を表せます。

ヒント3

4個の数値と3個の演算子からなる正しい逆ポーランド記法の形は5通りです。 数値を N、演算子を O と書くと、次の5通りです。

• NNONONO
• NNONNOO
• NNNONOO
• NNNOONO
• NNNNOOO

この形に、数字の順列と演算子3個の組み合わせを流し込めば、通常ルールの括弧づけをすべて試せます。

ヒント4

逆ポーランド記法の評価は、前問と同じスタック処理です。 ただし、割り算を正確に扱うため、スタックには fractions.Fraction を積みます。 0で割る式は、その候補だけ失敗として扱います。