結果

問題 No.45 回転寿司
ユーザー velfare_nagata
提出日時 2016-10-06 10:16:09
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 3,318 bytes
コンパイル時間 934 ms
コンパイル使用メモリ 113,676 KB
実行使用メモリ 29,604 KB
最終ジャッジ日時 2024-11-24 17:30:11
合計ジャッジ時間 2,898 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 WA * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = "7";
			//var line2 = "1 2 9 10 1 1 4";

			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 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>( index =>
			{
				var taste = v[index];
				var leftTaste = ( ( index - 1 >= 0 ) && ( !priorityTable.ContainsKey(index - 1) || priorityTable[index - 1] != int.MinValue ) ? v[index - 1] : 0 );
				var rightTaste = ( ( index + 1 < n ) && ( !priorityTable.ContainsKey( index + 1 ) || priorityTable[index + 1] != int.MinValue ) ? v[index + 1] : 0 );
				return taste - leftTaste - rightTaste;
			} );
			var updatePriorityTable = new Action<int>( index =>
			{
				var priority = getPriority( index );
				if( priority < 0 )
				{
					var shortPriority = ~( (short)( ( ~priority ) + 1 ) ) - 1;
					priorityTable[index] = ( shortPriority << 16 ) + index;
				}
				else
				{
					priorityTable[index] = ( priority << 16 ) + index;
				}
			} );

			// 優先度 = 取った皿の美味しさ - 取れなくなる皿の美味しさ
			// 優先度データは32bitデータで下記のように管理する
			// PPPPPPPPPPPPPPPPiiiiiiiiiiiiiiii
			// P：優先度
			// i：インデックス
			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;
				var bb = index - 2;
				if( bb >= 0 && priorityTable[bb] != int.MinValue )
					updatePriorityTable( bb );
				var ff = index + 2;
				if( ff < n && priorityTable[ff] != int.MinValue )
					updatePriorityTable( ff );
			}

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