TopCoder SRM562 (no contests) ポップン41が残1へ。
1問目、任意の予算があって、値段の違うきゅうりが複数売っている。
任意の個数選ぶときに、必ず買えるかどうかを判定せよ。
高い順にソートして、任意の個数を高い順から選んで、それが予算内か見るだけ。
import java.util.Arrays;
public class CucumberMarket {
public String check(int[] price, int budget, int k) {
Arrays.sort(price);
int sum = 0;
for(int i = price.length-1 ; i >= price.length-k ; i--){
sum += price[i];
}
System.out.println(sum);
if(budget >= sum)return "YES";
return "NO";
}
}
2問目は、無限のフィールドに、ある形にペイントすると。
それを任意の回数行なって、i,i(i>=0 i ∈ N)座標を左上にして、塗り重ねる。
その時の塗り重なっている個数を求める。
ある一定のところまで塗り重ねると、個数が固定される部分が出てくるので、
そこの合計を足し合わせる。ちょっと複雑な問題。
System Test通っていたので掲載。
import java.util.ArrayList;
public class PastingPaintingDivTwo {
public long countColors(String[] clipboard, int T) {
int dbr = 0;
boolean[][] newcrack = new boolean[clipboard.length][clipboard[0].length()];
ArrayList
for(int k = 1 ; k < clipboard.length ; k++){
for(int i = 0 ; i < clipboard.length-k ; i++){
for(int j = 0 ; j < clipboard[i].length()-k ; j++){
if(!newcrack[i][j] && clipboard[i].charAt(j) == 'B' && clipboard[i].charAt(j) == clipboard[i+k].charAt(j+k)){
newcrack[i][j] = true;
dbr++;
}
}
}
initial.add(dbr);
}
long count = 0;
for(int i = 0 ; i < clipboard.length ; i++){
for(int j = 0 ; j < clipboard[i].length() ; j++){
if(clipboard[i].charAt(j) == 'B')count++;
}
}
long sum = count;
if(T == 1)return sum;
for(int i = 0 ; i < initial.size()-1; i++){
sum += count-initial.get(i);
if(T == i+2)return sum;
}
if(initial.size() != 0){
long rest = count-initial.get(initial.size()-1);
sum += rest*(T-initial.size());
System.out.println(count);
}else{
long rest = count;
sum += rest*(T-1);
}
return sum;
}
}
hardは時間ないのでときませんでした。
ビーマニの乱かけたときのあたり譜面の確率みたいな感じ。
順位は92位/900人中といった感じで絶好調だったのですが、
challenge phaseでバグがあっただけで、no contestsに。残念。
夕方からはpop'n の残りの41埋め。
カグランジとトランスコア。
粘着の末埋まった。
トランスコアは、コメントの「タンタカタンタン」を覚えてから2回目でクリアに。
最後は見えないけどね・・・。
後は点数低いですが、万物快楽理論でまさかの同点。
by ddrer-yossi | 2012-12-01 23:28 | TopCoder