[C# / paiza POH] paizaオンラインハッカソン6（霧島編）を解く！

ニアです、こんにちはー！
今回は、paizaオンラインハッカソン6のプログラミング記事です。

paizaオンラインハッカソン6には3種類の問題がありますが、ここでは霧島さんの方をチョイスします。
-> https://paiza.jp/poh/joshibato/kirishima

1. nマスのすごろくがあり、各マスには数値が書いてあります（但し、1番目のマス（スタート）とn番目のマス（ゴール）は0です）。1番目のマスからスタートし、1回だけルーレット回して、その出目の数だけ進みます。

1. 移動したマスに書かれた値が0ならここで終了、そうでなければ、その値だけ進みます（正の数ならゴール方向、負の数ならスタートの方向）。
2. 以下のいずれかを満たすまで、2.を繰り返します。

• 移動したマスに書かれた値が0である
• 移動したマスはすごろくの範囲外である
• 同じルートで無限ループ

#1. 動的計画法（トップダウン方式）で解く！
すごろくの2マス目から順に動的計画法（トップダウン方式）を使って、ゴール可能なマスを調べていきます。

「移動するマス数」と「巡回済みフラグ」、「ゴール可能かどうかのフラグ」の3つのデータを持つ構造体（Block）を用意し、要素数nのリストを作成します。
リスト先頭（スタートマス）の巡回済みフラグとリスト末尾（ゴールマス）のゴール可能かどうかのフラグを立てておき、2番目の要素から順にゴール可能かどうかを再帰的に調べていきます。

その後、ルーレットの出目がリストの範囲内かつ、その位置のゴール可能かどうかのフラグが立っているかどうかで、ゴール可能かどうかを判別していきます。

poh6-kirishima1.cs

using System;

struct Block {
	// 移動するマス数
	public int NextTo;
	// 巡回済みフラグ
	public bool IsVisit;
	// ゴール可能かどうかのフラグ
	public bool CanArriveAtGoal;
}

class Program {

	static void Main( string[] args ) {

		// すごろくのマップを作成します。
		int n = int.Parse( Console.ReadLine() );
		Block[] blocks = new Block[n];
		string[] s = Console.ReadLine().Split( ' ' );

		// 移動するマス数を読み取ります。
		// IsVisitとCanArriveAtGoalの初期値は false です。
		for( int i = 0; i < n; i++ ) {
			blocks[i] = new Block {
				NextTo = int.Parse( s[i] ),
				IsVisit = false,
				CanArriveAtGoal = false
			};
		}

		// スタートマスを巡回済みにします。
		blocks[0].IsVisit = true;
		// ゴールマスのCanArriveAtGoalを true にします。
		blocks[n - 1].CanArriveAtGoal = true;

		// 動的計画法（トップダウン方式）で2マス目からゴール手前のマスまでの中で
		// ゴール可能かどうかを調べます。
		for( int i = 1; i < n - 1; i++ )
			VerifyBlocks( i, blocks );

		int m = int.Parse( Console.ReadLine() );
		// サイコロの出目からゴール可能かどうかを調べます。
		for( int i = 0; i < m; i++ ) {
			int dice = int.Parse( Console.ReadLine() );
			Console.WriteLine( dice > 0 && dice < n && blocks[dice].CanArriveAtGoal ? "Yes" : "No" );
		}

	}

	static bool VerifyBlocks( int cur, Block[] blocks ) {
		// cur + 1 番目のマスをまだ巡回していない時
		if( !blocks[cur].IsVisit ) {
			// cur + 1 番目のマスを巡回済みにします。
			blocks[cur].IsVisit = true;
			// 移動するマス数が0の時、CanArriveAtGoalの値を返します。
			// ※ true : ゴールマス / false : ゴール以外のマス
			if( blocks[cur].NextTo == 0 )
				return blocks[cur].CanArriveAtGoal;

			// 移動先のマスの位置を求めます。
			int nextBlock = cur + blocks[cur].NextTo;

			// 移動先のマスがすごろくの範囲内（スタートマスを除く）の時、
			// 再帰呼び出しで cur + 1 番目のマスからゴール可能かどうかを調査します。
			if( nextBlock > 0 && nextBlock < blocks.Length )
				blocks[cur].CanArriveAtGoal = VerifyBlocks( nextBlock, blocks );
		}
		// cur + 1 番目のマスが巡回済みの場合、そこからゴール可能かどうかの値を返します。
		// ※ cur が 0 の時は false となります。
		return blocks[cur].CanArriveAtGoal;
	}

}

paiza.IO -> https://paiza.io/projects/yf0Fu7g6hZNtnb_qCCG5qg

実行結果
◆ 入力

8
0 6 -2 -2 0 1 -1 0
6
7
3
4
2
5
10

◆ 出力

Yes
Yes
No
No
No
No

実行速度

テストケース1：success　0.03秒
テストケース2：success　0.03秒
テストケース3：success　0.03秒
テストケース4：success　0.03秒
テストケース5：success　0.03秒

-> https://paiza.jp/poh/joshibato/kirishima/result/2b905e88?o=23e249f3

#2. ゴールマスからルートを辿って解く！

もう1つの方法として、すごろくの各マスからのルートをゴールマスから辿っていき、ゴール可能なマスを見つけます。

ゴール可能なマスの位置のHashSetを作成し、ゴールマスの位置をそのHashSet及びキューに入れます。
キューからマスの位置を取り出し、そのマスに移動可能なマスを見つけていき、それらの位置をHashSet及びキューに入れます（すでにHashSetに含まれていればスキップします）。この作業をキューが空になるまで繰り返します。

その後、ルーレットの出目がHashSetに含まれるかどうかで、ゴール可能かどうかを判別していきます。

poh6-kirishima2.cs

using System;
using System.Collections.Generic;

class Program {

	static void Main( string[] args ) {

		// すごろくのマップを作成します。
		int n = int.Parse( Console.ReadLine() );
		int[] blocksNextTo = new int[n];
		string[] s = Console.ReadLine().Split( ' ' );

		// 移動するマス数を読み取ります。
		for( int i = 0; i < n; i++ )
			blocksNextTo[i] = int.Parse( s[i] );

		// ゴールマスへ到着できるルートをゴールマスから順に辿っていき、
		// ゴール可能なマスをリストアップします。

		// ゴール可能マスのHashSetです。
		HashSet<int> blocksCanArriveAtGoal = new HashSet<int>();
		// 現在のマスへ移動できるマスのキューです。（Stackでも可能です）
		Queue<int> prevBlocks = new Queue<int>();
		// HashSetとキューにゴールマスを入れます。
		blocksCanArriveAtGoal.Add( n - 1 );
		prevBlocks.Enqueue( n - 1 );

		// キューが空になるまで調べます。
		while( prevBlocks.Count > 0 ) {
			// 現在調査するマスを取得します。
			int cur = prevBlocks.Dequeue();
			// 2マス目からゴール手前のマスまでを調べ、curに移動できるマスをリストアップします。
			for( int i = 1; i < n - 1; i++ ) {
				if( i + blocksNextTo[i] == cur ) {
					// curに移動できるマスをHashSetとキューに追加します。
					if( blocksCanArriveAtGoal.Add( i ) )
						prevBlocks.Enqueue( i );
				}
			}
		}

		int m = int.Parse( Console.ReadLine() );
		// サイコロの出目からゴール可能かどうかを調べます。
		for( int i = 0; i < m; i++ ) {
			Console.WriteLine( blocksCanArriveAtGoal.Contains( int.Parse( Console.ReadLine() ) ) ? "Yes" : "No" );
		}

	}

}

paiza.IO -> https://paiza.io/projects/XUMu7r6gN8mFBQS-GgsVug

※実行結果は同じなので省略します。

実行速度

テストケース1：success　0.04秒
テストケース2：success　0.04秒
テストケース3：success　0.05秒
テストケース4：success　0.04秒
テストケース5：success　0.04秒

-> https://paiza.jp/poh/joshibato/kirishima/result/edba6f2d?o=ede63f9e

動的計画法（トップダウン方式）で解く方法と比べて、実行速度はちょっと遅めです。HashSetクラスにおいて、指定した要素が含まれているかどうかを調べる時間がネックになっているのかも。

paizaオンラインハッカソン6をまだやっていない方は、ぜひチャレンジしてみよう！

それでは、See you next time!