結果

問題 No.45 回転寿司
ユーザー ShotaroSuzuShotaroSuzu
提出日時 2020-05-27 17:18:18
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 4,180 bytes
コンパイル時間 4,023 ms
コンパイル使用メモリ 80,604 KB
実行使用メモリ 64,172 KB
最終ジャッジ日時 2024-04-21 05:12:51
合計ジャッジ時間 10,147 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 RE -
testcase_23 RE -
testcase_24 WA -
testcase_25 RE -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 RE -
testcase_32 RE -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder.level2.no45;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

/**
 * No.45 回転寿司.
 * https://yukicoder.me/problems/78 </br>
 * あなたは、回転寿司にきている。 </br>
 * お寿司はN皿が順番に流れてくる。N皿のお寿司のそれぞれの美味しさがViで表される。 </br>
 * 流れてくるお寿司が自分の前に来た時に取ることができるが、このお店のルールで、 </br>
 * 2連続で皿を取ることが出来ない。 </br>
 * もちろん、自分の前を過ぎたお寿司も取ることが出来ない。 </br>
 *  </br>
 * この時、あなたが得られる美味しさの最大の合計値を求めてください。 </br>
 * お寿司は一周回ってくることはないとする。 </br>
 */
public class RotationSushi {

	public static void main(String[] args) {
		new RotationSushi().execute();
	}


	private void execute() {
		List<Integer> sushis = read();

		int maxDeliciousness = calcMaxDeliciousness(sushis);

		output(maxDeliciousness);
	}

	//基本方針1.美味しいものから順に取る
	//基本方針2.端から順に足していく（要素が増えるたびに選び直す）
	//基本方針3.明らかにまずいものは取らないようにする？
	//基本方針4.一旦すべて組み合わせて最大値を求める
	
	//基本方針4でやってみる
	int calcMaxDeliciousness(List<Integer> sushis) {
		Set<List<Integer>> allCombinationByIndex = getAllSushiCombinationByIndex(sushis);
		int maxDeliciousness = findMaxDeliciousness(allCombinationByIndex, sushis);
		return maxDeliciousness;
	}

	private int findMaxDeliciousness(Set<List<Integer>> allCombinationByIndex, List<Integer> sushis) {
		int maxDeliciousness = 0;
		for(List<Integer> combinationByIndex : allCombinationByIndex) {
			int deliciousness = 0;
			for(Integer index : combinationByIndex) {
				deliciousness += sushis.get(index);
			}
			if(maxDeliciousness < deliciousness) {
				maxDeliciousness = deliciousness;
			}
		}
		return maxDeliciousness;
	}

	private Set<List<Integer>> getAllSushiCombinationByIndex(List<Integer> sushis) {
		Set<List<Integer>> sushiConmbinationsByIndex = new HashSet<>();
		Set<List<Integer>> sushiCombinationsByIndexForSearch = new HashSet<>(); 
		sushiCombinationsByIndexForSearch.add(Arrays.asList(0));
		if(sushis.size() >= 2) {
			sushiCombinationsByIndexForSearch.add(Arrays.asList(1));
		}
		return getAllCombinationByIndexRecursively(sushis, sushiConmbinationsByIndex, sushiCombinationsByIndexForSearch);
	}


	private Set<List<Integer>> getAllCombinationByIndexRecursively(List<Integer> sushis, Set<List<Integer>> sushiConmbinationsByIndex, Set<List<Integer>> sushiCombinationsByIndexForSearch) {
		if (sushiCombinationsByIndexForSearch.isEmpty()) {
			return sushiConmbinationsByIndex;
		}
		Set<List<Integer>> newSushiCombinationsForSearch = new HashSet<>();
		for(List<Integer> combination : sushiCombinationsByIndexForSearch) {
			int currentIndex = combination.get(combination.size() - 1); 
			if(currentIndex >= sushis.size() - 2) {
				sushiConmbinationsByIndex.add(combination);
				continue;
			}
			if(currentIndex < sushis.size()  - 2) {
				List<Integer> skipOneCombination = new LinkedList<>(combination);
				skipOneCombination.add(currentIndex + 2);
				newSushiCombinationsForSearch.add(skipOneCombination);
			}
			if(currentIndex < sushis.size()  - 3) {
				List<Integer> skipTowCombination = new LinkedList<>(combination);
				skipTowCombination.add(currentIndex + 3);
				newSushiCombinationsForSearch.add(skipTowCombination);
			}
		}
		return getAllCombinationByIndexRecursively(sushis, sushiConmbinationsByIndex, newSushiCombinationsForSearch);
	}


	private void output(int maxDeliciousness) {
		System.out.println(maxDeliciousness);
	}

	private List<Integer> read() {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		
		List<Integer> sushi = new ArrayList<>();
		for (int i = 0; i < sc.nextInt(); i++) {
			sushi.add(sc.nextInt());
		}
		return sushi;
	}

}
0