2020-11-05

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

AOJ JAG AOJ-ICPC550点数列コーナーケース場合分け競技数学色強め辞書順数学的帰納法に基づく考察パリティ指数の指数 AOJ-ICPC JAG夏合宿

コーナーケースがエグい

問題概要

$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$ 個とする。次のように求められる。

のとき
- $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}$ となる
かつの場合は、
- $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$ とする。

でが奇数のとき
- 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;
}

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

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