#306584 (Java21) No.5003 物理好きクリッカー

提出ソース

結果

問題	No.5003 物理好きクリッカー
ユーザー	uwi
提出日時	2018-12-25 22:53:09
言語	Java21 (openjdk 21)
結果	TLE
実行時間	-
コード長	7,157 bytes
コンパイル時間	3,407 ms
実行使用メモリ	396,324 KB
スコア	1,923,441,553
平均クエリ数	312.50
最終ジャッジ日時	2021-07-19 09:56:46
合計ジャッジ時間	34,953 ms
ジャッジサーバーID （参考情報）	judge15 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	8,906 ms 396,324 KB
testcase_01	TLE	-
testcase_02	--	-
testcase_03	--	-
testcase_04	--	-
testcase_05	--	-
testcase_06	--	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

package adv2018.marathon;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;

public class A2 {
	static Scanner in;
	static PrintWriter out;
	static String INPUT = "";
	
	static final int W = 200;
	
	// 0:click
	// 1-5: buy
	// 8: reclick
	// 9-13: reinforce
	
	static final boolean DEBUG = false;
	
	static void solve()
	{
		int n = ni();
		char[] os = in.next().toCharArray();
		for(int i = n-1;i >= 0;i--){
			if(os[i] == 'F'){
				for(int j = i+1;j < i+20 && j < n;j++){
					assert os[j] == 'N';
					os[j] = 'F';
				}
			}
		}
		
		State init = new State();
		
		Comparator<State> comp = (x, y) -> Long.compare(x.has, y.has);
		PriorityQueue<State> beam = new PriorityQueue<>(comp);
		beam.add(init);
		
		// TODO 速度がいくらなんでもおそすぎる
		for(int i = 0;i < n;i++){
//			tr(i, beam.size(), beam.peek().has);
			char o = os[i];
			Set<Long> cache = new HashSet<>();
			final int ii = i;
			Comparator<State> compz = (x, y) -> Long.compare(x.has + x.pro() * (n-1-ii), y.has + y.pro() * (n-1-ii));
			PriorityQueue<State> nbeam = new PriorityQueue<>(compz);
			for(State s : beam){
				// click
				{
					State ns = new State(s);
					long plus = ns.pro() + (1L<<ns.clv);
					ns.o = 0;
					ns.add(plus, o);
					add(ns, nbeam, cache);
				}
				// buy
				for(int j = 0;j < 5;j++){
					long price = s.fs[j].buy();
					if(o == 'S'){
						price = (price * 90 + 99)/100;
					}
					if(s.has >= price){
						State ns = new State(s);
						ns.o = 1+j;
						ns.has -= price;
						ns.fs[j].num++;
						ns.add(ns.pro(), o);
						add(ns, nbeam, cache);
					}
				}
				// reinforce
				for(int j = 0;j < 5;j++){
					if(s.fs[j].num > 0){
						long price = s.fs[j].reinforce();
						if(o == 'S'){
							price = (price * 90 + 99)/100;
						}
						if(s.has >= price){
							State ns = new State(s);
							ns.o = 9+j;
							ns.has -= price;
							ns.fs[j].lv++;
							ns.add(ns.pro(), o);
							add(ns, nbeam, cache);
						}
					}
				}
				// enhclick
				{
					long price = 15L;
					for(int j = 0;j < s.clv;j++){
						price *= 10;
					}
					if(o == 'S'){
						price = (price * 90 + 99)/100;
					}
					if(s.has >= price){
						State ns = new State(s);
						ns.has -= price;
						ns.o = 8;
						ns.clv++;
						ns.add(ns.pro(), o);
						add(ns, nbeam, cache);
					}
				}
			}
			beam = nbeam;
		}
		
		State best = null;
		while(!beam.isEmpty()){
			best = beam.poll();
		}
		
		if(DEBUG){
			tr("score", best.has);
		}
		int[] route = new int[n];
		for(int i = n-1;i >= 0;i--){
			route[i] = best.o;
			best = best.prev;
		}
		
		if(DEBUG){
			for(int i = 0;i < n;i++){
				if(route[i] != 0){
					int v = route[i];
					out.print(i + ": ");
					if(v <= 5){
						out.println("buy " + init.fs[v-1].f.name);
					}else if(v == 8){
						out.println("enhclick");
					}else{
						out.println("reinforce " + init.fs[v-8-1].f.name);
					}
				}
			}
		}else{
			for(int v : route){
				if(v == 0){
					out.println("click");
				}else if(v <= 5){
					out.println("buy " + init.fs[v-1].f.name);
				}else if(v == 8){
					out.println("enhclick");
				}else{
					out.println("reinforce " + init.fs[v-8-1].f.name);
				}
				out.flush();
				String res = in.next();
				if(res.equals("-1") || res.equals("-2")) {
				}else if(!res.equals("ok")){
					throw new RuntimeException();
				}
			}
		}
	}
	
