#733367 (C++14) No.1816 MUL-DIV Game

提出ソース

結果

問題	No.1816 MUL-DIV Game
ユーザー	startcpp
提出日時	2022-01-22 01:43:03
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	44 ms / 2,000 ms
コード長	4,105 bytes
コンパイル時間	1,376 ms
コンパイル使用メモリ	69,248 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-04 19:59:16
合計ジャッジ時間	2,011 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	1 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	9 ms 5,376 KB
testcase_10	AC	19 ms 5,376 KB
testcase_11	AC	17 ms 5,376 KB
testcase_12	AC	13 ms 5,376 KB
testcase_13	AC	26 ms 5,376 KB
testcase_14	AC	15 ms 5,376 KB
testcase_15	AC	20 ms 5,376 KB
testcase_16	AC	7 ms 5,376 KB
testcase_17	AC	36 ms 5,376 KB
testcase_18	AC	33 ms 5,376 KB
testcase_19	AC	18 ms 5,376 KB
testcase_20	AC	37 ms 5,376 KB
testcase_21	AC	14 ms 5,376 KB
testcase_22	AC	12 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	42 ms 5,376 KB
testcase_26	AC	42 ms 5,376 KB
testcase_27	AC	42 ms 5,376 KB
testcase_28	AC	42 ms 5,376 KB
testcase_29	AC	44 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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) が残る値になる。


(i) のとき A_1 = A_2 = 1 で 答え 1
(ii) のとき A_1 = 1 で 答え A_2
だが、min(A_1 * A_2, A_3) はこの2ケースも網羅するので、N >= 4, N:偶数 のときの答えは全てこれになる。

*/

yukicoder

結果

テストケース

ソースコード