AtCoder

ABC285 B問題(Longest Uncommon Prefix)を解く

AtCoder_ABC285_B

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

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

B問題 Longest Uncommon Prefix(Difficulty : 108)

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

ABC285 B問題 Longest Uncommon Prefix

文字列の中で重複している文字を探す問題です。AtCoder Problems による Difficulty は 108 でした。

解答案

問題文に書いてある数式の把握が難しかったです。このような場合は、入力例と出力例を確認しています。この問題については、入力例の計算を確かめて把握ができました。

問題を解く方針を書きだします。問題文では、文字列の添え字を 1 からカウントしていますが、以下では 0 からカウントします。

  • N と文字列 S を読み込む。
  • 1 から N – 1 まで以下を繰り返す。ループ変数を i とする。
    • 0 から以下を繰り返す。ループ変数を j とする。
      • 0 から連続して S[j] と S[i + j] が等しくならない最大の j を求める。
      • j を出力する。
        ※0 から j-1 まで一致していない。つまり、j 個が一致していない。

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

方針に従いプログラムしました。

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

int main()
{
	int n;
	cin >> n;
	string s;
	cin >> s;


	for (int i = 1; i < n; ++i) {
		int result = 0;
		for (int j = 0; i + j < s.length(); ++j) {
			if (s[j] != s[i + j]) {
				++result;
			} else {
				break;
			}
		}
		cout << result << endl;
	}

	return 0;
}

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

Python プログラム例(ABC285B)

Python 版として、C++ のプログラムをそのまま移植しました。

"""AtCoder Beginner Contest 285 B"""
n = int(input())
s = input()
for i in range(1, n):
    result = 0
    for j in range(len(s) - i):
        if s[j] != s[i + j]:
            result += 1
        else:
            break
    print(result)

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

処理時間を改善するため、以下を変更しました。

  • 文字列からリストに変更する。
  • 文字列の長さを毎回求めるのではなく、n を参照する。
  • result のインクリメントを避けるロジックに変更する。

以下が、改善したプログラムです。

"""AtCoder Beginner Contest 285 B"""
n = int(input())
s = list(input())
for i in range(1, n):
    result = n - i
    for j in range(n - i):
        if s[j] == s[i + j]:
            result = j
            break
    print(result)

このプログラムは、PyPy3(7.3.0)と Python(3.8.2)のどちらも AC(Accepted=正しいプログラム)と判定されました。

Python について、まだまだ習熟度が足りないことが分かりました。

最後に

問題文を読んで把握ができず、入力例から理解した問題でした。また、効率(主に時間面)で、Python について、まだまだ理解不足だと感じました。

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

COMMENT

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

CAPTCHA