脳log[20190130] Problem 158

最終更新: 2019-04-12T22:44+0900

♪ [ProjectEuler] Problem 158

「解けなくて飛ばした問題の中で一番最初の問題」シリーズ。今は Problem 66 なんだけど……解けない。気を取り直してテキトーに興味の持てる問題に取りかかってみたのが Problem 158。Difficulty Rating は Problem 66 が 25 % で、Problem 158 が 55 %。100 % に近い方が難しいっぽい。

#!rubyw
# coding: utf-8

# Classified identity
#
# * p-value.
# * the number of characters that will increment p-value.
# ･ the number of characters that will not increment p-value. (can be calculated)
# ･ length. (counted externally)
# ･ string value and its rightmost character. (no use)

p1, p0 = [0] * 26, [0] * 26
("a".."z").each{|ch|
	p0["z".ord - ch.ord] += 1
}

2.upto(26){|length|
	q1, q0 = [0] * (27 - length), [0] * (27 - length)

	# increment
	p0.each.with_index{|sum, number|
		number.times{|n|
			q1[n] += sum
		}
	}

	# not increment
	p0.each.with_index{|sum, number|
		not_number = 27 - length - number
		not_number.times{|n|
			q0[n + number] += sum
		}
	}
	p1.each.with_index{|sum, number|
		not_number = 27 - length - number
		not_number.times{|n|
			q1[n + number] += sum
		}
	}

	puts "p(%2d) = %12d"%[length, q1.inject(&:+)]
	p1, p0 = q1, q0
}

過去に Problem 191 を解いた経験が生きている。ちなみに Problem 191 の Difficulty Rating は 35 %。