Div 2 500, Div1 250 - RouteIntersection

問題

N 次元空間で移動する．移動経路は途中で交わるか？

考え方

次元数がとてつもなくデカイこと，移動回数はそんなに多くないことから，移動シミュレーションをやるのが吉．適当な回数移動した状態からの移動差分だけを計算し，原点になっているかをチェックする．

コード

#include <vector>
#include <string>
#include <map>
using namespace std;
class RouteIntersection
{
public:
  string isValid(int N, vector <int> coords, string moves)
  {
    for( int i = 0 ; i < coords.size() ; ++i ) {
      map<int,int> dx;
      for( int j = i ; j < coords.size() ; ++j ) {
        if( dx.find(coords[j]) != dx.end() ) {
          dx[coords[j]] += (moves[j]=='+')?1:(-1);
          if( dx[coords[j]] == 0 ) dx.erase(dx.find(coords[j]));
        } else {
          dx.insert(pair<int,int>(coords[j], (moves[j]=='+')?1:(-1)));
        }
        if( dx.empty() ) return "NOT VALID";
      }
    }
    return "VALID";
  }
};