結果

問題 No.45 回転寿司
ユーザー velfare_nagata
提出日時 2016-10-06 12:50:46
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,697 bytes
コンパイル時間 917 ms
コンパイル使用メモリ 113,848 KB
実行使用メモリ 27,684 KB
最終ジャッジ日時 2024-11-24 17:30:25
合計ジャッジ時間 6,830 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 1 WA * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = "6";
			//var line2 = "340 2 225 296 621 454";
			
			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 remainList = 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 ) + 1;
				var lossPoint = lossList.IndexOf( leftTaste + rightTaste ) + 1;
				var remainPoint = remainList.IndexOf( taste - ( leftTaste + rightTaste ) ) + 1;
				return gainPoint + lossPoint + remainPoint;
			} );
			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();
				remainList.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 );
					if( taste > 0 && leftTaste > 0 && rightTaste > 0 )
						remainList.Add( taste - ( leftTaste + rightTaste ) );
				}
				gainList.Sort();
				lossList.Sort();
				lossList.Reverse();
				remainList.Sort();
				remainList.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