CodeIQ：ぎゅうぎゅうシーケンス

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「ぎゅうぎゅうシーケンス」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

【問題】
整数値の並びがあります。
この並びの中で"1", "2", "3"をすべて含む区間のうち、最も小さい区間サイズを調べてください。

たとえば、{3, 4, 2, 6, 5, 1, 3, 3, 2}のような並びの場合、最後の4要素分{1, 3, 3, 2}は、"1", "2", "3"のすべてを含み、かつサイズが最小(4)になっています。

【入力】
1行目に正の整数値の数N(最大5000)、2行目に正の整数値(100より小さい)がN個、半角スペース区切りで書かれています。
また、2行目には"1", "2", "3"のすべてが少なくとも1つずつは含まれています（つまり、区間が必ず見つかるデータになっています）。

【出力】
最小の区間サイズのみ出力してください。

【入出力サンプル】
Input

9
3 4 2 6 5 1 3 3 2

Output

4

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

def search(arr, st)
	flag = [nil, false, false, false]
	flag[arr[st]] = true

	for i in st+1...arr.size
		if (arr[i] == 1) || (arr[i] == 2) || (arr[i] == 3) then
			flag[arr[i]] = true
		end

		if flag == [nil,true,true,true] then return i-st+1 end
	end
	return nil
end

def searchMin(arr)
	ret = []

	for i in 0..arr.size
		if (arr[i] == 1) || (arr[i] == 2) || (arr[i] == 3) then
			ret << search(arr, i)
		end
	end

	return ret.compact.min
end

# main
arr = STDIN.read.split("\n")[1].split.map{|a| a.to_i}
p searchMin(arr)

解説

☆☆☆の問題ですが入力数が少ないので難しくありません。

考え方

何も考えずに総当たりで探します。
任意の場所からスタートして1、2、3が1個ずつ見つかったら最初に見つけた場所から最後に見つかった場所までの数字の数を記録するというのを先頭から順にやればできます。

main

入力値をsearchMin()に渡し、結果を印字して終わります。
数値の個数は使わなくても良いので無視します。

searchMin(arr)

開始位置を1つ、2つめ、…、としながらsearch()関数で1、2、3が登場した場合のその区間の数字の数をチェックします。
開始位置は1、2、3のどれかなのでそれ以外の数値の場合は無視します。
結果はretに配列として保持し、最小値を返します。見つからなかった時はnilが入っているのでArray#compactでnilをのぞいてからArray#minで最小値を選びます。

search(arr, st)

arrの数値配列のst番目から最後までに1、2、3が登場した区間の長さを返します。
変数flagは1、2、3が登場したかどうかをチェックするためのフラグで添え字番号と同じ場所の値がtrueになるとその値が登場したことを表します。
あとは数字を一つずつチェックし、3ことも出現したらそこで長さをチェックしてループを抜けます。
結果として長さを返します。
ちょっとした工夫が見つからなかった時にnilにしていることです（効果はsearchMin()を参照）。

雑感

実力判定問題に同じような問題があった気がします。
テスト結果のページに解答例が示されていてそっちはもっと凝ったやり方をしていました。