Topcoder SRM 563 div2

眠い。
がんばった。A,B解いた。
でも、Bすごい時間かかった。あと2分くらいのときにとけた。
Q.push({1,2,3,4});みたいのだめだった。
もっと早く解きたい。

A.なんかがんばるだけ。簡単。

#include <iostream>
#include <sstream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

class FoxAndHandleEasy {
    public:
        string isPossible(string S, string T) {
            for(int i=0;i<S.length();i++){
                string n = S.substr(0,i)+S+S.substr(i);
                if(n==T) return "Yes";
            }
            return "No";
        }


// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arg0 = "Ciel"; string Arg1 = "CieCiell"; string Arg2 = "Yes"; verify_case(0, Arg2, isPossible(Arg0, Arg1)); }
	void test_case_1() { string Arg0 = "Ciel"; string Arg1 = "FoxCiel"; string Arg2 = "No"; verify_case(1, Arg2, isPossible(Arg0, Arg1)); }
	void test_case_2() { string Arg0 = "FoxCiel"; string Arg1 = "FoxFoxCielCiel"; string Arg2 = "Yes"; verify_case(2, Arg2, isPossible(Arg0, Arg1)); }
	void test_case_3() { string Arg0 = "FoxCiel"; string Arg1 = "FoxCielCielFox"; string Arg2 = "No"; verify_case(3, Arg2, isPossible(Arg0, Arg1)); }
	void test_case_4() { string Arg0 = "Ha"; string Arg1 = "HaHaHaHa"; string Arg2 = "No"; verify_case(4, Arg2, isPossible(Arg0, Arg1)); }
	void test_case_5() { string Arg0 = "TheHandleCanBeVeryLong"; string Arg1 = "TheHandleCanBeVeryLong"; string Arg2 = "No"; verify_case(5, Arg2, isPossible(Arg0, Arg1)); }
	void test_case_6() { string Arg0 = "Long"; string Arg1 = "LongLong"; string Arg2 = "Yes"; verify_case(6, Arg2, isPossible(Arg0, Arg1)); }

// END CUT HERE

};



// BEGIN CUT HERE

int main() {
    FoxAndHandleEasy ___test;
    ___test.run_test(-1);
}

// END CUT HERE

B.夕方にもやったような……
BFSでがんばるだけ。setがうんたらしたりしてつらかった。
pair

#include <iostream>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>

#include <numeric>
#include <algorithm>
#include <functional>

#include <cctype>

#include <complex>
#include <string>
#include <sstream>

using namespace std;
#define pb push_back
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()

#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it)

const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};

typedef struct CASE{
    int x1;
    int y1;
    int x2;
    int y2;
    int k;
} C;
typedef struct CASE2{
    int x1;
    int y1;
    int x2;
    int y2;
} CC;
class CoinsGameEasy {
    public:
    int w,h;
        int check(C c){
            int ret = 0;
            if(c.x1 == 0 || c.x1 == w-1
               || c.y1 == 0 || c.y1 == h-1) ret++;
            if(c.x2 == 0 || c.x2 == w-1
               || c.y2 == 0 || c.y2 == h-1) ret++;
            return ret;
        }
        int minimalSteps(vector <string> board) {
            int x1,x2,y1,y2;
            x1 = x2 = y1 = y2 = -1;
            w = board[0].length()+2;
            h = board.size()+2;
            stringstream ss;
            rep(i,w) ss << ".";
            string s;
            ss >> s;
            rep(i,h-2){
                board[i] = "." + board[i] + ".";
            }
            board.insert(board.begin(),s);
            board.push_back(s);

            rep(i,h){
                rep(j,w){
                    if(board[i][j] == 'o'){
                        if(x1 == -1 && y1 == -1){
                            x1 = j;y1 = i;
                        }else{
                            x2 = j;y2 = i;
                        }
                    }
                }
            }


            set<pair<int,pair<int,pair<int,int> > > > S;
            queue<C> Q;
            C c = {x1,y1,x2,y2,0};

            Q.push(c);
            //S.insert(make_pair(x1,make_pair(y1,make_pair(x2,y2))));

            while(!Q.empty()){
                C c = Q.front();
                Q.pop();
                pair<int,pair<int,pair<int,int> > > c2 = make_pair(c.x1,make_pair(c.y1,make_pair(c.x2,c.y2)));
                if(S.find(c2) != S.end()) continue;
                S.insert(c2);
                int k = check(c);
                if(c.k == 11) break;

                if(k == 1) return c.k;
                if(k == 2){
                    continue;
                }

                rep(i,4){
                    int nx1,nx2,ny1,ny2;
                    nx1 = c.x1+dx[i];
                    nx2 = c.x2+dx[i];
                    ny1 = c.y1+dy[i];
                    ny2 = c.y2+dy[i];
                    if(board[ny1][nx1] == '#'){
                        nx1 = c.x1;ny1 = c.y1;
                    }
                    if(board[ny2][nx2] == '#'){
                        nx2 = c.x2;ny2 = c.y2;

                    }
                    C c2 = {nx1,ny1,nx2,ny2,c.k+1};
                    Q.push(c2);
                }
            }
            return -1;
        }


// BEGIN CUT HERE
	public:
	void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); if ((Case == -1) || (Case == 6)) test_case_6(); }
	private:
	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
	void test_case_0() { string Arr0[] = {"oo"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 1; verify_case(0, Arg1, minimalSteps(Arg0)); }
	void test_case_1() { string Arr0[] = {".#",
 ".#",
 ".#",
 "o#",
 "o#",
 "##"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 4; verify_case(1, Arg1, minimalSteps(Arg0)); }
	void test_case_2() { string Arr0[] = {"..",
 "..",
 "..",
 "o#",
 "o#",
 "##"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(2, Arg1, minimalSteps(Arg0)); }
	void test_case_3() { string Arr0[] = {"###",
 ".o.",
 "###",
 ".o.",
 "###"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(3, Arg1, minimalSteps(Arg0)); }
	void test_case_4() { string Arr0[] = {"###",
 ".o.",
 "#.#",
 ".o.",
 "###"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 3; verify_case(4, Arg1, minimalSteps(Arg0)); }
	void test_case_5() { string Arr0[] = {"###########",
 "........#o#",
 "###########",
 ".........o#",
 "###########"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 10; verify_case(5, Arg1, minimalSteps(Arg0)); }
	void test_case_6() { string Arr0[] = {"############",
 ".........#o#",
 "############",
 "..........o#",
 "############"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = -1; verify_case(6, Arg1, minimalSteps(Arg0)); }

// END CUT HERE

};



// BEGIN CUT HERE

int main() {
    CoinsGameEasy ___test;
    ___test.run_test(-1);
}

// END CUT HERE