Akihito Ikeda

diverta 2019 Programming Contest 2

posts/2019-06-16diary

diverta 2019 Programming Contest 2

出場できませんでした。ので、後からやりました。けど、2問しかやりませんでした。

ちなみにこれは前回ジャッジトラブルでunratedになったdiverta 2019 Programming Contestのやり直しコンテストのようです。

A - Ball Distribution

特定の1人に多く配って、残りの人には1個ずつ配ればよさそう!
ただし1人のときは0(ってサンプルが親切に教えてくれる)。

n, k = gets.strip.split.map(&:to_i)

if k == 1
    puts 0
else
    puts n - k
end

↑こういうのもっといい感じに書きたいですね。
三項演算子でputs k == 1 ? 0 : n - kとかかな〜?
でもこのままがいいのかな、シンプルなことはシンプルに書いたほうが。

B - Picking Up

思考の流れをメモっていたのでそれを書きます。

  • まず最大コストはN
  • そこからいい感じにp, qを選んでどれだけコストを減らせるか?
  • 少なくとも、最初の点から適当に次の点を選んで、その(dx, dy)を(p, q)とすれば 必ず1はコストを減らすことができる
  • 全ての点について、お互いの(dx, dy)を調べ、もっとも多い組を(p, q)とすればよい?
  • 3点あったとき、上から回収するのと下から回収するのは同じなので(dx, dy)の正負は関係ない
  • じゃあ絶対値をとれば良い
  • って絶対値とったらダメじゃん!
  • (1, 1)と(-1, -1)は同じ(逆向き)だけど、(1, -1)は違うじゃん!
  • アホすぎる
  • 最大のN = 50の場合でも、全ての点の(dx, dy)の組み合わせは 50C2 = 1225通りなので余裕で間に合う
  • O(n^2)?
  • N = 1の時に気をつける
n = gets.strip.to_i
xys = n.times.map { gets.strip.split.map(&:to_i) }

if n == 1
    puts 1
else
    dxdy = []
    xys.combination(2).to_a.map do |c|
        p1, p2 = c
        dx = p1[0] - p2[0]
        dy = p1[1] - p2[1]

        dxdy.push [dx, dy]
        dxdy.push [-dx, -dy]
    end

    count = dxdy.group_by(&:itself).map { |k, v| [v.size, k] }.max_by(&:first)[0]
    puts n - count
end

実装的には、

dxdy.group_by(&:itself).map { |k, v| [v.size, k] }.max_by(&:first)[0]

ここがちょっと苦しい感じがする。

[[1, 1], [1, 2], [2, 1], [1, 1]]

こういう配列の最頻値の個数を欲しがっているところ。
この場合だと、[1, 1]が2回出てくるので2が欲しい。
もっといい感じに書けないかな〜?

C以降

ノータッチ\(^o^)/

最近解ける問題しか解いてないのでやばい

© Akihito Ikeda - Last update 26.11.2020 00:01.