ARC 相当の企業主催コンテストです。B/C で詰まってしまい、ぎりぎり滑り込んでのC完でした。

diverta 2019 Programming Contest 2

この連載記事では、着手した問題の考察を自分なりに書いていきます。
- 前回: 競プロ参戦記 #50 Sum Equals Xor | ABC 129 - Qiita
問題の詳細は問題一覧を参照してください。
- 問題一覧: https://atcoder.jp/contests/diverta2019-2/tasks

A - Ball Distribution

問題概要: N 個のボールを K 人に配る。どの人にも少なくとも1個のボールを配る。最も多くのボールが配られた人と、最も少ない数のボールが配られた人の、配られたボールの個数の差の最大値を求めよ。

A: 考察

K=1 なら、「最も多くの」と「最も少ない数の」が同じ人になるので、「配られたボールの個数の差」は 0 です。

K≥2 なら、すべての人にボールを1個ずつ配った後、残りを1人に押し付けるのがベストです。このとき個数の差は、1個ずつ配ったボールを除くボールの個数なので、N-K です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/diverta2019-2/submissions/5925143

B - Picking Up

問題概要: 2次元平面上に N 個のボール (点) がある。以下の操作を行うとき、コストの最小値を求めよ。

操作:

2つの整数 p, q を好きに選ぶ。ただし p = q = 0 はダメ。
回収されていないボール (x, y) を1つ選んで回収する。直前に座標 (x-p, y-q) のボールを回収していたのでなければ、コストが1増える。すべてのボールが回収されるまで繰り返す。

制約:

1≤N≤50

B: 考察

(p, q) をどう決めるか、(p, q) を決めたときの最小コストをどう計算するか、という2つの問題があります。

後者から考えます。コストのルールは、以下のように言い換えられます。

ボールを回収するたび、コストが1増える
ボール (x, y) を回収した直後に (x+p, y+q) のボールを回収するたび、コストが1減る

適切な順番でボールを回収するとコストを最小化できます。端のボールから順番に回収すればコストの減少を取り漏らすことはありません。

したがって、ボールを座標でソートして、端から順番に回収し、コストが減少するボールが見つかればそちらを優先して回収する、という手続きで最小のコストを計算できます。

残るは (p, q) をどう選ぶかです。(x, y) と (x+p, y+q) のような位置関係のボールのペアが存在するときのみ、(p, q) は候補になります。というのも、そうでなければコストの減少が全く起こらないので、最小コストは明らかに N-1 だからです。

候補であるボールのペアの差は O(N^2) 通りありますが、N が小さいので、全通り試せます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/diverta2019-2/submissions/5936352

C - Successive Subtraction

問題概要: 長さ N の整数列 A が与えられる。以下の操作を N-1 回行った後、残る唯一の要素の値の最大値を求めよ。また、その最大値を得るための操作手順の一例をあげよ。

操作: 数列から2つの要素 x, y を取り除き、数列に末尾に要素 (x-y) を加える

制約: 2≤N≤ 10^5, |A(i)|≤10^4

C: 考察

大混乱になりました。

誤った考察の例としては (数列の最大値) - (残りの最小値) で最大化できる (できない) とか、少なくとも半分の要素は最終的にマイナスになる (ならない) といった勘違いをしましたが……そのあたりはスルーして考察を整理します。

はじめに気づくのは、最終的な値は Σ±A(i) のような式で表せることです。例えば A = [2, 3, 5, 7] のとき、最後の要素の式は以下のようなものがありえます。

(2-3)-(5-7)
2-(3-(5-7))
5-(7-(3-2))

いずれにせよ展開すると ±2±3±5±7 です。

そのため、最後の要素として「引き算の入れ子になった式」の代わりに「最終的に各 A(i) につく符号」を考えてよいです。

符号の組み合わせとしてどんなものがあるか考えます。直観的に「すべてプラス」と「すべてマイナス」はなさそうです。念のため、これを詳しく確認しましょう。N≥2 なので、最後の要素は A(i) を葉とするツリーで表せます。

    (2 - (5 - 3)) - 7

         (-)
        /   \
     (-)     7
     / \
    2  (-)
      /   \
     5     3

左端の葉ノード (上の例では 2) は最終的にプラスです。一方で、根ノードの右の子ノードの左端の葉ノード (7) は最終的にマイナスです。したがって、「すべてプラス」「すべてマイナス」はありません。

逆に他のパターンはすべて存在します。後述の手順で構築できるからです。

結局、最大値は「負の要素になるべくマイナスをつける (すべてマイナスにはしない)」という戦略で決定できます。

C: 構築

次に構築です。

操作で x, y を取り除くとき、x, y の最後の符号を最初に決めた通りに (例えば、x にプラス、y にマイナスをつくように) 達成するには、どうすればいいでしょうか。そのためには、最後の要素の式を展開したときに x-y の符号がプラスになるか、y-x の符号がマイナスになることが条件です。

これは「最後の要素の式を展開したときにつく符号」(以下、最後の符号)を要素だけでなく、操作で作った式についても考えられるということです。

そこで、「最後の符号がプラスになる要素」の集合と「最後の符号がマイナスになる要素」の集合を用意します。この2つの集合から要素を取り出して x-y か y-x を作って片方の集合に入れる、という操作を繰り返すと、集合がだんだん小さくなるので、問題が解けそうです。

注意点は構築が正しく完了するかどうかです。「最後の符号がマイナス」の要素がなくなった時点で「最後の符号がプラス」の要素がちょうど1つならOK、そうでなければ失敗になります。x-y と y-x のどちらを作るか選ぶ際に、要素数が少ない方の集合に入れられる要素を作る (同じならプラス側の集合に入れる) ことにすればよいです。

こうして構築ができました。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/diverta2019-2/submissions/5933935