# D - Maximum Sum of Minimum

# 概要

  • NN頂点からなる木と頂点ごとにラベリングされている整数cic_iが与えられる
  • 各頂点で以下のようにスコアを計算する
    • 各辺に2つの端点に書き込まれた整数の最小値を書き込む
    • 各辺の総和をスコアとする
  • スコアの最大値を求め, その時の整数の書き込み方をもとめよ

# 思考

  • 実験する
  • 整数cic_iの最大値は絶対にスコアに含まれない
    • 2頂点の最小値なので, 最大値はスコアに含まれない
  • 最大値イコールcic_iの合計スコア - cic_iの最大値らしい
  • 後は辺のつなぎ方を確かめる
  • 根に最大値を置いて, 順番にラベリングしてあげれば良さそう
  • 実装
  • WA

30分終了

  • 結果を見ると, sampleも落ちている
  • もう一度ソースコードを見返してみる
  • cout << " "[i==0] << ans[i];という表現を使っている
    • AOJはこれが使えなかった
    • AtCoderも使えないのか......?
  • if文に書き直す
  • AC!

# 気づいたこと・感想

  • AtCoderでもこの構文は使えない......
    • cout << " "[i==0] << ans[i];という表現
  • ちなみにこの構文はアルメリアさんの記事で見かけたもの
  • 構文の意味を知らないので明日本人に聞いてみる
Last Updated: 2019-9-19 14:26:56