2016年12月4日のAtCoderの記録。言語はRubyです。
競技プログラミングの感想をQiitaに投げている人ってあまりいない印象なのだけど、投稿して良いのだろうか。
問題はこちら：AtCoder Beginner Contest 048
私の回答一覧はこちら：自分の結果
#A問題
文字列がAtCoder Foobar Contestの形式であることを仮定しなくても良い。
スペース区切りの2番めの1文字目を取ってくれば良いから
ch = gets.split[1][0]
puts "A" + ch + "C"
でおしまい。
#B問題
変数に適切に代入した後
puts b/x - (a-1)/x
とする。
a以上b以下の数のうち、xの倍数の個数
= 1以上b以下の数のうち、xの倍数の個数 - 1以上(a-1)以下の数のうち、xの倍数の個数
= b/x - (a-1)/x
a,bが0である可能性もあるので、その辺を念入りに試験したあと提出。
#C問題
DPかなぁと思って漸化式を立てようとしても上手くいかない。
最初の要素から減らしていくのは明らかに損である。したがって、2番目の要素から減らしていく。2番目の要素が0になっても1番目+2番目が条件を満たさないなら、1番目の要素から減らすしかない。
あとは
2番目+3番目が条件を満たすように、 3番目の要素を減らす
3番目+4番目が条件を満たすように、 4番目の要素を減らす
……と続けていけば良い。
このやり方の最適性はあんまり厳密に考えてないけど、「無駄な減らし方」をしてないから多分大丈夫だろうなぁ、という気分で提出した。
#D問題
5文字や6文字の例をいくつかやってみて「これ……先手と後手がどういう風に操作をしようと、勝者は変わらないのでは……」という気がしてきた。
確証は無かったが、正しそうな気がしたので仮定した。すると「先手と後手は可能な手をテキトウに(=最善を尽くさずに)選択する」と考えて良い。簡単のため、両者は削除できる最初の文字を削除していくということに決めつけて解いた。
str = gets.chomp
c = 0
fl = 0
while true do
0.upto(str.length - 3) do |i|
if str[i] != str[i+2]
str.slice!(i+1)
c += 1
# puts str
break
end
if i == str.length - 3
# 文字を削除できない
fl = 1
break
end
end
break if fl == 1
break if str.length == 2
end
if c % 2 == 0
puts "Second"
else
puts "First"
end
フラグ用の変数flを使わないといけなかったのが、ゴチャゴチャしていて気に入らない。もうちょっと綺麗に書けたような気がする。
デバッグ用のputs strをつけたまま一度提出してしまい、5分ペナルティを喰らった。
解説の動画を見ていたら、「2文字・3文字・4文字……のありえる文字列を全て考える」というやり方をしていた。自分は「サイズの小さい問題を適当に作って考える」ということはしていたが、「サイズの小さい問題を全て列挙して考える」ということはしていなかった。確かにそうやればもっと早く解けたかもしれない。次回以降は気をつけよう。
#配列の合計
C問題で必要になったのだが、咄嗟に書けないからググってしまった。
sum_of_array = array.inject(0){ |sum, i| # (0) はあっても無くても良い
sum + i
}
(もっと短い書き方もあるが、ここでは割愛)
詳細な説明は以下を参照。
ruby の inject をわかりやすく説明してみる
ちょっとわかりにくいけど非常に便利なinjectメソッド
Rubyリファレンス：inject (Enumerable)