第28回オフラインリアルタイムどう書く　をC++で

#まとめ
* やってみた
* テストデータを含めずに150行ほど
* かかった時間は2時間ほど。問題文パーサに1時間、解答に30分、デバッグに30分。
* できたあとで他の人のを見てみると、こっちのやり方がゴリ押し過ぎて吹いた。
* 整数型に int ではなく long long を使っているのは、追加問題を解くための苦肉の策
* 記事を投稿した後で思い出したけど string -> long long 変換部分を書くのにググってたからオフラインじゃなかった。

#問題に対するアプローチ
[問題はこちら](http://nabetani.sakura.ne.jp/hena/ord28spirwa/)
城壁をグルグル回る。回るごとに外周がでかくなる。自分が今向いている方向はどこか？　という問題。
回るごとにどんどん長くなっていくので計算量が爆発しそうに感じるが、実際のところ、増えるのは突起の先の部分だけだ。

■■↓↓↓
■↓←↓↓
■↓↓←↓
←←↓↓←
←←←↓
←←←←

南東の角に沿って進む左向きの矢印は東の突起と同じ1マスだし、南東の角に沿う下向きの矢印は南の突起と同じ2マス。ここはどれだけ外周を回っても数が変わらない。
代わりに、突起の厚さ(？)を回り込むための矢印は数が増えていく。

というわけで、突起の部分だけを変数にして、あとの東西南北の突起の長さは定数のままに、うまいこと計算してやればなんとかなりそう、ということがわかる。
ただし、0日目の分のマスによって2週目以降の切り替わりが厄介になる。

→→↓
→↓→→↓
■→→↓↓
■→↓↓↓
■■↓↓↓

ここは周回最後の南下だけ北の突起から1マス減らすようにすればいい。
そして0日目がある分、二週目以降の最初の東行きが突起より1マス増える。
このことを考慮してコーディングしていく。

#コードと結果

コードはこちら。結果出力部分はいろいろサボった。

```C++:spiral.cpp
// 十字の壁がそそり立つ世界の中を君は螺旋状に歩く 　 横へな 2015.2.7 問題
// http://nabetani.sakura.ne.jp/hena/ord28spirwa/
// 諸事情により C++11 以降は使わず
// 基本的に int ではなく long long なのは追加問題を解くための苦し紛れの策

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

// 十字の壁のデータ構造体　北東南西
struct CrossWall {
	long long N;
	long long E;
	long long S;
	long long W;
};

// 問題の入力文字列を解析して数値型に戻すクラス
class QuestionParser{
public:
	QuestionParser(const string &question):n(), e(), s(), w(), days(){
		// 日数を設定
		vector<string> QandA(Split(question, ':'));
		days = StoI(QandA[1]);
		// 十字の壁の長さを設定
		vector<string> Q(Split(QandA[0], ','));
		n = StoI(Q[0]);
		e = StoI(Q[1]);
		s = StoI(Q[2]);
		w = StoI(Q[3]);
		return;
	}
	// 壁のデータ構造体を返す
	CrossWall GetCrossWall(void){
		CrossWall wall = {n, e, s, w};
		return wall;
	}
	// 日数を返す
	long long GetDays(void){
		return days;
	}
private:
	// 十字の壁の長さ　北東南西
	long long n, e, s, w;
	// 日数
	long long days;
	// 入力された文字列を指定された区切り文字で区切る
	vector<string> Split(const string &input, const char sep){
		istringstream ss(input);
		vector<string> vec;
		string word;
		while (getline(ss, word, sep)) {
			vec.push_back(word);
		}
		return vec;  // C++11 より前ならコピー返しになるので効率悪い
	}
	// 文字列を long long 型に変換
	long long StoI(const string &input){
		istringstream ss(input);
		long long i; ss >> i; return i;
	}
};

/////////////////////////////////////
// 解答本体：十字の壁を歩く
/////////////////////////////////////
string WalkingWay(const CrossWall & wall, long long days){
	long long wall_edge = 2;// 壁の端の長さ　一週回るごとに長くなる

	// 東側の突起から始める
	days -= wall.E; //東に進む
	if(days<0) { return "E"; }
	// 回る
	while (days>=0){
		// 東側の突起　続き
		days -= wall_edge;// 南に進む
		if(days<0){ return "S"; }
		days -= wall.E; // 西に戻る
		if(days<0) { return "W"; }

		// 南側の突起
		days -= wall.S; // 南に進む
		if(days<0) { return "S"; }
		days -= wall_edge; // 西に進む
		if(days<0){ return "W"; }
		days -= wall.S; // 北に戻る
		if(days<0){ return "N"; }

		// 西側の突起
		days -= wall.W; // 西に進む
		if(days<0) { return "W"; }
		days -= wall_edge; // 北に進む
		if(days<0){ return "N"; }
		days -= wall.W; // 東に戻る
		if(days<0){ return "E"; }

		// 北側の突起
		days -= wall.N; // 北に進む
		if(days<0) { return "N"; }
		days -= wall_edge; // 東に進む
		if(days<0){ return "E"; }
		days -= (wall.N-1); // 南に戻る　ここは最初の0日目分に気を付ける
		if(days<0){ return "S"; }
		
		// 全ての突起を回ったので外周が増える
		wall_edge += 2;
		
		// 東側の突起の最初
		days -= (wall.E+1); //東に進む　ここは二週目分に気をつける
		if(days<0) { return "E"; }
	}
	// ここにいるならおかしいのでエラー文字を返す
	return "X";
}

// 結果を確認する
void test(const string &question, const string &right){
	// 問題文を解析して解く
	QuestionParser q(question);
	CrossWall wall(q.GetCrossWall());
	string answer(WalkingWay(wall, q.GetDays()));
	// デバッグ用メッセージ出力
	static int num=0;
	if(answer!=right){
		cout << num << ":Wrong!: " << question << endl;
		cout << "Ansered: " << answer << " But Right: " << right << endl;
	}
	num++;
	return;
}

// 追加問題を解いて表示
void AdvancedTest(const string &question){
	// 問題文を解析して解く
	QuestionParser q(question);
	CrossWall wall(q.GetCrossWall());
	string answer(WalkingWay(wall, q.GetDays()));
	// 解答データを出力
	cout << "Q:" << question << " Answer:"  << answer << endl;
	return;
}

// エントリポイント　ここからはじまる
int main(void){
	// エラーがあれば文字出力　なければ何も出力しない
/*0*/ test( "2,3,5,4:85", "S" );    
/*1*/ test( "1,2,3,4:1", "E" );    
/*2*/ test( "1,2,3,4:2", "S" );    
/*3*/ test( "1,2,3,4:3", "S" );    
/*4*/ test( "1,2,3,4:4", "W" );    
/*5*/ test( "1,2,3,4:27", "E" );    
/*6*/ test( "1,2,3,4:63", "E" );    
/*7*/ test( "1,2,3,4:40", "W" );    
/*8*/ test( "1,4,3,2:40", "S" );    
/*9*/ test( "3,3,3,3:30", "S" );    
/*10*/ test( "3,3,3,3:31", "E" );    
/*11*/ test( "3,3,3,3:32", "E" );    
/*12*/ test( "3,3,3,3:70", "S" );    
/*13*/ test( "3,3,3,3:71", "E" );    
/*14*/ test( "3,3,3,3:72", "E" );    
/*15*/ test( "1,1,1,1:7", "N" );    
/*16*/ test( "1,2,1,1:7", "W" );    
/*17*/ test( "1,6,1,1:7", "S" );    
/*18*/ test( "1,8,1,1:7", "E" );    
/*19*/ test( "1,1,1,1:30", "N" );    
/*20*/ test( "1,2,1,1:30", "W" );    
/*21*/ test( "1,5,1,1:30", "S" );    
/*22*/ test( "1,8,1,1:30", "E" );    
/*23*/ test( "9,9,9,9:99", "W" );    
/*24*/ test( "5,6,3,8:3", "E" );    
/*25*/ test( "5,8,1,1:11", "W" );    
/*26*/ test( "2,8,1,2:18", "S" );    
/*27*/ test( "3,2,3,1:20", "N" );    
/*28*/ test( "3,3,8,1:28", "N" );    
/*29*/ test( "2,5,1,2:32", "E" );    
/*30*/ test( "2,5,1,6:33", "E" );    
/*31*/ test( "1,2,5,7:34", "N" );    
/*32*/ test( "3,6,5,6:36", "E" );    
/*33*/ test( "6,2,8,1:39", "S" );    
/*34*/ test( "3,1,2,3:41", "W" );    
/*35*/ test( "1,1,3,4:45", "W" );    
/*36*/ test( "1,3,1,2:46", "N" );    
/*37*/ test( "4,4,4,4:49", "W" );    
/*38*/ test( "3,1,4,4:55", "N" );    
/*39*/ test( "6,6,2,1:56", "W" );    
/*40*/ test( "3,2,1,2:59", "S" );    
/*41*/ test( "2,7,7,1:60", "S" );    
/*42*/ test( "3,1,1,1:63", "N" );    
/*43*/ test( "4,6,4,1:78", "E" );    
/*44*/ test( "7,5,3,6:79", "W" );    
/*45*/ test( "7,8,3,1:81", "E" );    
/*46*/ test( "3,2,5,2:82", "S" );    
/*47*/ test( "1,1,3,4:84", "N" );    
/*48*/ test( "7,4,1,5:88", "S" );    
/*49*/ test( "3,6,5,3:89", "S" );    
/*50*/ test( "1,4,2,3:92", "N" );    
/*51*/ test( "1,3,4,5:93", "W" );    
/*52*/ test( "2,4,8,1:94", "W" );    
/*53*/ test( "3,6,1,7:99", "S" );

// 追加問題
	cout << "Advanced Test" << endl;
	AdvancedTest("1234,2345,3456,4567:978593417");
	AdvancedTest("1234,2345,3456,4567:978593418");
	AdvancedTest("31415,92653,58979,32384:9812336139");
	AdvancedTest("31415,92653,58979,32384:9812336140");
	AdvancedTest("314159,265358,979323,84626:89099331642");
	AdvancedTest("314159,265358,979323,84626:89099331643");
	return 0;
}

```

追加問題の答えは標準出力に表示

```shell-session:
Advanced Test
Q:1234,2345,3456,4567:978593417 Answer:E
Q:1234,2345,3456,4567:978593418 Answer:S
Q:31415,92653,58979,32384:9812336139 Answer:W
Q:31415,92653,58979,32384:9812336140 Answer:S
Q:314159,265358,979323,84626:89099331642 Answer:S
Q:314159,265358,979323,84626:89099331643 Answer:W
```

こんな感じで。