全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019：C - Different Strokes

問題

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

考え方

サンプルが自明すぎて、最適なケースがよくわからない。最適化問題(最大化/最小化)では簡単なケースで実験することが重要。

以下の 2 つの料理があるケースを考える。

A_1\ B_1 \\ A_2\ B_2

この時仮にAが 1 の料理を食べたとすると解は A_1 - B_2 となる。2 の料理を食べたとすると解は A_2 - B_1 となる。このときの選び方の差を考えると 1 の料理を食べたほうが良い場合は以下の条件を満たす場合である。

A_1 - B_2 \ge A_2 - B_1

\Leftrightarrow A_1 + B_1 \ge A_2 + B_2

このことを一般化すると料理の食べ方は A_i+B_i が大きい料理から食べていくことが最適である。これはBにとっても同様である。よって元の数列を A_i+B_i の降順にソートして、大きい料理から順に A, B, A, ..., B と食べるように選べば良い。

別の考察ルート

求める値を数式で表現する。「最終的に高橋くんが得る幸福度の総和」を X、「最終的に青木さんが得る幸福度の総和」を Y とすると求める値は Z = X - Y であって、高橋くんは Z を最大化するように選択し、青木さんは Z を最小化するように選ぶ。

\begin{align} \displaystyle Z = X - Y = \sum_{i \in N} A_i - \sum_{j \in N} B_j = \sum_{i \in N} A_i - (\sum_{k=1}^N B_k - \sum_{i \in N} B_i) \\ = \sum_{i \in N} (A_i + B_i) - \sum_{k=1}^N B_k \end{align}

であって、\displaystyle \sum_{k=1}^N B_k は定数であるから結局 Z は \displaystyle \sum_{i \in N} (A_i + B_i) の値のみに依存することが分かる。

よって Z を最大化するときは \displaystyle \sum_{i \in N} (A_i + B_i) が大きい値から高橋くんが選んでいくことが最適であるから、A_i + B_i でソートしたのち、大きい料理から順に選んでいけば良い。

Submission #4111580 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

どこに着目して考察するべきだったか

小さいケースで実験することが重要。サンプルが弱いときは特に。また定式化して一般化するテクもよく見る。

何がバグっていたか

得た知見(典型ポイント)

  • 2つの要素に着目
  • 簡単なケースを定式化
  • 求めたい値を数式で表現して、同値変形で変数を減らす

類題

2 項間の値を定式化して一般化するとよいです。
- F - 天使とふすま

同じ構造です。すでに \displaystyle \sum_{i=1}^N c_i のコストがかかっていたものとして式変形します
- K - パンプキン