SRM456 DIV2

topcoder SRM

rate 954->1139.
もももももう少しで青色！！
部屋内1位でびっくりした。やったね。

250 - AppleWord

1つのa,2つ以上のp,1つのl,1つのe、という順番、数で構成されている文字列をAppleWordと呼ぶ。
文字列が渡されるので、それをAppleWordにしたい。文字列に対してできる操作は、文字を取り替えることだけ。文字を削除したり追加したりすることはできない。


そこで、与えられた文字列をAppleWordにするために変えなきゃいけない最小の文字数を返せ。っていう問題。
できない場合は-1を返す。


wordと同じ長さのAppleWordを作ってから比較して違う部分を数えた。
こんなことしないで普通に頭から見ていくだけでよかった。乙。

import java.util.*; 
public class AppleWord { 
    public int minRep(String word) { 
        int res = 0; 
        int len = word.length(); 
        if(len<5) return -1; 
        word = word.toLowerCase(); 
        char[] c = word.toCharArray(); 
        char[] d = new char[len]; 
        for(int i=0; i<len; i++){ 
            if(i==0) { 
                d[i]='a'; 
            } else if(i==len-2){ 
                d[i]='l'; 
            } else if(i==len-1){ 
                d[i]='e'; 
            } else{ 
                d[i]='p'; 
            } 
        } 
        for(int i=0; i<len;i++){ 
            if(c[i]!=d[i]) res++; 
        } 
        return res; 
    } 
}

500 - SilverDistance

将棋の銀がスタート地点からゴール地点に到達できる最小手数を返せ。って問題。シンプル！！


ゴールとスタートの差を取ってうんたらかんたら出来そうだったけど数学超絶苦手なぼくはとても危険な予感がしたので1手ずつうごかしました。
最大で2,000,000手だし問題ないはず。問題なかった。
dx,dy消し忘れたままsubmitしてた恥ずい

public class SilverDistance { 
    public int minSteps(int sx, int sy, int gx, int gy) { 
        int dx = gx-sx; 
        int dy = gy-sy; 
        int nx = sx; 
        int ny = sy; 
        int res = 0; 
        while(nx!=gx || ny!=gy){ 
            if(nx==gx && ny<gy) return res + gy-ny; 
            if(nx<gx){ 
                nx+=1; 
                if(ny<gy){ 
                    ny+=1; 
                } else { 
                    ny-=1; 
                } 
                res++; 
            } else { 
                nx-=1; 
                if(ny<gy){ 
                    ny+=1; 
                } else { 
                    ny-=1; 
                } 
                res++; 
            } 
        } 
        return res; 
    } 
}

英語だと銀はそのままSilverなのかー。
角とか飛車はどうなるんだろう、とちょっと気になった

1000

int[] sticksが与えられる。
sticksの要素数は棒の数で、要素は棒の長さ。
最大でC回、好きな棒を好きな長さで二分割できる。
分割作業が終わったら、棒を降順でソートした後にK番目の棒を選んでその長さを返せって問題。(Kは1から始まる)


わからない。
地道に最長のものを半分に割っていく方法で書いてみたけど例題4のケースですらやたら時間かかってむりぽ。
二分探索を使うらしいけどtop submissionを見ても何をやってるのかさっぱりでした！ヒャッハー！

SRM445 DIV2 過去問

topcoder SRM

300 - TheEncryptionDivTwo

ジョンはセキュリティの鬼です。
友達に手紙書きたいけど誰かに盗み見られたくないから暗号化したいらしいです。
アルファベットを別のアルファベットに置換する方法で暗号化します。文字列の先頭から、アルファベットの早い順に置換していきます。
例："hello" -> "abccd"
暗号化したい文字列が渡されるので、暗号化済みの文字列を返せ。って問題。

  • 文字を置換して、その先に今置換した文字と同じのがあったらそこも同じ文字に置換
  • 書いて実行したら結果がおかしい
  • 既に置き換えたところをまた置き換えてた
  • 初期値じゃなかったら置き換えないようにすればいいか
  • charの初期値ってなんだっけ・・・
  • わかんないので最初にArrays.fill()で適当に埋めとこう
public class TheEncryptionDivTwo {
    public String encrypt(String message) {
	int len = message.length();
	char[] c = message.toCharArray();
	char[] res = new char[len];
	//Arrays.fill(res, '0');
	char b = 'a';
	for(int i=0; i<len; i++){
	    //if(res[i]!='0') continue;
	    if(res[i]!=0)
		continue;
	    res[i] = b;
	    for(int j=i+1; j<len; j++)
		if(c[j]==c[i]) res[j] = b;
	    b++;
	}
        return new String(res);
    }
}

後で調べたらcharの初期値は0(\u0000)だったので変更。

500 - TheNewHouseDivTwo

ジョン、またお前か。
新しい家を建てたいけど、セキュリティの鬼であるジョンは東西南北それぞれの直線方向に1つ以上の古い家がある場所じゃないと安心できないらしいです。
古い家の場所がint x, int yで与えられるので、ジョンが安心して新しい家を建てることのできる場所の数を返せ。って問題。

  • 最初、4つの古い家に囲まれた場所でないとダメって読み違えて時間ロス。directlyを直接(隣接してる)って読んじゃったっぽい。正しくは"直線的に"でした。
  • 最大で200*200*50だし全部チェック。でも一番端っこは見る必要ないNE！
public class TheNewHouseDivTwo {
    public int count(int[] x, int[] y) {
        int res = 0;
        for(int i=-99; i<=99; i++){
	    for(int j=-99; j<=99; j++){
		boolean N=false, S=false, W=false, E=false;
	        for(int k=0; k<x.length; k++){
		    if(x[k]==j && y[k]<i) N = true;
		    if(x[k]==j && y[k]>i) S = true;
		    if(y[k]==i && x[k]<j) W = true;
		    if(y[k]==i && x[k]>j) E = true;
		}
		if(N&&S&&W&&E) res++;
	    }
	}
	return res;
    }
}