回文探索

2 secs 1024 MB

RIN0SU_1856

問題

提出

テストケース

解説

次の順番で、問題を解いていきます。

$i\neq j$ となる $1$ 以上 $N$ 以下の $i, j$ を選びます。
- $2$ 重ループで、異なる $2$ つの文字列 $S_i$ と $S_j$ を選択します。
$S_i$ と $S_j$ を連結した文字列 $T=S_i+S_j$ を作ります。
- '\0' は文字列の終端を示すため、これを追加して連結した文字列を終わらせます。
$T$ が回文かどうかを判定するために、先頭の文字と末尾の文字から $1$ 文字ずつ一致するか判定します。
- この比較を $\displaystyle\frac{|T|}{2}$ 回だけ行い、どこかで一致しない場合は回文ではないと判定します。

上記の $1,2,3$ を行い $T$ が一度でも回文をあれば Yes、そうでなければ No を出力します。

解答例

解答例 (C)

xxxxxxxxxx
 
#include <stdio.h>
​
int main() {
    int N;
    scanf("%d", &N);
​
    char S[N][101]; // 文字列の長さは適宜調整
    for (int i = 0; i < N; i++) {
        scanf("%s", S[i]);
    }
​
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j) {
                char T[202]; // 連結後の文字列の長さは適宜調整
​
                // 文字列の連結
                int idx = 0;
                for (int k = 0; S[i][k] != '\0'; k++) {
                    T[idx] = S[i][k];
                    idx++;
                }
                for (int k = 0; S[j][k] != '\0'; k++) {
                    T[idx] = S[j][k];
                    idx++;
                }
                T[idx] = '\0';
​
                // 回文判定
                int is_palindrome = 1; // True
                for (int k = 0; k < idx / 2; k++) {
                    if (T[k] != T[idx - k - 1]) {
                        is_palindrome = 0; // False
                        break;
                    }
                }
​
                if (is_palindrome) {
                    printf("Yes\n");
                    return 0;
                }
            }
        }
    }
    printf("No\n"); // 回文が一度も見つからなかった場合、最後に "No" を出力
    return 0;
}

解答例(C++)

xxxxxxxxxx
 
#include <iostream>
#include <string>
#include <vector>
using namespace std;
​
int main() {
    int N;
    cin >> N;
​
    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
​
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j) {
                string T = S[i] + S[j];
                int l = T.size();
​
                // 回文判定
                bool is_palindrome = true;
                for (int k = 0; k < l / 2; k++) {
                    if (T[k] != T[l - k - 1]) {
                        is_palindrome = false;
                        break;
                    }
                }
​
                if (is_palindrome) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

解答例 (Python)

xxxxxxxxxx
 
N = int(input())
S = [input() for _ in range(N)]
​
Flag = False # 回文が見つかったかどうかを管理するフラグ
for i in range(N):
    for j in range(N):
        if i == j: continue
        # 文字列を連結
        T = S[i] + S[j]
        l = len(T)
        # 回文判定
        is_palindrome = True
        for k in range(l // 2):
            if T[k] != T[-k-1]:
                is_palindrome = False
                break
        if is_palindrome:
            Flag = True
            break
if Flag:
    print("Yes")
else:
    print("No")

別解

C++では下記の解答例のように reverse を用いて文字列を反転させることが出来ます。
reverse についての詳細は、公式ドキュメントをご覧ください。

別解の解答例 (C++)

xxxxxxxxxx
 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
​
int main() {
    int N;
    cin >> N;
​
    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S[i];
    }
​
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i != j) {
                string T = S[i] + S[j];
                string T_rev = T;
                reverse(T_rev.begin(), T_rev.end());
​
                if (T == T_rev) {
                    cout << "Yes" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Pythonでは、下記の解答例のようにスライスを用いて文字列を反転させることが出来ます。
スライスについての詳細は、公式ドキュメントをご覧ください。

別解の解答例 (Python)

xxxxxxxxxx
 
N = int(input())
S = [input() for _ in range(N)]
​
Flag = False  # 回文が見つかったかどうかを管理するフラグ
​
for i in range(N):
    for j in range(N):
      if i != j:
            # 文字列を連結
            t = S[i] + S[j]
            if t == t[::-1]: # スライスを用いて、文字列の逆順を取得
                Flag = True
                break
​
if Flag:
    print("Yes")
else:
    print("No")