	static int ct = 0;
	
	static void add(State s, PriorityQueue<State> beam, Set<Long> cache)
	{
		ct++;
		long h = s.h();
		if(!cache.add(h))return;
		beam.add(s);
		if(beam.size() > W)beam.poll();
	}
	
	// click
	// buy
	// reinforce
	// enhclick
	
	public static class Facility
	{
		String name;
		long base; // 基本生産量
		long price; // 基本価格
		public Facility(String name, long base, long price) {
			this.name = name;
			this.base = base;
			this.price = price;
		}
	}
	
	public static class OneF
	{
		Facility f;
		int lv; // 0
		int num;
		
		public OneF(OneF o)
		{
			f = o.f;
			lv = o.lv;
			num = o.num;
		}
		
		public OneF(Facility f)
		{
			this.f = f;
			lv = 0;
			num = 0;
		}
		
		long buy()
		{
			long p = f.price;
			for(int i = 0;i < num;i++){
				p = (p*6+4)/5;
			}
			return p;
		}
		
		long reinforce()
		{
			long p = f.price;
			for(int i = 0;i <= lv;i++){
				p *= 10;
			}
			return p;
		}
	}
	
	public static class State
	{
		OneF[] fs;
		int clv;
		long has;
		State prev;
		int o;
		
		public State()
		{
			o = -1;
			fs = new OneF[5];
			fs[0] = new OneF(new Facility("hand", 1, 150));
			fs[1] = new OneF(new Facility("lily", 10, 2000));
			fs[2] = new OneF(new Facility("factory", 120, 30000));
			fs[3] = new OneF(new Facility("casino", 2000, 600000));
			fs[4] = new OneF(new Facility("grimoire", 25000, 10000000));
		}
		
		public State(State s)
		{
			prev = s;
			fs = new OneF[5];
			for(int i = 0;i < 5;i++)fs[i] = new OneF(s.fs[i]); // 必要なときにnewするようにする
			clv = s.clv;
			has = s.has;
		}
		
		long h()
		{
			long h = has;
			for(OneF f : fs){
				h = h * 1000000009 + f.lv;
				h = h * 1000000009 + f.num;
			}
			h = h * 1000000009 + clv;
			return h;
		}
		
		long pro()
		{
			long ret = 0;
			for(OneF f : fs){
				ret += (f.f.base<<f.lv) * f.num;
			}
			return ret;
		}
		
		void add(long x, char o)
		{
			if(o == 'F')x *= 7;
			has += x;
			if(o == 'B')has = has + (has + 99) / 100;
		}
	}
	
//	public static class SL {
//		long[] a;
//		int w = 0; // width
//		int p = 0; // index pointer
//		int b = 0; // bit pointer
//		int sz = 0; // size
//		
//		public SL(SL o) {
//			this.p = o.p;
//			this.w = o.w;
//			this.b = o.b;
//			this.sz = o.sz;
//			a = Arrays.copyOf(o.a, o.a.length);
//		}
//		public SL(int n, int w) { a = new long[n*w/64+1]; sz = 0; this.w = w; }
//		public SL add(int n)
//		{
//			if(p+1 >= a.length && b+w >= 64 || p >= a.length)a = Arrays.copyOf(a, a.length*3/2+1);
//			for(int i = 0;i < w;i++){
//				if(n<<~i<0)a[p] |= 1L<<b;
//				if(++b >= 64){
//					b -= 64;
//					p++;
//				}
//			}
//			sz++;
//			return this;
//		}
//		public int size() { return sz; }
//		public SL clear() { p = 0; sz = 0; b = 0; return this; }
//		public int[] toArray() {
//			int[] ret = new int[sz];
//			int lp = 0, lb = 0, lsz = 0;
//			while(lp < p || lp == p && lb < b){
//				for(int i = 0;i < w;i++){
//					if(a[lp]<<~lb<0)ret[lsz] |= 1<<i;
//					if(++lb >= 64){
//						lb -= 64;
//						lp++;
//					}
//				}
//				lsz++;
//			}
//			return ret;
//		}
//	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		tr(System.currentTimeMillis() - S + "ms");
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static long nl() { return Long.parseLong(in.next()); }
	static double nd() { return Double.parseDouble(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード