AtCoder

ABC276 D問題(Divide by 2 or 3)を解く

AtCoder_ABC276_D

AtCoder が提供しているABC(AtCoder Beginner Contest)276 のD問題をC++とPythonで解いてみました。ABC276は、2022年11月5日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 Divide by 2 or 3(Difficulty : 645)

問題はリンク先をご覧ください。

ABC276 D問題 Divide by 2 or 3

2と3に着目して素因数分解して解きます。AtCoder Problems による Difficulty は、645 でした。ABC D問題として、やや易しい難易度の問題です。

考察と方針

まず、入力例と出力例を整理します。例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 を解いていきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA