結果

問題 No.45 回転寿司
ユーザー velfare_nagatavelfare_nagata
提出日時 2016-10-06 12:19:12
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,423 bytes
コンパイル時間 978 ms
コンパイル使用メモリ 112,396 KB
実行使用メモリ 29,992 KB
最終ジャッジ日時 2024-05-03 15:36:33
合計ジャッジ時間 6,127 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 36 ms
19,072 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 37 ms
18,816 KB
testcase_22 AC 36 ms
19,200 KB
testcase_23 AC 34 ms
18,944 KB
testcase_24 AC 35 ms
19,200 KB
testcase_25 AC 31 ms
19,072 KB
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 AC 33 ms
19,072 KB
testcase_32 AC 32 ms
19,072 KB
testcase_33 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace CodeIq
{
	internal class Program
	{
		/// <summary>
		/// あなたは、回転寿司にきている。
		/// お寿司はN皿が順番に流れてくる。N皿のお寿司のそれぞれの美味しさがViで表される。
		/// 
		/// 流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、
		/// 連続で皿を取ることが出来ない。
		/// もちろん、自分の前を過ぎたお寿司も取ることが出来ない。
		/// 
		/// この時、あなたが得られる美味しさの最大の合計値を求めてください。
		/// お寿司は一周回ってくることはないとする。
		/// </summary>
		private static void Main()
		{
			// パラメータ取得
			var line1 = Console.ReadLine();
			var line2 = Console.ReadLine();
			//var line1 = "12";
			//var line2 = "309 748 273 451 241 704 200 300 487 375 4 691";

			var n = int.Parse( line1.Split( ' ' )[0] );
			var v = new int[n];
			var vDatas = line2.Split( ' ' );
			for( var i = 0; i < n; i++ )
				v[i] = int.Parse( vDatas[i] );

			var gainList = new List<int>();
			var lossList = new List<int>();
			var priorityTable = new Dictionary<int, int>();
			var isAte = new Func<bool>( () =>
			{
				foreach( var value in priorityTable.Values )
					if( value != int.MinValue )
						return false;
				return true;
			} );
			var getPriority = new Func<int, int>( i =>
			{
				if( priorityTable.ContainsKey( i ) && priorityTable[i] == int.MinValue )
					return int.MinValue;

				var taste = ( !priorityTable.ContainsKey( i ) || priorityTable[i] != int.MinValue ) ? v[i] : 0;
				var leftTaste = ( ( i - 1 >= 0 ) && ( !priorityTable.ContainsKey( i - 1 ) || priorityTable[i - 1] != int.MinValue ) ? v[i - 1] : 0 );
				var rightTaste = ( ( i + 1 < n ) && ( !priorityTable.ContainsKey( i + 1 ) || priorityTable[i + 1] != int.MinValue ) ? v[i + 1] : 0 );
				var gainPoint = gainList.IndexOf( taste );
				var lossPoint = lossList.IndexOf( leftTaste + rightTaste );
				return ( gainPoint + lossPoint ) > 0 ? gainPoint + lossPoint : 0;
			} );
			var updatePriorityTable = new Action<int>( index =>
			{
				var priority = getPriority( index );
				if( priority != int.MinValue )
					priorityTable[index] = ( priority << 16 ) + index;
			} );
			var updateLossGainList = new Action( () =>
			{
				// SUSHI毎の損得リストを更新
				// SUSHI αを取った際の損益を順位化し、総合ポイントによって優先度を判定する
				gainList.Clear();
				lossList.Clear();
				for( var i = 0; i < v.Length; i++ )
				{
					var taste = ( !priorityTable.ContainsKey( i ) || priorityTable[i] != int.MinValue ) ? v[i] : 0;
					var leftTaste = ( ( i - 1 >= 0 ) && ( !priorityTable.ContainsKey( i - 1 ) || priorityTable[i - 1] != int.MinValue ) ? v[i - 1] : 0 );
					var rightTaste = ( ( i + 1 < n ) && ( !priorityTable.ContainsKey( i + 1 ) || priorityTable[i + 1] != int.MinValue ) ? v[i + 1] : 0 );
					if( taste > 0 && !gainList.Contains( taste ) )
						gainList.Add( taste );
					if( ( leftTaste + rightTaste ) > 0 && !lossList.Contains( leftTaste + rightTaste ) )
						lossList.Add( leftTaste + rightTaste );
				}
				gainList.Sort();
				lossList.Sort();
				lossList.Reverse();
			} );

			// 優先度 = 取った皿の美味しさ - 取れなくなる皿の美味しさ
			// 優先度データは32bitデータで下記のように管理する
			// PPPPPPPPPPPPPPPPiiiiiiiiiiiiiiii
			// P：優先度
			// i：インデックス
			updateLossGainList();
			for( var i = 0; i < v.Length; i++ )
				updatePriorityTable( i );

			// 優先度の高い順にSUSHIをとっていく
			var totalTaste = 0;
			while( !isAte() )
			{
				var target = priorityTable.Values.Max();
				var index = ( target & 0xFFFF );
				totalTaste += v[index];

				// SUSHIを取った時点で横の皿が取得できなくなり、更に横の皿の優先度が更新される
				priorityTable[index] = int.MinValue;
				var b = index - 1;
				if( b >= 0 )
					priorityTable[b] = int.MinValue;
				var f = index + 1;
				if( f < n )
					priorityTable[f] = int.MinValue;

				updateLossGainList();
				for( var i = 0; i < n; i++ )
					updatePriorityTable( i );
			}

			Debug.Print( totalTaste.ToString() );
			Console.WriteLine( totalTaste );
		}
	}
}
0