AtCoder Beginner Contest 055

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

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

A問題

特に言うことなし。問題文そのまま。

n = gets().to_i
puts n*800-n/15*200

B問題

$N!$ を $10^9+7$ で割った余りを求める問題。最後に割ろうとすると数が大きくなりすぎるので良くない。1つ掛けるごとに剰余を出せばよい。

i = gets.to_i
ans = 1
1.upto(i) do |k|
	ans = ans * k % (1000000000+7)
end
puts ans

C問題

書いたコードの量は、前回のC問題(深さ優先探索)に比べて随分少なくなった。頭を使えば書くべきコードを減らせるタイプの問題である。

全数探索：cを組み合わせてSにする回数さえ決まれば最大数は決まる。したがってcをSにする回数に関して、全ての可能性を調べて最大値を取れば良い。しかし、cの個数の最大が$10^{12}$なので、この方法では時間オーバーする。
二分探索：これもダメ。計算量を減らせそうだが、「cをSにする操作」をi回行ったときのSccの個数をf(i)とすると、f(i)は山型の関数になる。したがって最大値を二分探索で求めることは不可能。

正解の解法は以下のようになる。
頭の中で一旦、Sを全て2つのcにバラす。最初にn個のsとm個のcがあったので、全部で(2*m+n)個のcができる。この状態からSccを作るには、4つずつ組にしていってからcを組み合わせてSにすればよい。(※1)
しかし実際には「Sを全て2つのcにバラす操作」はできない。そのため最初にSが多くてcが少ないと、(※1)の数よりも少なくなる。(たとえばSが10個でcが2個の場合、Sccは1組しかできない)その場合はcの数が制約条件になるので、m/2が答え。

n,m = gets.split(" ").map{|v|
	v.to_i
}
 
all = n * 2 + m
if m >= all/4*2 then
	puts all / 4
else
	puts m/2
end

短くしようとすると2行までは縮められる(下記のコードから変数allを削除すれば良い)。ワンライナーでできるかは分からない。しかし……ここまで簡潔に書ける問題がC問題で良いのかなぁ。

n,m = gets.split.map &:to_i
all = n * 2 + m
puts m >= all/4*2 ? all / 4 : m/2

D問題

ある点の動物と両隣の動物がわかれば、その点の解答が分かる。
自身と両隣のうちどれか1つが(羊から狼に/狼から羊に)入れ替わると、回答の○×も入れ替わる。これより、自身と両隣の3匹のうち、羊の匹数の偶奇によって回答が決まる(全員羊なら○なので、羊が奇数なら○、偶数なら×になる)。論理演算子としてはXOR を使えば良い。
1,2番の動物を仮に決めると、2番の発言から3番の動物がきまり、3番の発言から4番の動物がきまり……最後にN番の動物が決まる。最後にN番と1番の発言に合致するかをチェックすれば良い。(実際のコードでは代わりに、1番の動物と2番の動物が最初に仮に決めたものと合致するかを調べている。直前のコードをそのまま利用できるからである。)
仮に決める方法は4通りあるので、全部試してダメだったら-1を出力。

def check(ans, n, s)
	# 2番からn-1番の回答に合致させる
	1.upto(n-2) do |i|
		temp = (ans[i-1] == "S") ^ (ans[i] == "S") ^ (s[i] == "o") 
		ans[i+1] = temp ? "S" : "W"
	end
 
	temp = (ans[n-2] == "S") ^ (ans[n-1] == "S") ^ (s[n-1] == "o")
	ans_zero = temp ? "S" : "W"
 
	temp = (ans[n-1] == "S") ^ (ans[0] == "S") ^ (s[0] == "o")
	ans_one = temp ? "S" : "W"
 
	if ans_zero == ans[0] && ans_one == ans[1] then
		return true
	else
		return false
	end
end
 
 
n = gets.to_i
s = gets.chomp
 
ans = []
ans[0] = "S"
ans[1] = "S"
if check(ans, n, s) 
	puts ans.join
	exit
end
 
ans = []
ans[0] = "S"
ans[1] = "W"
if check(ans, n, s) 
	puts ans.join
	exit
end
 
ans = []
ans[0] = "W"
ans[1] = "S"
if check(ans, n, s) 
	puts ans.join
	exit
end
 
ans = []
ans[0] = "W"
ans[1] = "W"
if check(ans, n, s) 
	puts ans.join
	exit
end
 
puts -1

コードの後半に関しては「ループ使えばスマートに書けそうだけど時間かかるし、いいやベタに書いちゃえ」という方針。
ans = ["W", "S"]みたいに書けば良かったな。

何かいい方法が無いかと調べてみたら、repeated_permutationというメソッドが今回の目的にぴったりだった。重複を許した順列、というと仰々しいが、n個の候補から重複を許してm個並べた、n^m個の全通りの並べ方を返すものである。公式リファレンスも参照。
このメソッドを使うと、このように簡潔に書ける。

["S", "W"].repeated_permutation(2) { |ans|
	if check(ans, n, s)
		puts ans.join
		exit
	end
}
puts -1

以上。レートが1113まで上がったので、上手く行けばもうすぐABCは卒業かな。