ABC326F問題

Robot Rotation

atcoder.jp

まず、全探索を考えます。
単純なBit全探索だと、入力が最大の時に計算量が2^80になってしまい、間に合わないので工夫する必要があります。

まず、行動をする時に向くことができる方向が右と左の２つだけなので、配列Aのうち、奇数番目の要素はY軸方向、偶数番目の要素はX軸方向にしか関係がないとわかります。

つまり、２つにわけて考えることができるので、ここで計算量が2^40*2になります。

また、例えばY軸に関係する要素も前から全探索するのと後ろから全探索する、の２つにわけると、入力が最大のときでも計算量は2^20*2*2にまで落とすことができます。

このように、うまく工夫して計算量を落とすとACを得ることができます。

(Y軸方向と、X軸方向の２回、Bit全探索を行うので関数にしました）

#include <bits/stdc++.h>
using namespace std;
pair<int,int> rotti(int n,vector<long long>a,long long mokuteki){
  long long count;
  if(n<=20){
    for(int tmp=0;tmp<(1<<n);tmp++){
      bitset<20>s(tmp);
      count=0;
      for(int i=0;i<n;i++){
	if(s[i]==1)count+=a[i];
	else count-=a[i];
      }
      if(count==mokuteki){
	return {tmp,-1};
      }
    }
    return {-1,-1};
  }
  map<long long,int>dict;
  for(int tmp=0;tmp<(1<<20);tmp++){
    bitset<20>s(tmp);
    count=0;
    for(int i=0;i<20;i++){
      if(s[i]==1)count+=a[i];
      else count-=a[i];
    }
    dict[count]=tmp;
  }
  for(int tmp=0;tmp<(1<<(n-20));tmp++){
    bitset<20>s(tmp);
    count=0;
    for(int i=0;i<n-20;i++){
      if(s[i]==1)count+=a[i+20];
      else count-=a[i+20];
    }
    if(dict.count(mokuteki-count)==0)continue;
    return {dict[mokuteki-count],tmp};
  }
  return {-1,-1};
}
int main()
{
  long long n,x,y;
  cin >> n >> x >> y;
  vector<long long>A(n),a,b;
  for(int i=0;i<n;i++)cin >> A[i];
  for(int i=0;i<n;i++){
    if(i%2==0)a.emplace_back(A[i]);
    else b.emplace_back(A[i]);
  }
  //たて
  pair<int,int>tate=rotti(a.size(),a,y);
  if(tate.first==-1){
    cout << "No" << endl;
    return 0;
  }
  vector<int>tate_muki;
  bitset<20>t(tate.first);
  for(int i=0;i<min(int(a.size()),20);i++){
    if(t[i]==1)tate_muki.emplace_back(1);
    else tate_muki.emplace_back(0);
  }
  bitset<20>s(tate.second);
  if(tate.second!=-1){
    for(int i=0;i<a.size()-20;i++){
      if(s[i]==1)tate_muki.emplace_back(1);
      else tate_muki.emplace_back(0);
    }
  }
  pair<int,int>yoko=rotti(b.size(),b,x);
  if(yoko.first==-1){
    cout << "No" << endl;
    return 0;
  }
  bitset<20>ss(yoko.first);
  vector<int>yoko_muki;
  for(int i=0;i<min(int(b.size()),20);i++){
    if(ss[i]==1)yoko_muki.emplace_back(1);
    else yoko_muki.emplace_back(0);
  }
  bitset<20>tt(yoko.second);
  if(yoko.second!=-1){
    for(int i=0;i<b.size()-20;i++){
      if(tt[i]==1)yoko_muki.emplace_back(1);
      else yoko_muki.emplace_back(0);
    }
  }
  char hako='R',muki='R';
  x=0,y=0;
  cout << "Yes" << endl;
  for(int i=0;i<n;i++){
    if(i%2==0){
      if(x==tate_muki.size())break;
      if(muki=='L'){
	if(tate_muki[x]==1)hako='R';
	else hako='L';
      }
      else{
	if(tate_muki[x]==1)hako='L';
	else hako='R';
      }
      if(tate_muki[x]==1)muki='U';
      else muki='D';
      x++;
    }
    else{
      if(y==yoko_muki.size())break;
      if(muki=='U'){
	if(yoko_muki[y]==1)hako='R';
	else hako='L';
      }
      else {
	if(yoko_muki[y]==1)hako='L';
	else hako='R';
      }
      if(yoko_muki[y]==1)muki='R';
      else muki='L';
      y++;
    }
    cout << hako;
  }
  cout << endl;
  return 0;
}