SRM558 Div1 参加記

TopCoder
順位 得点 レーティング
256th 120.36 1594 -> 1631 +37
275 550 1000 Challenge
120.36 Open Unopen +0/-0

Easyしか解けなかったわけですが、周りの人がもりもりEasyを落としたので、350位くらいから250位近くに浮上してきました。不沈艦(?

Easy: Stamp

  • 概要

長さNのマスを、RGBの色を使って希望する色に塗りたい。マスは最初無色。
最初に使うスタンプの長さLを決める。これにはL * stampCostのコストがかかる。
次に、R、G、Bから一色を選び(Cとする)スタンプのインクとする。スタンプが押せる条件は、
押そうとしている領域全てが*かCであること
スタンプがマスをはみ出さないこと
既に押されている色がCであること
を満たすときである。1回押すごとにpushCostかかる。
希望の色の列にするための最小コストを求めよ。
1 <= N <= 50

  • 頭の中

Lは1〜N全て試そう
左端から順番に押して行こう
押した回数が少なければいいから、左から貪欲に多く押せるだけ押せばいいんじゃね？
書く
細かくバグる
修正
サンプル4でWA
あー、貪欲に押すとあかんわ
DPしよう
dp[ 押したスタンプの区間の右端 ][ そのときの色 ] -> 最小コスト
これを全てのLについて試せばいいだろう
書く
サンプル通る
提出

import java.util.Arrays;

public class Stamp {

	public int getMinimumCost(String desiredColor, int stampCost, int pushCost){
		int n = (desiredColor).length();
		desiredColor = "*"+desiredColor;
		char[] color = {'R','G','B'};
		int INF = 1<<29;
		int res = INF;
		char[] s = desiredColor.toCharArray();
		for(int L=1;L<=n;L++){
			int[][] dp = new int[n+1][3];
			for(int[]d:dp)Arrays.fill(d, INF);
			dp[0][0] = dp[0][1] = dp[0][2] = L*stampCost;
			for(int t=L;t<=n;t++)for(int c=0;c<3;c++){
				boolean ok = true;
				for(int i=t;i>t-L;i--)if(s[i]!=color[c] && s[i]!='*')ok=false;
				if(!ok)continue;
				for(int pre=0;pre<3;pre++){
					dp[t][c] = Math.min(dp[t][c], dp[t-L][pre]+pushCost);
				}
				for(int i=t-L+1;i<t;i++)dp[t][c] = Math.min(dp[t][c], dp[i][c]+pushCost);
			}
			res = Math.min(res, (Math.min(dp[n][0], Math.min(dp[n][1], dp[n][2]))));
			System.out.println("L:"+L+" "+res);
		}
		System.out.println(res);
		return res;
	}
	
	public static void main(String[] args) {
		new Stamp().getMinimumCost("*B**B**B*BB*G*BBB**B**B*", 5, 2);
	}
}

medを読むが残り時間の少なさでやる気が無くなったのでぼーっとしてた

  • 反省

貪欲解法を思い付いて実装に時間食って挙句解法が間違ってて本当に時間のムダ。
サンプル4に目を通して、且つ、手計算できる大きさだったので手を動かしていればすぐDPへ切り替えられた。サンプルに全部目を通すことで防ぐことができるミスをなくそうと思う