LoginSignup
1
1

AtCoder Beginner Contest 347参戦記録(A~C問題)

Posted at

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日間で構成されている場合、予定のある日の配列を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"

おわりに

考えるのは楽しいですが、解けないのは悔しい…!
最近あまり過去問精進できてないので、時間取ってやっていきたいと思います。

参考リンク

1
1
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
1