6/20に行われたAtCoder Beginner Contest 206（Sponsored by Panasonic）の問題の復習です。
Rubyを学習してきたので、Rubyで回答しています。
始めたばかりでまだまだレーティングが低く、AB問題はだいたい問題なく解け、CD問題は解けたり解けなかったり、EFはほぼ解けないという状態のため、ABCD問題について復習がてら自分の解答をまとめてみました。
A Maxi-Buying (https://atcoder.jp/contests/abc206/tasks/abc206_a)
ABC国の消費税率は8パーセントです。
ABC国にはエナジードリンク屋さんがあります。ここでは、エナジードリンク1本を、税抜きN円で販売しています。
ここに消費税を加算した後の金額は|1.08×N|円となります。
ただし、実数xに対し、|x|はx以下の最大の整数を表します。
この金額が定価の206円より安いなら Yay! 、定価と等しいなら so-so 、定価より高いなら :( と出力して下さい。
Nは整数
入力
N
出力
答え
解答
入力した数値に税率1.08をかけて小数点以下を切り捨てるfloorメソッドを使って数字を整えました。
その結果をもとに条件式でYay!、so-so、:(の3つから出力するものを決める記述を行いました。
N = gets.to_i
sum = (N * 1.08).floor
if sum < 206
puts "Yay!"
elsif sum > 206
puts ":("
else
puts "so-so"
end
B Saving (https://atcoder.jp/contests/abc206/tasks/abc206_b)
シカのAtCoDeerくんは、空の貯金箱を持っています。
AtCoDeerくんは、その貯金箱に、
1日目の朝に1円、2日目の朝に2円…
というように、i日目の朝にi円を貯金箱に入れます。
また、AtCoDeerくんは、毎日夜に貯金箱にいくら入っているかを確認します。
AtCoDeerくんが貯金箱にN円以上入っていることを初めて確認するのは、何日目の夜でしょうか?
入力
N
出力
答え
解答
貯金の合計値がNよりも大きくなるまで貯金をする繰り返し処理を行います。
貯金額がNより大きくなった時に繰り返し処理をした回数が答えになります。
貯金額の合計値をsum、繰り返し処理をした回数をiと定義し、sumがNを超えた時に処理を止め、その時のiを出力する記述にしました。
N = gets.to_i
sum = 0
i = 0
until N <= sum do
i += 1
sum += i
end
puts i
C Swappable (https://atcoder.jp/contests/abc206/tasks/abc206_c)
N個の整数からなる配列A=(A1,A2,...,AN)が与えられるので、
次の条件を全て満たす整数組 (i,j)の数を求めてください。
1≤i<j≤N
Ai≠Aj
入力
N
A1 A2 A3 .... AN
出力
答え
解答
時間制限で不可となった解答
(A1,A2),(A1,A3)...(A1,AN)
(A2,A3),(A2,A4)...(A2,AN)
の組み合わせ全てに対してAi≠Ajを満たす組み合わせをすべて抽出し、その中で同じ組み合わせになっていないものをカウントして出力しようと考えた。
N個の数値があるので、(Ai,Aj)となるときのAi側の数値を1~Nとした時にAjはN-i個分の個数を確認すればよい。
そこでAi側に対してN回繰り返し処理を行わせ、Aj側にはN-i回の繰り返し処理を行わせ、A1~ANすべての値を使った組み合わせる処理を記述した。
その中でAi ≠ Ajとなる組み合わせを配列combiに格納し、その個数を出力することで答えを得ようと考えた。
答え自体は出力例と同じ答えがでるが、処理時間が長すぎて誤りとなってしまった。
N = gets.to_i
array = gets.split.map(&:to_i)
combi = []
N.times do |i|
(N-i).times do |j|
if (array[i] != array[j+i])
combi << [array[i],array[j+i]]
end
end
end
p combi.length
時間制限をクリアできる記述方法
すべての組み合わせの内、条件を満たさない組み合わせを考えて減算することで答えを出す方法
入力した値N個に対して考えられる組み合わせの数はN個から2つの数字を選ぶのでNC2となり、 N*(N-1) / 2 です。
このすべての組み合わせから Ai=Aj となる組み合わせを減算すれば答えになります。
例えば 2,2,3,4,4,4という数値が与えられた場合は
2に対しては2C2つまり1通りがAi = Ajとなります。
3に対してはすべての組み合わせが有効
4に対しては3C2つまり3通りがAi = Ajとなります。
よってこの場合はすべての組み合わせは6この要素から2つの要素を選ぶ組み合わせになるため、6C2ですべての組み合わせが表せます。その中から同じ要素があるものに対してはそれぞれ減算を行うことで答えを得ることができます。
6C2 - 2C2 - 3C2 = (6*5/2*1) - (2*1/2*1) - (3*2/2*1) = 15 - 1 - 3 = 11
よってこの場合の答えは11通りとなります。
この流れを記述します。
入力されたN個の数値をsort!メソッドを使って小さい順に並べ替えます。
数値に絶対に入力されることのない0を小さい順に並べ替えた後に格納します。（処理の上で必要な操作になるので、後述します。）
同じ要素の個数をカウントするためcntを定義します。
後述しますが、並べ替えられた数値を比較するための最初の値としてbefore=0で定義します。
入力されたN個の数値の組み合わせはsumで定義します。
入力されたN個の値を配列arrayに格納します。
beforeに対して同じ数値であればcntを1つ増やします。
beforeとnumが違う場合は違う組み合わせとなるまでカウントしたcntを使って、cnt*(cnt-1)/2の組み合わせ分がAi=Ajとなるため、sumからこの数を減算します。
その後cntは1に戻し、比較するbeforeの数値をnumに置き換えます。
その後はまた同じように処理を繰り返します。
この結果残ったsumの値が問題文の条件を満たす要素の個数となり、この問題の答えとなります。
N = gets.to_i
array = gets.split.map(&:to_i)
array.sort!
array << 0
cnt = 1
before = 0
sum = N * (N-1) / 2
array.each do |num|
if num == before
cnt += 1
else
sum -= cnt * (cnt-1) / 2
cnt = 1
before = num
end
end
puts sum
まとめ
AB問題はすぐに溶けたのですが、C問題は処理の時間制限にかかり不適切な解答となってしまった。
D問題以降は時間が足りず回答できずに終了
Cまでは最低ラインとして回答できるように学習していきます！