結果

問題 No.1816 MUL-DIV Game
ユーザー startcppstartcpp
提出日時 2022-01-22 01:34:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 50 ms / 2,000 ms
コード長 3,837 bytes
コンパイル時間 599 ms
コンパイル使用メモリ 69,504 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-04 19:48:00
合計ジャッジ時間 2,219 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 6 ms
5,376 KB
testcase_10 AC 23 ms
5,376 KB
testcase_11 AC 20 ms
5,376 KB
testcase_12 AC 15 ms
5,376 KB
testcase_13 AC 30 ms
5,376 KB
testcase_14 AC 17 ms
5,376 KB
testcase_15 AC 22 ms
5,376 KB
testcase_16 AC 7 ms
5,376 KB
testcase_17 AC 40 ms
5,376 KB
testcase_18 AC 37 ms
5,376 KB
testcase_19 AC 20 ms
5,376 KB
testcase_20 AC 40 ms
5,376 KB
testcase_21 AC 16 ms
5,376 KB
testcase_22 AC 13 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 50 ms
5,376 KB
testcase_26 AC 49 ms
5,376 KB
testcase_27 AC 48 ms
5,376 KB
testcase_28 AC 48 ms
5,376 KB
testcase_29 AC 48 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n;
int a[100000];

signed main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	sort(a, a + n);
	
	if (n == 1) cout << a[0] << endl;
	if (n == 2) cout << a[0] * a[1] << endl;
	if (n >= 3 && n % 2 == 1) cout << 1 << endl;
	if (n >= 4 && n % 2 == 0) cout << min(a[0] * a[1], a[2]) << endl;
	
	return 0;
}

/*
N = 1 のとき、答えは A_1
N = 2 なら答えは A_1 * A_2
N >= 3 and N:奇数のとき、Bobのターンで常に 1 を作ることで、答えは 1

以降では、N >= 4 and N:偶数のケースを考える。 
また、考察を簡単にするため、A_1 <= A_2 ... <= A_N とする。

## (i) Aliceターンで 1 1 [偶数個] のとき

Bobのターンで必ず 1 [偶数個] の形になり、
[偶数個] >= 2個なら 1 1 [偶数個] でAliceに戻せるので、[偶数個] = 0個なら 1 が答えになる。

##  (ii) Aliceターンで 1 [奇数個] のとき

[奇数個]の部分から 2 つ選んでしまうと、1 [偶数個] かつ Bobターンになるので、同様に 1 になってしまう。よって初手に 1 を必ず選ぶが、このとき [奇数個] の形になる。

Bob が 適当に 1 を作ると、1 [奇数個] のパターンに戻り、これは 最初の [奇数個] の列からちょうど
2つの値が消えたパターンになっている。Bob の戦略を「値のペアを選んで、1 を作ること」に限定したとき、
[奇数個] の列から2つの値を消し続けて、最終的な値を最小化する問題になるので、これは自明にその中で
最小となる A_2 と等しい。

逆に Bobが「あえて大きな値を作るようなムーブ」をしたとしても、A_2 以上の値を作ることができる。

Alice の戦略を
・A_2 未満の値があれば、それともう一方の値を適当に選ぶ
・無ければ、適当に選ぶ
に固定してみる。すると、A_2 以下の値は最初 1 個未満であり、Aliceの操作後には 0 個になる。
次にBobがどう操作しようが A_2 以下の値は再び 1 個未満で Aliceに回る。
最後はAliceが行動して終了するので、A_2 以上の値を維持することができる。

以上の考察より、両者最善を尽くすと A_2 が残る値になる。

## (iii) Aliceターンで A_1 >= 2 のとき

まず、Bob の戦略を「1を作る」に限定した場合を考える。
このとき、最初のBobのターン後に (ii) に帰着される。
初手で Alice がペアを作った直後の数列を B_1, ..., B_{N-1} (昇順）としたとき、B_1 を残すのがBobの最善で、このときの答えも B_1 になるので、B_1 を最大化すればよく、これは min(A_1 * A_2, A_3) になる。
・A_1 と A_2 でペアを作らない場合、B_1 <= A_2
・A_1 と A_2 でペアを作る場合、B_1 = min(A_1 * A_2, A_3)
・後者の方がB_1を大きくできる。

次に、Bobの戦略として「あえて大きな値を作るようなムーブ」を考慮してみる。

Alice の戦略を
・初手は (A_1, A_2) を選択。
・それ以降は
  ・min(A_1 * A_2, A_3) 未満の値があれば、それともう一方の値を適当に選ぶ
  ・無ければ、適当に選ぶ
とする。

まず初手Bobのターンに置いて、min(A_1 * A_2, A_3) 未満の値は 0 個なので、
その次の Aliceのターンでも、1 個未満である。
そのため、次のAliceの行動によって、min(A_1 * A_2, A_3) 未満の値が 0 個の状態でBobに回せる。
あとは同様であり、最後は Alice のターンで終了するので、最終的に残る値は
min(A_1 * A_2, A_3) 以上になる。

よって、両者最善を尽くすと、min(A_1 * A_2, A_3) が残る値になる。
*/
0