問題
このゲームは 2 人のプレイヤーの間で行なわれます。
ゲームには、表裏がそれぞれ黒と白に塗られたコインと、1 × N の横に長いボードを使います。
便宜上、黒い面を向いているコインを黒コイン、白い面を向いているコインを白コインと呼ぶことにしましょう。
ゲームは次の手順で進みます。
・手順
1. 親番のプレイヤーが、ボードのすべてのマスにコインを無作為に並べます。この状態からゲームスタートです。
2. ボードに次の操作を施したあと、「黒コインがいくつあるか」を先に答えられたプレイヤーの勝利となります。
・操作
「黒コインで挟まれている1つもしくは連続した白コイン」および「白コインで挟まれている1つもしくは連続した黒コイン」を一斉に反転させる。反転するコインがなくなるまでこの操作を繰り返す。
次の図は上記の操作によってコインが反転していく様子を表したものです。
このゲームにすっかりはまってしまったあなたは、自主練習のために黒コインの個数を計算するプログラムを作ることにしました。
コインの並びが与えられたときに、操作を施したあとで黒コインがいくつあるかを計算するプログラムを書いてください。
入力
入力は以下のフォーマットで与えられます。
N
s
・1 行目には、ボードの横の長さを表す整数 N が入力されます。
・2 行目には、ゲーム開始時のコインの並びを表す文字列 s が与えられます。これは "b" と "w" のみからなる長さ N の文字列です。
・s の i 文字目 (1 ≦ i ≦ N) が "b" のとき、ボードの左端から i マス目は黒コインとなります。
・s の i 文字目 (1 ≦ i ≦ N) が "w" のとき、ボードの左端から i マス目は白コインとなります。
出力
表の数を出力
回答コード(100点 Bに昇格)
num = gets.to_i
game = gets.chomp.split("")
@omote = "b"
@ura = "w"
def turn(game , first_c, last_c , start , last)#コインの配列、先頭(表か裏)、ケツ(先頭が表なら裏、またその逆)、反転の先頭、ケツ
return if start > last #反転すべて反転したら終了
start.upto(last) do |coin|
if game[coin] == @omote #表なら裏に
game[coin] = @ura
else #裏なら表に
game[coin] = @omote
end
end
start=game.index(last_c)
last =game.rindex(first_c)
turn(game , first_c, last_c, start , last)
end
if game[0]==@ura && game[num-1]==@ura #1文字目と最後の文字がwなら全部wになるので
puts 0
elsif game[0]==@omote && game[num-1]==@omote #bなら全部bなので
puts num
else
if game[0] == @ura #一文字目がwなら最初のbのインデックから反転させていく
start = game.index(@omote)
last = game.rindex(@ura)
turn(game , @ura , @omote, start , last)
puts game.select{|c| c==@omote}.size
else #一文字目がbなら最初のwのインデックスから反転させていく
start = game.index(@ura)
last = game.rindex(@omote)
turn(game , @omote , @ura, start , last)
puts game.select{|c| c==@omote}.size
end
end
解説
問題にとりかかる前に自分でいくつかシュミレーションをしたところ
「最初と最後が同じ面なら全てのコインがそちらの面になる」
とたまたまきづくことができた(たまたまではなく実力が付いてきたから気づけたのか!?なんて。)
if分岐で上の条件でわけて簡単な出力になるものと、
そうでないものとしてから、ここに適応する関数をくみたてていった。
この問題は端っこからオモテ、もしくはウラが決定されていくものと判断が思いのほかパッと判断できたので、決定された部分いじる事の無いような(余計な処理が行われないような)仕組みを考えて再帰呼び出しで書き出してみた。
インスタンス変数を用いてうまい事処理が出来てるのではないかと思うけどもう少し無駄が省けそう。
Bランク昇格記念の問題なので別にいいか。