CodeIQ「『キャリー・オーバー』問題」に参加しました。

CodeIQ「『キャリー・オーバー』問題」の掲載期間が終わったということで、自分の提出コードを公開します。なおほかの方の解答はTogetterにまとめられてます。また解説記事もCodeIQMagazineに掲載される――はずなので、その際はリンクを張りたいと思います。おぼえていたら(´・ω・｀)

3097.rb

n, c = STDIN.gets.split.map(&:to_i)

# ある一桁の足し算に着目したとき、繰り上がりに関する挙動は次の3種類に分類できる。
# type-a : 前桁の繰り上がりに関係なく、繰り上がりが発生する。
# type-b : 前桁が繰り上がったとき、繰り上がりが発生する。
# type-c : 前桁の栗が上がりに関係なく、繰り上がりは発生しない。
# まずはある一桁の計算において、上記のa,b,cに該当する組合せの総数をそれぞれ求める。
types = Hash.new(0)
[*0..9].repeated_permutation(2) do |x, y|
    types[:a] += 1 if x + y > 9
    types[:b] += 1 if x + y == 9
    types[:c] += 1 if x + y < 9
end

# a,b,cを並べて、その並べ方において繰り上がりが発生する回数を記録しておく。
# a,b,cの並べ方は重複順列を利用すると過不足なく求めることができる。
digits = Hash.new{|hash, key| hash[key] = []}
%i(a b c).repeated_permutation(n) do |digit|
    flg = false # 前桁が繰り上がったかどうかを示すフラグ。
    cnt = (0...digit.size).reduce(0) do |sum, i|
        flg = digit[i] == :a || (flg && digit[i] == :b)
        flg ? sum + 1 : sum
    end
    digits[cnt] << digit
end

# 繰り上がりの回数がc回になる、a,b,cの並べ方から求めるF(n, c)を計算する。
ans = digits[c].reduce(0) do |sum, digit|
    a, b, c = %i(a b c).map{|t| digit.count(t)}
    sum + (types[:a] ** a * types[:b] ** b * types[:c] ** c)
end

p ans

3097.py

import itertools, collections

if __name__ == '__main__':
    n, c = map(int, input().split(' '))

    types = collections.defaultdict(int)
    for x, y in itertools.product(range(10), repeat=2):
        if x + y >  9: types['a'] += 1
        if x + y == 9: types['b'] += 1
        if x + y <  9: types['c'] += 1

    digits = collections.defaultdict(list)
    for digit in itertools.product(('a', 'b', 'c'), repeat=n):
        flg = False
        cnt = 0
        for i in range(len(digit)):
            flg = digit[i] == 'a' or (flg and digit[i] == 'b')
            if flg: cnt += 1

        digits[cnt].append(digit)
    
    answer = 0
    for digit in digits[c]:
        a, b, c = (digit.count(symbol) for symbol in ('a', 'b', 'c'))
        answer += types['a'] ** a * types['b'] ** b * types['c'] ** c
    
    print(answer)

提出言語はRubyとPython3――ですが、違う言語なのに見た目がほぼ一緒ですね(´・ω・｀) 同一人物が同一の思想のもとコード書いているので、似通ってくるのは仕方ないといえばその通りかもしれません(言い訳)

詳しい解き方はRubyのソース内コメントを参考にしていただくとして、簡単な感想だけ述べておきます。本問は足し算において繰り上がりの発生回数を求めるというものでした。考えられる整数の組み合わせすべてを求めたあとその総和を求める、つまりは全探索をすると計算量が大きくなりすぎるので、何とか計算量を減らす必要があります。わたしの場合は「繰り上がりのパターン」による場合分けを利用することにより、計算量を減らすことに成功しましたが、漸化式など、より数学的な回答方法もありそうですね。