日記日和。 TopCoder SRM604

今日も日記をひたすら書いていました。7月分一杯を書き上げた。

昼ごろにふと艦これで3-4出撃したところ、あっさり1回でボスに到達。
昨日は1回も行かなかったのに…。

日記日和。 TopCoder SRM604_f0019846_1922251.png


クロスビーツはようやくHEADPHONE PARTYを解禁した。
2chスレの解析班お疲れ様です。

ひたすら書いた後に22時にゲーセンへ。
まほろば教のリベンジを主に行っていった。

日記日和。 TopCoder SRM604_f0019846_19235952.jpg

ちがうんだよなー…。

日記日和。 TopCoder SRM604_f0019846_19244213.jpg

なんとかぎりぎり。 95.0% AAA+ フルコン

これで後は麻雀とChalonだけだ。

ということで余ったところでChalonをやる。
日記日和。 TopCoder SRM604_f0019846_19254513.jpg

こっちはあっさり。 95.9% AAA+

日記日和。 TopCoder SRM604_f0019846_19262773.jpg

麻雀もやってみた。93.2%。あれ、十分戦えるぞ・・・?

そして閉店間際のポップンも忘れずに。
日記日和。 TopCoder SRM604_f0019846_19271059.jpg

演説(H) miss1。どうでもいいところでミスったので結構つらい。

帰宅後はSRMに参加。

Easyは、文字列の配列が与えられていて、
ある文字列をa+bに分けて、b+aにしたときに、
他の文字列と一致するといった組み合わせがいくつあるか出力せよという問題。

文字を2回繰り返して一致するか見るのもいいが、
これだと長さが一致しない場合は弾かないとアウトになる。

よって、調べる側を固定して、片方の文字列をそれぞれのところで分割したときに、
一致するかどうかを愚直に調べるのが良い。文字数も50文字程度で、
配列も50程度なので、最大でも(50*49)/2*50である。O(n^3)


public class FoxAndWord {

public int howManyPairs(String[] words) {
int count = 0;
for(int i = 0 ; i < words.length ; i++){
for(int j = i+1 ; j < words.length ; j++){
boolean istrue = false;
for(int k = 0 ; k <= words[i].length(); k++){
String a = words[i].substring(0,k);
String b = words[i].substring(k,words[i].length());
String str = b+a;
if(str.equals(words[j])){
istrue = true;
break;
}
}
if(istrue)count++;
}
}
return count;
}

}


mediumは、0,0の位置から、+1,+3,+9,+27とどっちかに足していくとき、
x,yに到達可能かどうか調べよという問題。
ただし座標は10億以下。
10億以下なので、3^18までしかないため、
全部調べても2^18 = 262144か、余裕じゃんと思って、
BFSで書いてみて速攻提出。

Queue q = new LinkedList();
q.add(0+","+0+","+1+","+1);
boolean isok = false;
while(!q.isEmpty()){
String[] st = q.poll().split(",");
int stx = Integer.parseInt(st[0]);
int sty = Integer.parseInt(st[1]);
int adder = Integer.parseInt(st[2]);
int power = Integer.parseInt(st[3]);
if(stx == x && sty == y){
isok = true;
break;
}
if(stx+adder <= x && stx+adder <= 1000000000)q.add((stx+adder)+","+sty+","+(int)Math.pow(3, power)+","+(power+1));

if(sty+adder <= y && sty+adder <= 1000000000)q.add(stx+","+(sty+adder)+","+(int)Math.pow(3, power)+","+(power+1));
}
if(isok){
return "Possible";
}else{
return "Impossible";
}

が、最大ケースで調べてみてTLEすることが判明し、なんだよこれ…となる。
泣く泣く再帰で書き直し、再提出した。残念無念。


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

public class PowerOfThreeEasy {

public String ableToGet(int x, int y) {
System.out.println();
if(StringMaker(0,0,x,y,0) == 0){
return "Possible";
}else{
return "Impossible";
}
}


public int StringMaker(long sx,long sy,long x,long y,int pow){
if(sx == x && sy == y)return 0;
if(sx < x && sy < y){
return Math.min(StringMaker(sx+(int)Math.pow(3,pow),sy,x,y,pow+1),StringMaker(sx,sy+(int)Math.pow(3,pow),x,y,pow+1));
}else if(sx < x){
return StringMaker(sx+(int)Math.pow(3,pow),sy,x,y,pow+1);
}else if(sy < y){
return StringMaker(sx,sy+(int)Math.pow(3,pow),x,y,pow+1);
}else{
return 1;
}
}
}


チャレンジは+1/-2で±0。
1189->1183 最後のチャレンジミスらなければDiv1だったかもしれない。

  by ddrer-yossi | 2014-01-11 19:19 | TopCoder

<< リフレク10(AAA+)終了、... 早めにゲーセンに行って早めに帰... >>

SEM SKIN - DESIGN by SEM EXE