悲しみのTopCoder SRM648

今日はこの3日間(うち2日間)のログインボーナスを朝に1本食べました。
f0019846_150694.jpg


お昼はうな丼。
f0019846_150544.jpg


帰宅後はSRMに備える。
Div1奪還戦です。
しかしmediumで頭のおかしいアルゴリズムを考えてしまい、失敗に終わった。

easyはやるだけ。よく見ればMath.pow(2,x) * Kでできているのにテンパりすぎ。
コードも酷い。

public class KitayutaMart2 {

public int numBought(int K, int T) {
int count = 0;
while(T != 0){
if(count == 0){
T -= K;
}else if(count == 1){
T -= 2*K;
}else{
T -= Math.pow(2,count) * K;
}
count++;
}
return count;
}

}


mediumは、グラフがあり、あるノードを完全に削除したときに、
孤立するグラフの個数が増える場合のノードのペアの組み合わせの数を求める問題。
20程度なので、全部調べてUnion-findすればよい。
こんな簡単なのに何故思いつくのに時間がかかったのか。

public class Fragile2 {

public int countPairs(String[] graph) {
int sum = 0;
for(int i = 0 ; i < graph.length - 1 ; i++){
for(int s = i + 1 ; s < graph.length ; s++){
char[][] ch = new char[graph.length][graph.length];
for(int j = 0 ; j < ch.length ; j++){
for(int k = 0 ; k < ch.length ; k++){
ch[j][k] = graph[j].charAt(k);
}
}
int[] number = new int[graph.length];
int[] rank = new int[graph.length];
for(int n = 0 ; n < graph.length ; n++){
number[n] = n;
}

for(int j = 0 ; j < ch.length - 1 ; j++){
for(int k = j + 1 ; k < ch.length ; k++){
if(ch[j][k] == 'Y'){
int a = numberuni(number, j);
int b = numberuni(number, k);
if(rank[a] < rank[b]){
number[a] = b;
}else{
number[b] = a;
if(rank[a] == rank[b])rank[a]++;
}
}
}
}

int count = 0;
for(int n = 0 ; n < graph.length ; n++){
if(number[n] == n){
count++;
}
}

for(int j = 0 ; j < ch.length ; j++){
ch[i][j] = 'N';
ch[s][j] = 'N';
ch[j][i] = 'N';
ch[j][s] = 'N';
}

number = new int[graph.length];
rank = new int[graph.length];
for(int n = 0 ; n < graph.length ; n++){
number[n] = n;
}

for(int j = 0 ; j < ch.length - 1 ; j++){
for(int k = j + 1 ; k < ch.length ; k++){
if(ch[j][k] == 'Y'){
int a = numberuni(number, j);
int b = numberuni(number, k);
if(rank[a] < rank[b]){
number[a] = b;
}else{
number[b] = a;
if(rank[a] == rank[b])rank[a]++;
}
}
}
}

int count2 = 0;
for(int n = 0 ; n < graph.length ; n++){
if(number[n] == n && n != i && n != s){
count2++;
}
}
if(count2 > count)sum++;
}
}

return sum;
}

public static int numberuni(int[] nums,int x){
if(nums[x] == x){
return x;
}else{
return numberuni(nums,nums[x]);
}
}

}


hardは、難しい問題だったようで。
A 文字数N、強さを満たすものの組み合わせKを満たす文字列を求めよという問題。
ABCCCならAで4、Bで3なので7になる。

challengeで失敗し、レートは1197->1158。次回復帰を。

その後はジムに行く時間も残っていなかったのでゲーセンへ。

Army of Marionetteで95.3%
f0019846_1553142.jpg


寒すぎたのでポップンもかなりやりました。
IdolaでBAD39 銅●
f0019846_1555850.jpg


火風陸空 BAD36 銅●
f0019846_156222.jpg


Metamorphose BAD26 銅●
f0019846_1564266.jpg


クロスビーツはいいね!でついにS+達成。
後はどこどこ地帯をなんとかするだけ。がんばろう。

  by ddrer-yossi | 2015-02-02 23:49 | TopCoder | Comments(0)

<< 海鮮丼と恵方巻 cross beatsロケテ三日目 >>

SEM SKIN - DESIGN by SEM EXE