提出 #38260304

---

ソースコード 拡げる

// g++ t.cpp -std=c++14 -I .
#include <iostream>
#include <string>
#include <map>
#include <random>
//#include <atcoder/all>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int M = 998244353;
using P = pair<int, pair<int, int>>;
template<class S, class T> void chmin(S& a, T b) {if (a>b) a=b;}
template<class S, class T> void chmax(S& a, T b) {if (a<b) a=b;}
template<class S, class T> void addMod(S& a, T b) {a=(a+b)%M;}
//int up[]={0,0,1,-1}, lf[]={1,-1,0,0};
int up[]={2,1,-1,-2,-2,-1,1,2}, lf[]={1,2,2,1,-1,-2,-2,-1};

random_device rng;
int an[320][320];
int mp[5000][10000];

int main() {
  int _; cin>>_; while(_-->0) {
    int n;cin>>n;
    int a[n],b[2*n];for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];for(int i=0;i<n;i++)b[n+i]=b[i];
    fill(mp[0],mp[n],-1);

    bool ans = true;

    for(int i=0;i<n;i++) {
      if (a[i] != b[i]) ans = false;
    }
    if (ans == true) {
      cout<<"Yes"<<endl;
      continue;
    }

    for(int i=0;i<n;i++) {
      int dp[n+1][2];fill(dp[0], dp[n+1], i); // {a[i]のi, a[i]を1つ以上捨てたか} -> b[i]のiの最大値
      for(int j=0;j<=n;j++) dp[j][0]=i, dp[j][1]=-1;

      for(int j=0;j<n;j++) {
        int k = j;
        int bi0 = dp[j][0];
        int bi1 = dp[j][1];

        if (mp[k][bi0] == -1) {
          int bi = bi0; //cout<<" "<<a[k]<<" =? "<<b[bi]<<endl;
          while(bi < 2*n && a[k] == b[bi]) bi++;
          for(int l=bi0;l<bi;l++) {
            mp[k][l] = bi;
          }
          chmax(dp[j+1][0], bi);
          if (bi >= i+n && j != n-1) ans = true;
        } else {
          chmax(dp[j+1][0], mp[k][bi0]);
          if (mp[k][bi0] >= i+n && j != n-1) ans = true;
        }

        if (j>0 && bi1>=0 && mp[k][bi1] == -1) {
          int bi = bi1;
          while(bi < 2*n && a[k] == b[bi]) bi++;
          for(int l=bi1;l<bi;l++) {
            mp[k][l] = bi;
          }
          chmax(dp[j+1][1], bi);
          if (bi >= i+n) ans = true;
        } else {
          chmax(dp[j+1][1], mp[k][bi1]);
          if (mp[k][bi1] >= i+n) ans = true;
        }

        chmax(dp[j+1][1], dp[j][0]);

        //cout<<i<<" "<<j<<" "<<dp[j][0]<<" "<<dp[j][1]<<" "<<ans<<endl;

        if (ans) break;
      }
        //cout<<i<<" "<<n<<" "<<dp[n][0]<<" "<<dp[n][1]<<" "<<ans<<endl;
      if (ans) break;
    }
    if (ans) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }
}

提出情報

ジャッジ結果