白俊10942号フェリンドロン?

白駿10942フィリン・ドロン?

問題のショートカット

コード#コード#

import sys

def palindrome(S, E):

  if check[S][E] == 1:
    return 1
  
  if S == E:
    return 1
  if E - S == 1:
    if numbers[S] == numbers[E]:
      check[S][E] = 1
      return 1
    else:
      return 0 
  
  if palindrome(S+1, E-1) == 1:
    if numbers[S] == numbers[E]:
      check[S][E] = 1
      return 1
    else:
      return 0
  else:
    return 0

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline())
questions = []

check = [[0 for _ in range(N)] for _ in range(N)]

for i in range(M):
  questions.append(list(map(int, sys.stdin.readline().split())))

for S, E in questions:
  print(palindrome(S-1, E-1))

トラブルシューティング

フェリンドロンって何?

回文:回文やファリンドロンは、逆さまに読んでも読める文や単語、数字、文字列などです.通常、単語間のスペースや句読点は無視されます.

各ビット数を比較します。

与えられた質問に応じて、それぞれすべての質問に答えればよい.このとき質問を基にS,Eをそれぞれ選び,フィリンドロムを作るかどうかを比較する.
でもタイムアウト...
与えられた最大問題数は10万個で,それぞれを比較すると時間的に複雑度が増し,当然タイムアウトが発生する.

ポイントDPを使用します。

時間を減らすために,以前に行った計算を繰り返す必要はなく,保存して利用すればよい.ここで,フェリンドロンを証明するために,S,Eごとに1格のS+1を移動し,E−1もフェリンドロンを構成する.これに基づいて,動的プログラミングアルゴリズムを用いて問題を解決することは容易である.
フェリンドロムを救うために、以前にやった計算なら...Check二重配列でPhilyndromが使えるか確認し,できれば計算なしで1を返す.