読者です 読者をやめる 読者になる 読者になる

はのちゃ爆発

はのちゃが技術ネタとか日常のこととかを書いてます。

AtCoder Beginner Contest 047 参戦記

はじめてのABC。

最後まで解ききれるか…!?と思ったけど、Bで時間を使いすぎて撃沈。 Dも解き方は分かったけど、コーディング時間が残っていなかった…

とりあえずABCなら最後までなんとか出来る、ということが確認できたので、 しばらくABCで精進するつもり。

AtCoderやってると銭湯行くのに時間が微妙になるのが悲しいというどうでもいい感想

C問、他の人の解答を見たらなるほど!というのがあったのでメモ。

C - 一次元リバーシ / 1D Reversi

きつねの次郎と三郎が一次元リバーシで遊んでいます。一次元リバーシでは、盤面には白か黒の石が一列に並んだ状態となっており、列の右端か左端に新たに石を打っていきます。通常のリバーシと同じように、たとえば白の石を打つことで黒の石を挟むと、挟まれた黒の石は白い石に変わります。

ゲームの途中で三郎に急用ができて帰ってしまうことになりました。このとき、盤面の状態は文字列 S で表されます。石は |S| (文字列の長さ) 個並んでおり、左から i (1≦i≦|S|) 個目の石の色は、S の i 文字目が B のとき黒、W のとき白です。

次郎は現在の盤面に対して、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にしようと考えました。最小で何個の石を打てばよいかを求めてください。

私の解答は以下のような感じ。

s = gets.chomp
counts = 0
before_char = s[0]
 
s.each_char do |c|
  counts += 1 unless before_char == c
  before_char = c
end
 
puts counts

146 Byte、25 ms、1916 KB。

これに対し、コード長が著しく短い方々のものは以下のような方法で計算していた。

s = gets.chomp
puts s.squeeze.length-1

squeeze! 並んでいる文字をまとめるメソッドですが、なるほど…!という感じ。

ちなみにこちらは39 Byte、12 ms、2044 KB。 処理時間は半分ですが、メモリ使用量が若干多い…?

以上、はじめてのABC参戦記でした。