RubyでAtCoderに参戦した記録です。
AB2完で、C問題はコンテスト終了後に解説を見てからコードを書きました。もっとC問題解けるようになりたい…！
ABC347 A Divisible
長さNの配列Aと正整数Kが渡されます。配列Aの中からKの倍数のみを全て取り出し、それぞれをKで割ったものを昇順で出力する問題です。
n,k=gets.split(" ").map(&:to_i)
array=gets.split(" ").map(&:to_i).sort
result = array.select{|num| num % k == 0}
puts result.map{|s| s / k}.join(" ")
問題文の通りに実装したという感じですね。
ABC347 B Substring
文字列Sが与えられ、その中に含まれる部分文字列が何種類あるか出力します。
ここでの部分文字列とは、「連続する部分列」、たとえば「yay」という文字列の部分文字列は、「y」「ya」「yay」「a」「ay」の5種類となります。
s = gets.chomp
size = s.size
result = []
for i in (0...size) # 部分列の先頭位置
for j in (1..size-i) # 部分列の末尾位置
result << s.slice(i,j)
end
end
puts result.uniq.size
文字列Sの部分文字列を全て配列resultに集め、最後にuniqで重複を取り除き、種類数を出力しました。
ABC347 C Ideal Holidays
N個の予定がそれぞれ今日から何日後にあるかの配列が与えられます。1週間が休日A日+平日B日からなるとした時、N個の予定全てが休日に重なる可能性はあるかどうかを出力します。
それぞれの予定が、1週間の日数A+B日の内の何日目に当たるかを考えればいいので、まずは「今日から何日後に予定があるか」の配列をA+Bで割った余りで考えるのが良さそう、というところまでは行ったのですが、その後、「では今日が1週間のいつだと仮定するのがいいのか？」「どうやって場合分けしよう…？」と躓いてしまいました。
# 提出コード。WAです。
n,a,b=gets.split(" ").map(&:to_i)
array=gets.split(" ").map(&:to_i)
sum = a + b
result = array.map{|s| s % sum}
# 以下求め方がわからず、とりあえず休日の日数A日と配列の各要素を比較しています。
flag = result.all?{|item| item <= a}
puts flag ? "Yes":"No"
上記コードだと、「今日が1週間の最終日(=1日後が休日A日の始まり)だった場合」しか検討できていないため、テストコード20件でWAが出てしまいました。
そんなわけで、以下解説確認後の解答です。今回はYouTubeの解説動画を参考にさせていただきました。
方針：予定がある日を含めずにB日分取ることができるかを検討する＋1週間を円で考える
たとえば1週間が休日2日、平日5日の７日間で構成されている場合、予定のある日の配列を7日で割った余りの配列の要素は、0~6のいずれかになっており、これは1週間のうちの何日目かを表しています。この問題では、1週間のうちの何日目に予定があるのかということがわかれば良いので、まずはこの配列をsortし重複を除きます。
例）休日2日、平日5日、予定があるのが2,3,9日後の場合：それぞれ1週間のうちの2,3,2日目なので、2,3日目のみ検討すれば良い
あとはその配列の隣同士の要素を比較し、間隔がB日以上空いているところがあれば、問題の条件を満たすことになります。
ただし、1週間は最後の日の次はまた最初の日に戻る=円状になっていることに要注意です。配列の最後の要素と最初の要素の間隔がB日以上の可能性があるからです。
例）上記例の場合、2日目〜3日目の間は0日 < 平日5日だが、3日目〜2日目と考えると、4,5,6,0,1日目が間にあるため条件を満たす
下記のコードでは、この部分を最初に別で検討することにしました。
n,a,b=gets.split(" ").map(&:to_i)
array=gets.split(" ").map(&:to_i)
sum = a + b
result = array.map{|s| s % sum}.sort.uniq
flag = false
if sum - result[-1] + result[0] > b # 週を跨ぐ部分の検証
flag = true
else
for i in (0...result.size-1)
if result[i+1] - result[i] > b # 隣同士の要素の間隔を検証
flag = true
break
end
end
end
puts flag ? "Yes":"No"
おわりに
考えるのは楽しいですが、解けないのは悔しい…！
最近あまり過去問精進できてないので、時間取ってやっていきたいと思います。
参考リンク