「今週のお題：点灯している量で考えるデジタル時計」問題解答 ( CodeIQ )
はじめに
CodeIQという所で週次で出題される「今週のお題」シリーズに解答しましたので、ネタバレです。
問題
デジタル時計 ( 24h制 ) は、各桁が数個のLEDのON/OFFで表示が制御されています。ここで、「合計n箇所のLEDが表示される時刻は?」を考え、時刻が何通りあるか、その場合の数を出力する、という問題でした。
なお、問題文には明記されていませんが、10の位が0の場合、「LEDが全てOFF」ではなく「0に対応したLEDがON」としていたようです。すなわち、例えば午前1時ちょうどの場合、“ 1: 0: 0”や“ 1:00:00”ではなく“01:00:00”に対応するLEDがONになる、ということです。
ケースは控えていないので忘れましたが、n=27に対して答えが8800となることは問題文に載っています。
解答
今回はPerlで実装しました。…特にGolfもしてないです。
解説
特に変なこともしていないので、提出版のコメントから。
概要
予め、点灯箇所の数に応じて、何種類の数値がありうるかを整理します。
例えば、一番右の桁で、2箇所点灯なら 1 の1種類のみ、5箇所点灯なら 2,3,5 の3種類といった具合に。
桁・点灯箇所数毎にループ ( 実装上は再帰 ) を行い、何通りあるか累積していきます。
計算に先だって、どの数字が何か所点灯するか ( リスト@L ) を元に、時の2桁 ( 変則的なまとめて )、分・秒の上位桁 ( 0～5 )、下位桁 ( 0～9 ) 別に、点灯箇所の数と数値の種類数の対応をリストとして整理します。
但し、最低の点灯箇所数以前は削っておきます。
後は、点灯箇所数と桁情報を補助関数f_supに渡して計算します。
点灯箇所数についても、最低の点灯箇所数分は間引いておきます。
終わりに
手抜きですがまあ。
コード、記事に直に埋め込むのとideoneを参照する ( こっちも埋め込みだけど ) のとどっちがいいかな…。今回は長いから参照という形にしましたが。
