[Baekjoon] 10942. ファリンドロン?[G3]

📚 質問する

https://www.acmicpc.net/problem/10942
数列の大きさは2000、質問数は100万個です.したがって,パリンドロンかどうかを判断し,それを2次元配列に置き,問題の答えを出力すればよい.
ファリン症候群かどうかを素早く確認する方法は?
私が考えている方法はmid値を確定し、左右に拡張し、ファリン症候群かどうかを判断することです.
真ん中がパリンドロンでなければ、退出します.
単数と偶数を分けて考えることができます.
まず、奇数であれば、図を描くことができます.

midは、すべての最初のインデックスを終了インデックスにチェックして検索する必要があります.
上図はmid街2時です.(最初のインデックスは0と呼ばれます)
入力した配列をarrと呼ぶ場合、arr[s]とarr[e]が同じ場合、その配列に1を入れます.
ファリンドロンを蒼白球に並べ、pallin[s][e]に1を入れればよい.
中間のarr[s]とarr[e]が異なるとmidを中心にパリン症候群が再発しないため終了する.また、sまたはeが1つの配列のサイズを超えると、インデックスが終了します.
これをすべてのインデックスで確認します.
偶数の時.

eをsの1つの格の前に置く.
そして、単数時と同様に求める.
そして値上げすればいいです.
DPを用いた方法は古典的な解答であり,私は上記のように解答して解決した.

📒 コード#コード#

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
palin = [[0] * n for _ in range(n)]     # 팰린드롬의 결과를 담을 배열
for i in range(n):          # 홀수일 때, i를 중심으로 한 칸씩 넓혀가며 팰린드롬인지 파악
    s = i
    e = i
    while s >= 0 and e < n:
        if arr[s] != arr[e]:    # 팰린드롬이 아니면 종료, i를 중심으로 하는 이후 값들도 무조건 팰린드롬이 아니다.
            break
        palin[s][e] = 1         # 팰린드롬이면 값을 넣어준다.
        s -= 1                  # 한 칸씩 양쪽으로 넓힌다.
        e += 1
for i in range(n):          # 짝수일 때, i + 0.5를 중심으로 한 칸씩 넓혀가며 팰린드롬인지 파악
    s = i
    e = i + 1
    while s >= 0 and e < n:
        if arr[s] != arr[e]:    # 팰린드롬이 아니면 종료
            break
        palin[s][e] = 1
        s -= 1                  # 한 칸씩 양쪽으로 넓힌다.
        e += 1
m = int(input())
for _ in range(m):
    s, e = map(int, input().split())
    print(palin[s - 1][e - 1])      # padding을 따로 넣지 않고 1씩 빼준 후 출력

🔍 結果