TopCoder SRM665。ラストジム。

今日はお昼はお高めな本マグロ丼。1000円Overの奴ですが格別です。
TopCoder SRM665。ラストジム。_f0019846_75517.jpg


早めに帰宅し、TopCoder SRM 665に参加。
Easyは、ある数より大きい数で100以下でxorを取って、
4と7だけの数にできるならその数を返せ、無理なら-1を返せという問題。
愚直実装でOK。やるだけ。


public class LuckyXor {

public int construct(int a) {
for(int i = a + 1 ; i <= 100 ; i++){
String v = String.valueOf(a ^ i);
boolean isok = true;
for(int j = 0 ; j < v.length(); j++){
if(v.charAt(j) == '4' || v.charAt(j) == '7'){

}else{
isok = false;
break;
}
}
if(isok)return i;
}
return -1;
}

}


mediumは始点と終点を4か7の辺でつないであって、
必ず1つの点が1つの辺で結ばれている状態のとき、
辺を1つ追加して、ループが出来るようにし、
そのループで4と7の数が同数になるとき、そのグループを出力せよという問題。
新しく追加する辺は4でも7でもどちらでもよい。

最低でも3つの点を繋いでいないと作れないことはわかる。
後はすべての点を始点としてO(N)、
幅探索ですべてを試して、行けそうな所で出力すればよい。


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class LuckyCycle {
public int[] getEdge(int[] edge1, int[] edge2, int[] weight) {
ArrayList[] list = new ArrayList[edge1.length + 1];
for(int i = 0 ; i < edge1.length + 1 ; i++){
list[i] = new ArrayList();
}
for(int i = 0 ; i < edge1.length ; i++){
list[edge1[i] - 1].add((edge2[i] - 1)+","+weight[i]);
list[edge2[i] - 1].add((edge1[i] - 1)+","+weight[i]);
}

for(int i = 0 ; i < edge1.length + 1 ; i++){
Queue q = new LinkedList();
q.add("-1"+","+i+","+0+","+0);
while(!q.isEmpty()){
String[] str = q.poll().split(",");
int kinsi = Integer.parseInt(str[0]);
int st = Integer.parseInt(str[1]);
int four = Integer.parseInt(str[2]);
int seven = Integer.parseInt(str[3]);

if((four+seven) >= 3 && Math.abs(four-seven) == 1){
if(four > seven){
return new int[]{(i + 1),(st+1),7};
}else{
return new int[]{(i + 1),(st+1),4};
}
}

for(int j = 0 ; j < list[st].size() ; j++){
String[] liststr = list[st].get(j).split(",");
if(Integer.parseInt(liststr[0]) != kinsi){
if(Integer.parseInt(liststr[1]) == 4){
q.add(st+","+liststr[0]+","+(four + 1)+","+seven);
}else{
q.add(st+","+liststr[0]+","+four+","+(seven+1));
}
}
}
}
}
return new int[]{};
}

}


hardは、4か7でしか構成されない2つの数を合わせて、
任意の数字である?を含んだある数を構成できるならその最小値を返せという問題。
桁数台で二分探索すればいいかなと思いましたが、
?が立ちはだかっていてそう簡単にはいかないようです。
TLE解しか作れなかったので終了。

Challenge Phaseは放置して、今日付けでもう行かないラストジムへ行きました。
最後のボクササイズを行い、ポイントアップチャレンジも有終の美を飾りました。
出ると思ってなかったですし、そもそももう行かないですけどね。
TopCoder SRM665。ラストジム。_f0019846_716176.png


ゲーセンは弐寺でドッキン☆サマーあばんちゅーる(A)を難。
途中のL.E.D地帯が難しいですね。
TopCoder SRM665。ラストジム。_f0019846_7173076.jpg


リフレクはPlaying With Fireを92.3%に更新
TopCoder SRM665。ラストジム。_f0019846_7175992.jpg


サンボルはぼくらしかしらない EXHAUSTをクリア。
TopCoder SRM665。ラストジム。_f0019846_7182926.jpg


その後にREVしようとしたら0時15分にはプレーできない状態だったので
諦めてサンボルに戻る。

TOXIC VIBRATION EXHAUSTをなんとかクリアへ。
TopCoder SRM665。ラストジム。_f0019846_7191361.jpg

  by ddrer-yossi | 2015-08-11 23:05 | TopCoder

<< 贅沢にも寿司。徒歩30分かけて... 誕生日。ボウリングとかアートア... >>

SEM SKIN - DESIGN by SEM EXE