土下座しながら探索中

主に競技プログラミング

SRM574 Div2

250:
問題概要:
vectorvectorが与えられる
vector内には'.'または大文字のアルファベットが含まれる
vectorの要素iと同じ数が存在するアルファベットをstringでその順にまとめてリターンせよ
入力は必ず正しいものとする
(すなわち、vectorの要素が複数のアルファベットとマッチすることや一致するものがないという場合はない)

解法:
その通りにやる

コード:

class CityMap {

	public:
	string getLegend(vector <string> cityMap, vector <int> POIs) {
	  vector<int> cnt;
	  cnt.resize(30);
	  rep(i,30)
	    cnt[i] = 0;
	  rep(i,cityMap.size())
	    rep(j,cityMap[i].size())
	    if(cityMap[i][j] != '.')
	      cnt[cityMap[i][j]-'A']++;

       
	  string ret;
	  rep(i,POIs.size())
	    {
	      rep(j,cnt.size())
		{
		  if(cnt[j] == POIs[i])
		    {
		      ret += ('A'+j);
		      break;
		    }
		}
	    }
	  return ret;
	}
};

500:
問題概要:
int型の変数A,Bが与えられる (1 <= A,B <= 999,999,999)
Aを以下の操作を行うことでBにできるか?
できるなら最小ステップ数を、できないなら-1を出力せよ
操作1. Aを10で割る(小数点以下切り捨て)
操作2. Aをリバースする (例: 1234 -> 4321)

解法:
Aの桁数は操作を行うことで現在の桁数以下になる
最大9桁なので全ての通りを試して問題ないので全て試した
Aの桁数がBの桁数未満になったら操作をうちきる

コード:

class TheNumberGameDiv2 {
public:
  map<int,int> used;
  int ans;
  int Bsize;
  string itos(int d)
  {
    stringstream ss;
    ss << d;
    return ss.str();
  }
  void dfs(int A,int B,int cost)
  {
    //cout << A << " " << B << " " << cost << endl;
    if(A == B)
      {
	ans = min(ans,cost);
	return;
      }

    string sA = itos(A);
    if(sA.size() < Bsize)
      return;

    int hA = A/10;
    if(used.find(hA) == used.end())
      {
	used[hA] = cost+1;
	dfs(hA,B,cost+1);
      } 
    else if(used[hA] > cost+1)
        {
	used[hA] = cost+1;
	dfs(hA,B,cost+1);
	} 

    reverse(all(sA));
    
    if(used.find((atoi)(sA.c_str())) == used.end())
      {
	used[(atoi)(sA.c_str())] = cost+1;
	dfs((atoi)(sA.c_str()),B,cost+1);
      }
    else if(used[(atoi)(sA.c_str())] > cost+1)
      {
	used[(atoi)(sA.c_str())] = cost+1;
	dfs((atoi)(sA.c_str()),B,cost+1);
      }

    
  }

  int minimumMoves(int A, int B) {
  
    used.clear();
    ans = (1<<29);
    Bsize = itos(B).size();
    dfs(A,B,0);
    if(ans == (1<<29))
      ans = -1;
    return ans;
  }

};



1000:
問題概要:
N個の頂点と2以上N-1以下の要素をもつvector pointsが与えられる
points[0]からスタートしてpoints[0]を除くノードをすべて1回だけ訪れ再度points[0]にもどれるか?
ただし、最初はpointsの順番に従うこと
さらに、ノードiからノードjへ移動するとiからjにラインが引かれる
points以外の点から移動する際はそれらのラインをどれか1つ以上と交差しなければならない
N個のノードは時計まわりに配置される

解法:
いける可能性があるところを全て試し最終的に条件をみたしつつpoints[0]へもどれるかどうか試した
今いる場所から次にいく予定の場所へラインを1つ以上またいでいけるかどうかはループを回して実際に交差しているかどうか試した
今注目しているラインの番号の小さいノードをl,大きいノードをrとし
これから行く場所と行く予定の場所の番号が小さい方をf,大きい方をtとすると
(l < f < r) && (l > t || t > r)
または
(l < t < r) && (l > f || f > r)
の時ラインと交差している
(実際に問題の図をみてみるとわかると思う)

この事から今いるノードに隣接するノードには行く可能性がないことがわかる
(隣接している場合それまでに通ってできたラインと交差することはありえない)

あとはそれまでに通った場所をvectorにもたせ、それをdequeにつっこんで探索した

コード:

class PolygonTraversal2 {
	public:

  bool check(int from,int to,vector<int> vec)
  {
    for(int i=0;i<vec.size()-1;i++)
      {
	int l = min(vec[i],vec[i+1]);	
	int r = max(vec[i],vec[i+1]);
	int f = min(from,to);
	int t = max(from,to);
	cout << "l <  r = " << l << "," << r << " f < t = " << f << "," << t << endl;
	if((l < f && f < r) && (l > t || t > r))
	  return true;
	else if((l < t && t < r) && (l > f || f > r))
	  return true;
	
      }
    return false;
  }
  
  int count(int N, vector <int> points) {

    deque<vector<int> > deq;
    deq.push_back(points);
    int cnt = 0;
    while(!deq.empty())
      {
	vector<int> v = deq.front(); deq.pop_front();
	if(v.size() == N)
	  {
	    if(check(v[v.size()-1],points[0],v))
	      cnt++;
	    continue;
	  }
	bool visited[15];
	rep(i,15)
	  visited[i] = false; 
	rep(i,v.size())
	  visited[v[i]] = true;	  

	int now = v[v.size()-1];
	for(int i=1;i<=N;i++)
	  {
	    if(visited[i] || now+1 == i || now-1 == i)
	      continue;
	    if(check(now,i,v))
	      {
		cout << "next = " << i << endl;
		print(v);
		vector<int> next = v;
		next.push_back(i);
		deq.push_back(next);
	      }
	  }

      }
    return cnt;
  }
};