はじめに

昨日は「第3回ドワンゴからの挑戦状」の予選日で参加してきました
自分が解いた解法で説明します

問題A「動画検索」

問題概要

動画の総数,キーワードAを含む動画数,キーワードBを含む動画数が与えられたとき
キーワードA,B両方を含む動画は最低いくつ存在するかを求める

解法

キーワードA以外の部分がキーワードBを含んでいたとするとその差が最低重複分になる

プログラム

questionA.rb

data = gets.split(" ").map{|data| data.to_i}
puts [data[2]+data[1]-data[0],0].max

マイナスにならないように注意する

問題B「ニコニコレベル」

問題概要

数字と"?"からなるの文字列が与えられ
文字列中の最大のニコニコ数(/(25)*/)のサイズを求める

解法

前の文字と今の文字を見る
1. "25"という文字列になればカウンタを1進める
2. 今"?"なら"?"が終わるまで進めその数と"?"の前後に応じた処理をする
3. 不適切な文字が来たら最大かを確認してカウンタをリセットする

2.についてさらに細分化すると
2-1. "?"の左と右でつながりそうでなければ左に接続して最大かを確認してカウンタリセット
2-2. 右に接続
という処理になります
2-1.は「2??2」のように左右が同じ数かつ"?"の数が偶数もしくは,「2?5」のように左右が異なる数かつ"?"の数が奇数のときです
このとき「2?5」と「5?2」では"?"を左につなげたときの「25」の数が違うことに注意してください

プログラム

questionB.rb

data = gets.chomp

prev="x"
count=0
level=0
data.size.times do |i|
  if data[i]=="?"
    next if prev == "?"
    j=i+1
    while data[j]=="?"
      j+=1
    end
    if (data[j] == "5" && prev=="2" && (j-i).odd?) 
      level=[count+1+(j-i)/2,level].max
      count =0
    elsif (data[j] == "2" && prev=="2" && (j-i).even?) ||(data[j] == "5" && prev=="5" && (j-i).even?)|| (data[j] == "2" && prev=="5" && (j-i).odd?)
      level=[count+(j-i)/2,level].max
      count =0

    end
    if data[j] == "5" && prev=="2"
      count+= (j-i)/2 +1
    elsif data[j] == "5" && prev!="2"
      count+= (j-i+1)/2
    elsif data[j] != "5" && prev=="2"
      count+= (j-i+1)/2
    else
      count+= (j-i)/2
    end
  elsif data[i]=="5" && prev=="2"
    count+=1
  elsif (data[i]=="2" && (prev=="5"||prev=="?")) || (data[i]=="5" && prev=="?")
  else
    level=[count,level].max
    count =0
  end
  prev = data[i]
end

puts [count,level].max*2

プログラム上では各文字でループして"?"がでたら一気に読み飛ばして前後を確認しています
そのため前の字が"?"だったら無視しています

問題C「スキーリフトの相乗り」

問題概要

1~4の数字が与えられて
4個1セットに組んでいく,このとき数字を分解することはできない
最小のセット数を求める

解法

上から貪欲法で詰めていく
1. 4は最大なので1組1セット
2. 3は1席空いているので1と一緒に1セットにしていく,1人組不足で空席になるのは気にしない(残りは2人組しかいなので)
3. 2を2組で1セットにしていく,余った2人は1人を2組持ってきて1セットにする
4. 以上の処理をして1人が余ったら4人で1セットにしていく

プログラム

questionC.rb

n=gets.to_i

data=[0,0,0,0]
n.times do
  data[gets.to_i-1] +=1
end


#4
count=data[3] 

#3
if data[0] >= data[2]
  data[0] -= data[2]
  count += data[2]
else
  data[0]=0
  count += data[2]
end

#2
count += data[1]/2

if data[1]%2==1
  count +=1
  data[0]-=2
end

#1
if data[0] >0
  count += (data[0]+3)/4
end

puts count

問題D「ネタだけ食べたい寿司」

問題概要

2つの値がN回与えられて好きな方を選ぶことができる
左の数(>右の数)をM回選ぶとそれより下は右の値も選べなくなる
選んだ値の和が最大となる値を求める

解法

場合分けする
1. MがN以上の場合
全部左を選ぶ
2. それ以外
M-1回であればどの値でも左を選べるので,左の値と右の値の差分が多いものを選ぶ
最後の1回は最後にとったと仮定して最大値を更新
最後の1回をひとつずつ戻していく
M-1回で選んだところまで来たら,最終地点がそこになるのでM番目に差分が大きいものをとればよい

プログラム

questionD.rb

n=gets.split(" ").map{|d| d.to_i}

diff=[]
diff2=[]
data=[]

n[0].times do |i|
  data << gets.split(" ").map{|d| d.to_i}
  diff << data[i][0] - data[i][1]
  diff2 << [data[i][0]-data[i][1],i]
end

max=0

if n[0]<=n[1]
  data.each do |d|
    max+=d[0]
  end
else
  data.each do |d|
    max+=d[1]
  end
  diff2.sort_by!{|d| d[0]}

  maxi=[0]
  (n[1]-1).times do |i|
    maxi << diff2[-1-i][1]
    max += diff2[-1-i][0]
  end

  maxi.sort!
  if maxi[-1] == (n[0]-1)
    max+=diff2[-1-(n[1]-1)][0]
  else
    maxbuf = max + diff[-1]
    max=[maxbuf,max].max
    i=(n[0]-2)
    until maxi[-1]==i
      maxbuf+=diff[i]
      maxbuf-=data[i+1][0]
      max=[maxbuf,max].max
      i-=1
    end
    maxbuf+=diff2[-(n[1])][0]
    maxbuf-=data[maxi[-1]+1][0]
    max=[maxbuf,max].max
  end
end
puts max

問題E「偶奇飴分け」

問題概要

0からN-1まで皿があり,1からNの皿に飴がある
全ての飴を左か右の隣に一斉に移動し飴のない皿を除いた左から奇数番目の飴の総和の最大値を求める
また,Q個のケースがあり,それぞれ与えられた飴玉の数を一つの皿だけ変更する
ケース全てにおいて最大値を出力しなければならない

解説はできればしたかった

実は今も解法がわかってません
ケース数Qに対して
部分点条件はQ=1なので総当たりでいけそうですが
皿の個数N,ケース数Qに対して
1≦N≦5×10^4,Q=5×10^4にも5.252sで答えないといけないので
ちゃんとしたスマートな解法がありそうです
- 初期位置の偶数場所と奇数場所を混ぜることはできない
- 左端と右端は必ずとれる
- 左右右や右右左に移動すれば0の皿を作り出せる
ってことは全て右に動かすようにしといて一部左に動かせばその地点で0を作ることによって奇数列と偶数列好きな方をとれるって点がかなりヒントになりそうです
まだ混乱しているので,明日辺り考え直してみます

反省

やってみた感じ過去回よりも簡単な感じはしましたが
結果は時間内にAとCしか解けないという散々な結果に終わりました
Dに至っては解法はすぐに思いついたのですが配列の最大数や配列をマイナスから回したりと
いろいろ混乱して解くのに3時間以上かかりました(制限時間は2時間)
Rubyもまだまだ使いこなせてませんね...
まだまだクソザコプログラマなのでもっと精進したいと思います
あと問題はしっかり読もう!(Bは必死に総和を求めていました...)