はじめに

CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。

問題

今回は次のような問題でした。

標準入力からの入力 n に対して、n 桁の 7セグメントディスプレイで表示される数値の内、表示を上下ひっくり返した時により大きな数値になるものが何通りあるか出力する。
ひっくり返す前後で、最上位に0が来ても構わない。また、1 の桁をひっくり返すと厳密には元の 1 とは配置が一致しないが、それも同様に 1 と見做す。

7セグメントディスプレイは、次の図のようになります。なお、ひっくり返す場合パタンと鏡像を作るように返すのではなく、180°回転をします。

ひっくり返した前後で、いずれもちゃんとした数字になるのは、0～9 の内 3,4,7 を除いた 7 種類。なので、$7^n$ 通りの中で条件を満たす数が何通りあるか、です。

しかしながら、ひっくり返した数値のペアを作れば、ひっくり返して小さくなる数値、大きくなる数値が1対1対応します。例外なのはひっくり返しても同じ数値になるもの。なので、{(全体)-(ひっくり返して同じ数値になる個数)}÷2で答えが求められます。

この「ひっくり返して同じ数値になるもの」ですが、n の偶奇によって若干変わります。どういうことかというと、

n が奇数
真ん中の数字は、ひっくり返しても同じになる 0,1,2,5,8 の5種。左半分の桁は7種類の数字が任意に使えるが、右半分の桁は左半分をひっくり返す → $5\cdot 7^{(n-1)/2}$通り
n が偶数
左半分の桁は7種類の数字が任意に使え、右半分は左半分をひっくり返す → $7^{n/2}$通り

ということで提出版のRubyの実装です。まあ、偶奇の違いもまとめて1つの式として表すことができます。

n=eval *$<;p (7**n-5**(n%2)*7**(n/2))/2

対称性に気付けば簡単に解ける問題だったかと思います。