AtCoder

ABC286 C問題(Rotate and Palindrome)を解く

AtCoder_ABC286_C

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

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

C問題 Rotate and Palindrome(Difficulty : 565)

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

ABC286 C問題 Rotate and Palindrome

問題の設定に従い全検索しました。AtCoder Problems による Difficulty は 565 でした。

解答案

問題を解く方針を書きだします。

  • N、A、B と文字列 S を読み込む。
  • S の後ろに S を加える。これは回転操作の処理を簡素化するためです。
  • 文字列 S に対して、以下を繰り返す。ループ変数は i(0 $\leqq$ i $\leqq$ N – 1)
    • S[i] から始まる長さ N の文字数に対して、回文して一致していない文字数をカウントする。
    • S[i] から始めた場合の、操作の値段を求める。
      ループ変数 i に対して、i × A 円の費用が発生します。回文として一致していない文字数分 B 円の費用が発生します。
  • 一番安い値段を出力する。

C++ プログラム例(ABC286C)

解答の初期値は、最小値を求めるため、非常に大きな値を設定することがあります。今回は、明らかな解(n/2 * b)があるため、その値を初期値としました。

値段の最小値を解答として出力します。以下が C++ プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long int ull;

int main()
{
	int n;
	cin >> n;
	ull a, b;
	cin >> a >> b;
	string s;
	cin >> s;
	s = s + s;

	ull result = (n / 2) * b;
	for (int i = 0; i < n; ++i) {
		ull temp_cost = i * a;
		for (int j = 0; j < n / 2; ++j) {
			if (s[i + j] != s[i + n - 1 - j]) {
				temp_cost += b;
			}
		}
		result = min(result, temp_cost);
	}

	cout << result << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC286C)

上記の C++ プログラムをそのまま移植しました。

"""AtCoder Beginner Contest 286 C"""
n, a, b = map(int, input().split())
s = input()
s += s

result = n // 2 * b
for i in range(n):
    temp_cost = i * a
    for j in range(n // 2):
        if s[i + j] != s[i + n - 1 - j]:
            temp_cost += b
    result = min(result, temp_cost)

print(result)

このプログラムは、Python(3.8.2)では、TLE(Time Limit Exceeded)判定でした。一方、PyPy3(7.3.0)では、AC 判定となりました。

以下は、Python(3.8.2)で AC 判定を受けているプログラムを参考にしました。まず、スライス記法で S をローテーションします。前のプログラムとの差分の背景色を変更しました。

"""AtCoder Beginner Contest 286 C"""
n, a, b = map(int, input().split())
s = input()

result = n // 2 * b
for i in range(n):
    temp_cost = i * a
    for j in range(n // 2):
        if s[j] != s[n - 1 - j]:
            temp_cost += b
    result = min(result, temp_cost)
    s = s[1:] + s[0]

print(result)

このプログラムもまだ Python(3.8.2)で TLE 判定でした。次に一番内側にあるループを関数化しました。引数はすべて渡します。次のプログラムとなります。

"""AtCoder Beginner Contest 286 C"""


def cost_b(s, n, b):
    cost = 0
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            cost += b
    return cost


n, a, b = map(int, input().split())
s = input()

result = n // 2 * b
for i in range(n):
    result = min(result, cost_b(s, n, b) + i * a)
    s = s[1:] + s[0]

print(result)

このプログラムは、Python(3.8.2)でも AC 判定となりました。参考までに関数引数を渡さず、グローバル変数を参照しても AC 判定でしたが、時間はかかる傾向がありました。

なお、関数に切り出す場合も S をスライス記法でローテーションしないプログラムでは、TLE判定を受けていました。

Python については、以下の傾向があると思われます。ただし、わたしは Python に習熟していないため、誤っているかもしれません。

  • リストの添え字の計算は、可能な範囲で簡略化する。
    演算毎に範囲チェックをしている可能性があります。
  • 内側のループは関数化した方が速い場合がある。関数化する場合、グローバル変数の参照ではなく、引数で渡した方が速い傾向がある。

最後に

問題の設定はやや難しいですが、全探索をする問題でした。

(今の私の実力では、)PyPy で提出したほうが無難かもしれません。もう少し習熟して、Python の力を最初から引き出したいです。

ABC286 について、引き続き、D問題まで紹介します。

COMMENT

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

CAPTCHA