AtCoder Beginner Contest 054

2017年2月11日のAtCoderの記録。言語はRubyです。

問題はこちら：AtCoder Beginner Contest 054
私の回答一覧はこちら：自分の結果

問題開始前に寝落ちしてしまい、寝ぼけ眼でのスタートとなった。

A問題

1を14に変換したあと大小比較。

B問題

単純に1つずつ見ていっても計算量はたかだか50^4なので、時間は間に合うだろうと判断できた。

n,m = gets.split(" ").map{|v|
	v.to_i
}
 
pic = []
n.times do
	pic << gets.chomp
end
template = []
m.times do
	template << gets.chomp
end
 
fl =0
for i in 0..n-m
	for j in 0..n-m
		# picの[i,j]成分を左上隅とした部分が、templateと一致するか
		fl = 0
		for k in 0 .. m-1
			if pic[i+k][j..j+m-1] != template[k]
				fl = 1
				break
			end
		end
		if fl == 0 then
			puts "Yes"
			
			exit
		end
	end
end
puts "No"

最初に書いたときは変数flを導入するのを忘れていて、どんな場合でもputs "Yes"が実行されるように書いてしまった。

このフラグの使い方はあんまりスマートじゃないから、使わずに切り抜けられないかと思って他の人の解答を見てみたけど、使わざるを得ないようだ。
なお、1回のマッチング部分を別の関数に切り出せば、フラグを使わなくとも書ける。参考：他の人の結果

C問題

深さ優先探索。再帰的に関数を呼び出す。
頂点の数は最高8とずいぶん少ない。だから以前の回答のようにスタックを使いすぎて失敗することもないだろう。と踏んで書いた。

問題内のテストケースは通ったのに不正解になること2回、正解になった。
1回目は始点の指定ミス。問題文中の頂点は1から始まるが、プログラム中では全て0からに直していた。始点(頂点1)を呼ぶときは0なのに、間違って1を引数に入れてしまった。グラフ系の問題はこの添え字を1間違えるミスをしやすいので、書くときは気をつける。
2回目は辺の情報を読むときに、辺の数はmなのでm回読み込むのが正解なのに、間違ってn回にしていた(頂点の個数)。
とはいえ、この手の「問題内のテストケースは通ったのに不正解」ってどうやって回避するのが良いんだろう。自分でテストケースを作るとか？

n,m = gets.split(" ").map{|v|
	v.to_i
}
 
$nbr = []
for i in 0..n-1
	$nbr[i] = []
end
 
# 接続関係を配列に直す
m.times do
	a,b = gets.split(" ").map{|v|
		v.to_i
	}
	$nbr[a-1] << b-1
	$nbr[b-1] << a-1
end
 
def CountPath(cur, prevs, n)	
	if prevs.length == n-1
		return 1
	end
 
	sum = 0
	for v in $nbr[cur]
#		if v is not in prevs
		if !(prevs.include?(v))
			prevs << cur
			sum = sum + CountPath(v, prevs, n)
			prevs.delete_at(-1)
 
		end
	end
	
	return sum
end
 
if $nbr[0].length == 0
	# 頂点1からの辺がない
	puts 0
	exit
end
 
puts CountPath(0, [], n)