ABC298 F問題 Rook Score

atcoder.jp

巨大なマス目から、(R,C) を選び、R行 または C列 のマス目の総和の問題です。
あらかじめ、各行の総和と各列の総和を計算しておくと、問題の値は、

と求められます。
ほとんどのマス目は 0 であることから、0以外の値のある行と列のみをリストアップします。
行・列を総和が大きい順に並び変えて、 の最大値を求めていきます。
列方向に探索するときに、 の値がそれまでの最大値以下であれば、それ以降の列は調べる必要が無くスキップすることができます。
また、(R,C)マスの値をすぐに取り出せるように、(R,C)をキーとする辞書型としておきます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()

  A = Dict()
  row = Dict()
  col = Dict()

  for k = 1:N
    r,c,x = readInts()
    A[ [r c] ] = x

    # r 行の和
    y = 0
    if haskey(row,r)
      y = row[r]
    end
    row[r] = x + y

    # c 列の和
    y = 0
    if haskey(col,c)
      y = col[c]
    end
    col[c] = x + y
  end

  nrow = length(row)
  ncol = length(col)

  # 和が大きい順に並び替え
  rows = sort(collect(row), by=x -> x[2], rev=true)
  cols = sort(collect(col), by=x -> x[2], rev=true)

  ans = 0

  for i = 1:nrow
    for j = 1: ncol
      v = rows[i].second + cols[j].second
      if ans >= v
        break
      end
      r = rows[i].first
      c = cols[j].first
      if haskey(A, [r c])
        v -= A[ [r c] ]
      end
      if v > ans
        ans = v
      end
    end
  end

  println(ans)

end  # function solve

# main
solve()