【AtCoder:17回目】AtCoder Beginner Contest 139の振り返り(Ruby)
【目次】
【本題】
振り返り
今回は 9/2(日)に開催されたAtCoder Beginner Contest 139の振り返りを行います。
AtCoder Beginner Contest 139 - AtCoder
今回は4問回答出来ました
レーティング微増
A - Tenki
問題文 ある 3 日間の天気予報が、長さ 3 の文字列 S として与えられます。
S の i
( 1 ≤ i ≤ 3 ) 文字目が S のとき、 i 日目の天気予報が晴れだったことを、C のときは曇りだったことを、R のときは雨だったことを意味します。
また 3 日間の実際の天気が、長さ 3 の文字列 T として与えられます。
T の i
( 1 ≤ i ≤ 3 ) 文字目が S のとき、 i 日目の実際の天気が晴れだったことを、C のときは曇りだったことを、R のときは雨だったことを意味します。
3 日間で天気予報が的中した日が何日あるかを出力してください。
制約 S および T は長さ 3 の文字列である。 S および T は S, C, R のみからなる。
一文字づつ比較していくだけですね。
私のコードは以下の通りです。
s = gets.to_s.chomp t = gets.to_s.chomp count = 0 3.times do |i| count += 1 if s[i] == t[i] end puts count
コード長 118 Byte 実行時間 7 ms メモリ 1788 KB
以下の様に、もう少しシンプルにも出来ましたね
s = gets.chomp
t = gets.chomp
p 3.times.select { |i| s[i] == t[i] }.size
コード長 66 Byte 実行時間 7 ms メモリ 1788 KB
B - Power Socket
問題文 高橋くんの家には電源プラグの差込口が 1 口しかありません。
そこで、高橋くんは A 個口の電源タップをいくつか使って未使用の差込口を B 口以上に拡張したいと考えています。
A 個口の電源タップ 1 つと未使用の差込口 1 口を使って、新たに差込口を A 口増やすことができます。
最小でいくつの電源タップが必要でしょうか。
制約 入力は全て整数である。 2 ≤ A ≤ 20 1 ≤ B ≤ 20
タップを追加するという事は、既存の差込口を一つ埋めてしまうという事になります。
なので、タップ追加で増える差込口はn-1
です
その辺りを考慮した提出したコードがこちらです。
a,b = gets.split.map(&:to_i) sum = 1 count = 0 while sum < b do sum += a - 1 count += 1 end puts count
コード長 119 Byte 実行時間 7 ms メモリ 1788 KB
以下の様に、全探索でやらない方法もありましたね
a, b = gets.split.map(&:to_i) puts ((b-1)/(a-1).to_f).ceil
コード長 59 Byte 実行時間 7 ms メモリ 1788 KB
C - Lower
問題文 左右一列に N 個のマスが並んでいます。
左から i 番目のマスの高さは H i です。
あなたは好きなマスに降り立ち、右隣のマスの高さが今居るマスの高さ以下である限り右隣のマスへ移動し続けます。
最大で何回移動できるでしょうか。
制約 入力は全て整数である。 1 ≤ N ≤ 10 5 1 ≤ H i ≤ 10 9
左右を比較して、右隣が低ければカウントし、高ければカウントを配列に格納してリセットするを繰り返すだけですね。
私の提出したコードは以下の通りです。
n = gets.to_i nums = gets.split(' ').map(&:to_i) count = 0 counts = [] (n-1).times do |i| if nums[i] >= nums[i+1] count += 1 else counts << count count = 0 end end counts << count puts counts.max
コード長 234 Byte 実行時間 61 ms メモリ 8964 KB
D - ModSum
問題文 整数 N に対して、 { 1 , 2 , . . . , N } を並べ替えた数列 { P 1 , P 2 , . . . , P N について、 i を P i で割った余りを M i とします。
M 1 + M 2 + ⋯ + M N の最大値を求めてください。
制約 N は 1 ≤ N ≤ 10 9 を満たす整数である。
余りの総和が最大になるパターンを求めるという内容です。
まず個々の余りが最大になるパターンを考えます。
割り算の余りは、割る対象(x)より大きい数(y)で割ると最大になります。
例えば、「3(x)」であれば「4(y)」以上の数字であれば、余りは最大の「3」になります。
yは、xより1だけ大きければ余りは最大になるので、必要以上に大きい数字をあてがわなくとも構いません。
そして、同じ数字では余りは0なので、連番をいくら並び替えても、連番内の最大値で余りを発生させる事は出来ません。
そう考えると、連番は1を末尾に移動させて並び替えるだけで、余りの総和が最大値になります。
#連番 [1, 2, 3, 4, 5] #並び替え後 [2, 3, 4, 5, 1] #個々の余り 1 + 2 + 3 + 4 + 0 #総和 10
1からnまでの連番の総和はn*(n+1)/2
という公式で求めることが出来ます。
連番の最大値nを除いた総和を求めるならn*(n-1)/2
で求めることが出来ます。
そしてn=1の場合は、余りは発生しえないので、答えは0になります。
この考えをもとに提出したコードがこちらです。
n = gets.to_i if n == 1 puts 0 else p n*(n-1)/2 end
D問題にしては、めちゃくちゃシンプルですが、これで通りました・・・いいのかこれ・・・