SRMの過去問を解きたい

2012-01-27

SRM 159 DIV2 250

public class StreetParking {
	public int freeParks(string street) {
		int c = 0;
		for(int i=0; i<street.Length; i++) {
			if (i+2 < street.Length && street[i+2] == 'B') {
				continue;
			} else if (i+1 < street.Length && street[i+1] == 'S') {
				continue;
			} else if (i+1 < street.Length && street[i+1] == 'B') {
				continue;
			} else if (i > 0 && street[i-1] == 'S') {
				continue;
			} else if (street[i] == '-') {
				c++;
			}
		}
		return c;
	}
}

書くだけ。

おまけ

正規表現で

public class StreetParking {
	public int freeParks(string street) {
		return System.Text.RegularExpressions.Regex.Replace(street, @"(-?[D-]?B|-?S-?|D)","").Length;
	}
}

Permalink | コメント(0) | トラックバック(0) | 11:04

2012-01-19

SRM 157 DIV2 250

public class GuessTheNumber {
	public int noGuesses(int upper, int answer) {
		int lower, x, guess;
		lower = 1;
		guess = 0;
		do {
			x = (lower + upper) / 2;
			if (x < answer) { lower = x + 1; }
			else if (x > answer) { upper = x - 1; }
			guess++;
		} while (x != answer);
		return guess;
	}
}

問題のアルゴリズム通りに書くだけだった。

Permalink | コメント(0) | トラックバック(0) | 23:09

SRM 156 DIV2 250

public class DiskSpace {
	public int minDrives(int[] used, int[] total) {
		for(int i=1;i<used.Length;i++) {
			used[0] += used[i]; // amount size
		}
		// but sort (降順)
		for (int i=0; i<total.Length-1;i++) {
			for (int k=total.Length-1; k>i; k--) {
				if (total[k-1] < total[k]) {
					used[1] = total[k];
					total[k] = total[k-1];
					total[k-1] = used[1];
				}
			}
		}
		
		for(int i=0;i<total.Length;i++) {
			used[0] -= total[i];
			if (used[0] <= 0) { return i+1; }
		}
		return 1;
	}
}

バブルソートの書き方わすれてた。

C#で降順ソート

		System.Array.Sort(total);
		System.Array.Reverse(total);

昇順ソートしてから逆順。ラクだね。

Permalink | コメント(0) | トラックバック(0) | 03:39

2012-01-17

SRM 155 DIV2 250

public class Quipu {
	public int readKnots(string knots) {
		int a = 0;
		string result = "";
		for(int i=1;i<knots.Length; i++) {
			if (knots[i] == '-') {
				result += (i - a - 1).ToString();
				a = i;
			}
		}
		return int.Parse(result);
	}
}

ちょっと残念な感じ。

Permalink | コメント(0) | トラックバック(0) | 21:26

SRM 154 DIV2 300

public class ProfitCalculator {
	public int percent(string[] items) {
		float total_cost, total_price;
		total_cost = total_price = 0;
		foreach(string item in items) {
			string[] spr = item.Split(' ');
			total_price += float.Parse(spr[0]);
			total_cost += float.Parse(spr[1]);
		}
		return (int)(((total_price - total_cost) / total_price) * 100);
	}
}

C#のキャストでfloatからintに変換すると単純に小数点以下切捨て。*1

Permalink | コメント(0) | トラックバック(0) | 11:51

*1：C++でも同じ

2012-01-16

SRM 153 DIV2 250

public class MostProfitable {
	public String bestItem(int[] costs, int[] prices, int[] sales, String[] items) {
		int max_profit = 0;
		String result = "";
		for(int i=0;i<costs.length;i++) {
			costs[i] = (prices[i] - costs[i]) * sales[i];
			if (costs[i] > max_profit) {
				max_profit = costs[i];
				result = items[i];
			}
		} 
		return result;
	}
}

costs（原価）に総利益を代入してみたり。

Permalink | コメント(0) | トラックバック(0) | 17:52

2012-01-15

SRM 151 DIV2 250

public class PrefixCode {
	public string isOne(string[] words) {
		for (int i=0;i<words.Length;i++) {
			for (int k=0;k<words.Length;k++) {
				if (i != k && words[i].Length < words[k].Length) {
					bool chk = true;
					for (int ic=0;ic<words[i].Length;ic++) {
						if (words[i][ic] != words[k][ic]) {
							chk = false;
						}
					}
					if (chk) {
						return "No, " + i;
					}
				}
			}
		}
		return "Yes";
	}
}

ネストの限界。

String.StartsWith()を使ったら

public class PrefixCode {
	public string isOne(string[] words) {
		for (int i=0;i<words.Length;i++) {
			for (int k=0;k<words.Length;k++) {
				if (i!=k && words[k].StartsWith(words[i])) {
					return "No, " + i;
				}
			}
		}
		return "Yes";
	}
}

Permalink | コメント(0) | トラックバック(0) | 15:48

SRM 150 DIV2 250

public class WidgetRepairs {
	public int days(int[] arrivals, int numPerDay) {
		int stock = 0;
		int day = 0;
		for(int i=0;i<arrivals.length;i++) {
			stock += arrivals[i];
			if (stock != 0) {
				stock -= numPerDay;
				day++;
				if (stock<0) { stock = 0; }
			}
		}
		while(stock>0) {
			stock -= numPerDay;
			day++;
		}
		return day;
	}
}

そういえば

		while(stock>0) {
			stock -= numPerDay;
			day++;
		}

ここは

		day += stock / numPerDay;
		if (stock % numPerDay != 0) { day++; }

こう書けた。

Permalink | コメント(0) | トラックバック(0) | 14:49

SRM 149 DIV2 250

public class FormatAmt {
	public String amount(int dollars, int cents) {
		String result = "";
		// dollars
		String ds = String.valueOf(dollars);
		for(int i=1; i<=ds.length(); i++) {
			result = ds.charAt(ds.length()-i) + result ;
			if (i%3==0 && i!= ds.length()) {
				result = "," + result;
			}
		}
		// cents
		result += '.';
		if (cents < 10) {
			result += '0';
		}
		result += String.valueOf(cents);
		return '$' + result;
	}
}

Permalink | コメント(0) | トラックバック(0) | 13:52