AtCoder が提供しているABC（AtCoder Beginner Contest）276 のD問題をC++とPythonで解いてみました。ABC276は、2022年11月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Divide by 2 or 3（Difficulty : 645）
問題はリンク先をご覧ください。
2と3に着目して素因数分解して解きます。AtCoder Problems による Difficulty は、645 でした。
考察と方針
まず、入力例と出力例を整理します。例3までは、問題文に掲載されています。例4以降は、独自に追加したものです。
- 例1）1、4、3 = 1、22、31 となるため、2 + 1 で出力は3になります。
- 例2）2、7、6 = 21、7、2131 となります。7 があるため出力は-1になります。
- 例3）1、1、1、1、1、1 何も操作する必要がないため、出力は0になります。
- 例4）7、14、21 = 7、7×21、7×31 となるため、出力は2になります。-1ではありません。
- 例5）4、4、8 = 22、22、23 となります。出力は、8→4の1になります。こちらも 7（2 + 2 + 3）ではありません。
- 例6）14、28、42 = 7×21、7×22、7×2131 となります。出力は2になります。
最初は、各 ai（$1 \leqq i \leqq N$）に対して、2で割り切る回数と3で割り切る回数を求めて、すべて加えていました。また、2 と 3の以外の素因数が含まれている場合に、-1 としていました。これは例3までは正解となりますが、例4以降を考えると不正解となります。提出して、WA（Wrong Answer）の判定を見て気づきました。
問題を解く方針を書きだします。
- N と数列 ai を読み込む。
- 各 ai を mi × 2pi × 3qi の形に置き換える。
- mi（$1 \leqq i \leqq N$）がすべて一致していなければ -1 を出力して終了する。
- pi（$1 \leqq i \leqq N$）の最小値 minpi をすべての pi から引く。
- qi（$1 \leqq i \leqq N$）の最小値 minqi をすべての qi から引く。
- pi と qi の合計を出力する。
解答案
C++ プログラム例（ABC276D）
ai を mi × 2pi × 3qi の形に置き換える関数 p_n を用意しました。複数の戻り値を返すために、pi と qi はポインタ経由で返しています。関数 p_n の戻り値は mi になります。
mi、pi、qi は、vector としました。方針では、各 pi から最小値を引いていますが、プログラムでは、pi の合計から、pi の最小値 × N を引きました。最小値は、sort して求めました。
以下がプログラムとなります。少し長くなりましたが、記載した方針に従ったプログラムになっています。
#include <bits/stdc++.h>
using namespace std;
int p_n(int n, int *p, int *q)
{
while (n > 1) {
if (n % 2 == 0) {
++(*p);
n /= 2;
} else {
break;
}
}
while (n > 1) {
if (n % 3 == 0) {
++(*q);
n /= 3;
} else {
break;
}
}
return n;
}
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<int> m(n);
vector<int> p(n);
vector<int> q(n);
for (int i = 0; i < n; ++i) {
m[i] = p_n(a[i], &(p[i]), &(q[i]));
}
sort(m.begin(), m.end());
if (m[0] != m[n - 1]) {
cout << -1 << endl;
return 0;
}
sort(p.begin(), p.end());
sort(q.begin(), q.end());
int result = 0;
for (int i = 0; i < n; ++i) {
result += p[i];
}
result -= p[0] * n;
for (int i = 0; i < n; ++i) {
result += q[i];
}
result -= q[0] * n;
cout << result << endl;
return 0;
}このプログラムは、AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC276D）
Python では、関数が複数の値を返すことができます。これにより 関数 p_n のプログラムは、多少見やすくなりました。
p と q はリストで sum と min 関数が適用できます。このため、ソートは行わず、最小値を使って、解答を求めています。
"""AtCoder Beginner Contest 276 D"""
def p_n(n):
p_t = 0
q_t = 0
while n > 1:
if n % 2 == 0:
p_t += 1
n /= 2
else:
break
while n > 1:
if n % 3 == 0:
q_t += 1
n /= 3
else:
break
return n, p_t, q_t
n = int(input())
a = list(map(int, input().split()))
m = []
p = []
q = []
for i in range(n):
m_t, p_t, q_t = p_n(a[i])
m.append(m_t)
p.append(p_t)
q.append(q_t)
m.sort()
if m[0] == m[-1]:
result = 0
result += sum(p) - min(p) * n
result += sum(q) - min(q) * n
else:
result = -1
print(result)こちらも「AC」と判定されました。
最後に
この問題は、問題文を正確に読めていませんでした。そのため、間違った方針でプログラムをして時間がとられました。方針がすっきりと明文化できていないため、コーディングでの細かな間違いも多かったです。
プログラムが長くなる場合（目安としては60－70行を超える場合）は、方針を明確に確立してから、コーディングを始めるほうが、最終的に速く解けることを再認識しました。
AtCoder の問題を解くことは面白く、引き続き ABC を解いていきます。
