AtCoder が提供しているABC（AtCoder Beginner Contest）368 F問題をC++とPythonで解いてみました。ABC368は、2024年8月24日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
F問題 Dividing Game（Difficulty : 1180）
問題の詳細は、リンク先をご覧ください。
複数の石の山から、特定の山の任意個の石を取る石取りゲームに帰着できます。AtCoder Problems による Difficulty は 1180 でした。
解答案
前日の記事で石取りゲームについて解説しました。この考え方が適用できます。
この問題文に以下の記述があります。
$A_i$ の正の約数であって $A_i$ 自身でないものを自由に選び $x$ とし、 $A_i$ を $x$ で置き換える。
この操作は、$A_i$ から任意個の素因数を取り除くと考えることができます。すべての素因数を取り除くと $x=1$ となり、これ以上の約数を選ぶことができない＝石がなくなることに等しくなります。
ゲームの構造が同じであるため、石取りゲームの結論を使うことができます。
石の山 $A_i$ の XOR（排他的論理和）が0以外であれば先手必勝、
0であれば後手必勝となる。
この問題では、与えられた数の素因数の数が石の数に相当します。
C++ プログラム例（ABC368F）
素因数分解する関数 prime_factor を修正して、素因数を返すように変更しました（6ー21行目）。
後は、素因数の数の XOR を計算して、0以外なら、”Anna” を、0なら “Bruno” を出力します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
int prime_factor(ull n)
{
int result = 0;
for (ull i = 2; i * i <= n; ++i) {
while (n % i == 0) {
++result;
n /= i;
}
}
if (n != 1) {
++result;
}
return result;
}
int main()
{
int n;
cin >> n;
vector<ull> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int result = 0;
for (int i = 0; i < n; ++i) {
result ^= prime_factor(a[i]);
}
if (result != 0) {
cout << "Anna" << endl;
} else {
cout << "Bruno" << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC368F）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 368 F"""
def prime_factor(n):
result = 0
i = 2
while i * i <= n:
while n % i == 0:
result += 1
n //= i
i += 1
if n != 1:
result += 1
return result
n = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(n):
result ^= prime_factor(a[i])
print("Anna" if result != 0 else "Bruno")こちらも「AC」と判定されました。
最後に
コンテスト中は、素数と合成数の個数に注目していました。例えば、すべて素数で個数が偶数であれば後手必勝、奇数であれば先手必勝であることは分かりました。コンテスト後ですが、石取りゲームに帰着できることが分かり解くことができました。
F問題としては珍しく緑Diffでした。前回、F問題で緑Diffだったのは、ABC185F問題（解説記事）でした。この問題は、セグメント木を使うだけの問題でした。この問題も典型度合いが高い問題であると思われます。
引き続き ABC の問題を紹介していきます。
