ABC166を復習してみた。

ABC164、ABC165の復習がまだできてないんだけどABC166は簡単めだったので先に復習した。

A. A?C

場合分けして出力するだけ。

s = gets.chomp
puts (s == 'ABC') ? 'ARC' : 'ABC'

B. Trick or Treat

もらったお菓子の数を保持しておいて、最終的に0だった子の数を出すだけ。

n, k = gets.split.map(&:to_i)
count = Array.new(n, 0)
k.times do
  gets  # 使わない
  gets.split.map{|s| s.to_i - 1}.each{|i| count[i] += 1}
end
puts count.select{|i| i == 0}.size

C. Peaks

隣り合ってる展望台よりも高い展望台の数を数えるだけ。
以下のコードでは、隣り合ってる展望台の中で自分の高さ以上の展望台を探し、なければ自分が一番高いとしてる。

n, m = gets.split.map(&:to_i)
heights = gets.split.map(&:to_i)
adj = n.times.map{Array.new}
m.times do
  a, b = gets.split.map{|s| s.to_i - 1}
  adj[a].push b
  adj[b].push a
end

count = 0
n.times do |i|
  height = heights[i]
  higher = adj[i].select{|j| heights[j] >= height}
  count += 1 if higher.empty?
end

puts count

D. I hate Factorization

これが一番難しかった。

自分が考えたのは、と因数分解できるよなということ。
で、（、一般性をなくすことなくとしていい）と因数分解できるとして、 のはずだから（※ここ怪しいまま解いた）、 となるはず。
で、たぶんなのでで（※ここも怪しいまま解いた）、となるにはが正でないとダメ。（※これ間違い、結果的に正を仮定してもOKではあるんだけど）
そこで、を決めればが決まり、その状態でを決めればが決まるので、あとは条件を満たすまでループ。
ここで、を1から順に上げていくんだけどは4乗の項が一番効くはずだからがを超えたら次のループにいく（※これも論理的にかなり怪しい）とした。

コードにすると、以下：

x = gets.to_i

def calc(a, b)
  a**4 + a**3 * b + a**2 * b**2 + a * b**3 + b**4
end

(1..x).each do |k|
  next if x % k != 0
  l = x / k
  (1..l).each do |a|
    break if a**4 > l
    b = a - k
    if calc(a, b) == l
      puts "#{a} #{b}"
      exit(0)
    end
  end
end

論理はめちゃくちゃだったんだけど、運よく通ってしまった。。。

ここからは解説の内容。

まず、という関数を考えると、これは単調増加する関数になってる。
なので、、すなわち、。
ここで、なので、ということが言える。
また、とが離れるほどとも離れるというのがポイント。

そして、もも整数でなので、とが一番近いのはのとき。
このとき、なので、はの関数と考えることができる。
この関数をとすると、と、のときに最小値1をとって、負の方向もしくは正の方向に行くほど値が大きくなっていく。
ここで、なので、これを超えてしまう範囲のは解になりえない。
そして、ちょっとしたループを回して調べると、でを超えることが分かる。
なので、のとき、。

じゃあ、のときはどうかというと、とはのときより離れてるので、ともより離れてることになるから、としたときに、となる。
なので、、となり、やはりを調べれば十分。
についても同様。

で、今はをの関数と考えたけど、の関数と考えても同様の議論ができて、ということが分かる。

あとは、この全部の組み合わせについてを計算して、に一致するものを見つければいい。
それぞれ約240通りだから、回くらいループ回せばOK。

コードは以下：

x = gets.to_i

(-118..119).each do |a|
  (-119..118).each do |b|
    value = a**5 - b**5
    if value == x
      puts "#{a} #{b}"
      exit(0)
    end
  end
end

E. This Message Will Self-Destruct in 5s

最初は普通にループ回してみて、当然のようにTLE。
そこで、アルゴリズムを考え直した。

これは、問題文では身長となってるけど、腕の長さと考えるとイメージしやすいなと思った。
つまり、さんは自分の位置から配列の上下に長さの腕を伸ばしていて、そこで握手することができたら、握手した人と条件を満たすことができる、という感じ。
（もう一人をさんとすると、さんの手の位置は、さんの手の位置はで、これが一致しているのだからとなっていて、となる）

気をつけないといけないのは（というか最初間違えた）、上に伸ばした手同士で握手してもダメで、上に伸ばした手と下に伸ばした手で握手しないといけないということ。
なので、下に伸ばした手の位置と上に伸ばした手の位置は別個に持つ必要がある。

あとは各位置について、上に伸ばした手の数と下に伸ばした手の数の組み合わせだけ、条件を満たす人がいることになるので、それを数えればいい。

コードは以下：

n = gets.to_i
heights = gets.split.map(&:to_i)

low_connector = n.times.map{Array.new}
high_connector = n.times.map{Array.new}

n.times do |i|
  low_connect = i - heights[i]
  high_connect = i + heights[i]
  if low_connect >= 0
    low_connector[low_connect].push i
  end
  if high_connect < n
    high_connector[high_connect].push i
  end
end

count = 0
n.times.each do |i|
  lower = low_connector[i].size
  higher = high_connector[i].size
  count += lower * higher
end

puts count

F. Three Variables Game

ちょっと時間足りなくなって間に合わなかったけど、シンプルな深さ優先探索（DFS）書いたらサクッと通った：

N, A, B, C = gets.split.map(&:to_i)
Commands = N.times.map{gets.chomp}

def dfs(state, hist)
  a, b, c = state
  if (a < 0) or (b < 0) or (c < 0)
    return
  end

  level = hist.size
  if level == N
    puts 'Yes'
    hist.each{|s| puts(s)}
    exit(0)
  end

  command = Commands[level]
  case command
  when 'AB'
    hist.push 'A'
    bfs([a+1, b-1, c], hist)
    hist.pop
    hist.push 'B'
    bfs([a-1, b+1, c], hist)
    hist.pop
  when 'BC'
    hist.push 'B'
    bfs([a, b+1, c-1], hist)
    hist.pop
    hist.push 'C'
    bfs([a, b-1, c+1], hist)
    hist.pop
  when 'AC'
    hist.push 'A'
    bfs([a+1, b, c-1], hist)
    hist.pop
    hist.push 'C'
    bfs([a-1, b, c+1], hist)
    hist.pop
  end
end

dfs([A, B, C], [])
puts 'No'

A, B, Cのいずれかが0未満になったそこから先は調べられないのと、なんでもいいから1つ見つければいいので、かなりタフな例に当たらないと計算量がにならないのかも。
（ツリーを考えると最悪になっててもおかしくないと思う）

今日はここまで！