けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2295 Power of Power (JAG 夏合宿 2011 day2-F) (550 点)

コーナーケースがエグい

問題概要

 N 個の非負整数  A_{1}, \dots, A_{N} が与えられる。これらの並び替え  B_{1}, \dots, B_{N} であって

 B_{1}^{B_{2}^{B_{3}^{\dots}}}

が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 0^{0} = 1 とする。

制約

  •  1 \le N \le 100
  •  0 \le A_{i} \le 10^{9}

考えたこと

エグい場合分けが大量に発生しそうなので注意したい。たとえば

  •  2^{3} = 8 <  3^{2} = 9
  •  2^{4} = 16 =  4^{2} = 16
  •  2^{5} = 32 >  5^{2} = 25
  •  2^{6} = 64 >  6^{2} = 36
  • ...

みたいなケースもある。とりあえず例外的なものから除外していこう。

0 と 1 のみを含む場合

まずは 0 と 1 のみを含む場合から解いてみる。0 と 1 の乱舞がとにかくヤバそうだからだ。

0 の個数を  N 個、 1 の個数を  M 個とする。次のように求められる。

  •  M = 0 のとき
    •  N が偶数のとき:最終結果は 1 となる
    •  N が奇数のとき:最終結果は 0 となる
  •  M \ge 1 のとき、最終結果は 1 となる ( 1^{0} = 1 というプレイができるので、 0 の個数を疑似的に偶数個にできる)

これらを踏まえて、辞書順最小のものを頑張って求める。 M \ge 1 のケースであっても、かならずしも最初に 1 を持ってくる必要はない。

たとえば  N = 7, M = 3 のとき、次の並びが最適となると思われる。

(0, 0, 0, 0, 0, 0, 1, 0, 1, 1)

つまり、


  •  N が偶数のとき、「0 を最初に全部並べてから 1 を全部並べる」が最適
  •  N が奇数のとき、「0 を  N-1 個並べて、(1, 0) と並べて、残りの 1 を全部並べる」が最適

となる。

0 も 1 も含まない場合

今度は、0 も 1 も含まない場合を解いてみる。比較的やりやすそうだ。一般に

 x^{y} \gt y^{x}

となる条件を解析すると、 f(x) = \frac{\log x}{x}極値 x = e = 2.718... であることから、 x または  y が 2 のケースだけちょっと特殊であることがわかる。

  •  x \gt 3 かつ  y \gt 3 の場合は、 x \lt y のとき  x^{y} \gt y^{x} となる
  •  x = 2 かつ  y \gt 3 の場合は、
    •  y = 3 のときは、 x^{y} \lt y^{x}
    •  y = 4 のときは、 x^{y} = y^{x}
    •  y \ge 5 のときは、 x^{y} \gt y^{x}

以上を踏まえて、次のように解ける (0 と 1 は含まないとする)。


  • 数列を小さい順に並び替える
  • 最後の 2 項が (2, 3) の場合は、そこだけ swap する

一般の場合

以上の考察をマージして、一般の場合を考える。

0 と 1 のみの部分の最適解が 1 のとき

この場合は

(2 以上の並びの最適解)(0, 1 の並びの最適解)

とすれば OK。

0 と 1 のみの部分の最適解が 0 のとき

つまり「1 がなく、0 が奇数個」という場合だ。この場合は、「2 以上の並び」を最適化していても、その末尾が無効化されてしまうことに注意。つまり、

「2 以上の値のうちの 1 個を 1 に変換する操作」

が付け加えられる格好になる。それならば、「2 以上の値のうちの最小値」をその対象とするのが良いだろう (最小以外のものを 1 にすると結果は必ず悪化する)。つまり

(2 以上の値のうち最小のものを除いたものの並びの最適解),
(2 以上の値のうちの最小値),
(0 の並び)

というふうに並べることで最適値が出せることがわかる。しかしそのうちの辞書順最小のものを求めよ、と問われたならばもう少し考える必要がある。たとえば

(4, 4, 5, 7, 3, 0, 0, 0, 0, 0)

という並びに対して、

(4, 4, 5, 7, 0, 0, 0, 0, 3, 0)

としても変わらないことがわかる。(3, 0, 0, 0, 0, 0) も (0, 0, 0, 0, 3, 0) も 1 を導くからだ。つまり、以下のように並べるのが最適となる!

  • (2 以上の値のうち最小のものを除いたものの並びの最適解)
  • 0 を  N-1
  • 2 以上の値のうちの最小値
  • 0

まとめ

場合分けがエグいことになったが、まとめる。0 の個数を  N、1 の個数を  M とする。


  •  M = 0 N が奇数のとき
    • 2 以上の値のうち最小のものを  a とする
    • 2 以上の値のうち  a 以外のものについて、小さい順に並べる
    • 末尾が (2, 3) ならば swap する
    • 0 を  N-1 個並べる
    • 最後に  a, 0 を付け加える
  • それ以外のとき
    • 2 以上の値を小さい順に並べる
    • 末尾が (2, 3) ならば swap する
    •  N 以下の最大の偶数の分、0 を並べる
    • 1 を 1 個並べる (存在しなければ何もしない)
    • 残りの 0 を並べる (存在しなければ何もしない)
    • 残りの 1 を並べる

計算量は  O(N \log N)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    int zero = 0, one = 0;
    deque<int> res;
    for (int i = 0; i < N; ++i) {
        int val; cin >> val;
        if (val == 0) ++zero;
        else if (val == 1) ++one;
        else res.push_back(val);
    }
    sort(res.begin(), res.end());

    auto matsubi = [&](deque<int> &A) {
        int n = (int)A.size();
        if (n >= 2 && A[n-2] == 2 && A[n-1] == 3) swap(A[n-2], A[n-1]);
    };
    if (one == 0 && zero % 2 == 1) {
        int vmin = res[0];
        res.pop_front();
        matsubi(res);
        for (int i = 0; i < zero-1; ++i) res.push_back(0);
        res.push_back(vmin);
        res.push_back(0);
    }
    else {
        matsubi(res);
        for (int i = 0; i < zero/2*2; ++i) res.push_back(0);
        if (one) res.push_back(1);
        if (zero % 2 == 1) res.push_back(0);
        for (int i = 0; i < one-1; ++i) res.push_back(1);
    }
    for (auto v : res) cout << v << endl;
}