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^)／

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