TopCoder SRM 416 div2

全体的にひどかった(自分が)。

250点問題

与えられた文字列の中の最頻出文字を辞書順に出力する。

public String listMostCommon(String[] text) {
	int freqs[]=new int['z'-'a'+1];
	int max_freq=0;
	for(String t:text) {
		for(int i=0;i<t.length();i++) {
			Character c=t.charAt(i);
			if(c==' ') continue;
			int idx=c-'a';
			freqs[idx]++;
			if(max_freq < freqs[idx]) max_freq=freqs[idx];;
		}
	}
	String res="";
	if(0 < max_freq) for(int i=0;i<freqs.length;i++) 
		if(freqs[i]==max_freq) res=res+new String(new byte[]{(byte)('a'+i)});
	return res;
}

文字コードから文字に変換する方法がわからなくて必死にぐぐってた。

• 文字コード用の配列を別に作れば逆変換の方法がわからなくてもいける
• freqs=new int[(int)'z'+1] とかすれば引き算しなくていい

500点問題

与えられた整数Nから、立ってるビットの数が同じでNより大きい最初の数を返す。

    public int getNextNumber(int N) {
    	System.out.println("N:"+N);
    	final int bits=32;
		int outer=-1;
		for(int i=bits-1;0<=i;i--) {
			if( (N&(1<<i))!=0 ){ outer=i; break; }
		}
    	int idx=-1;
    	for(int i=0;i<bits;i++) {
    		final int cur=1<<i;
    		final int nex=1<<(i+1);
    		if( (N&cur)!=0 && (N&nex)==0 ) { idx=i; break; }
    	}
    	System.out.println("idx:"+idx);
		if(idx<outer) {
			return (N|(1<<(idx+1)))&~(1<<idx);
		} else {
			int ones=0;
			for(int i=0;i<idx;i++) {
				if( (N&(1<<i))!=0 ) ones++;
			}
			System.out.println("ones:"+ones);
			int result=0;
			result|=(1<<(idx+1));
			for(int i=0;i<=idx;i++) {
				if(ones==0) return result;
				result|=(1<<i);
				ones--;
			}
		}
		return -1;
    }

試行錯誤のあとがたいへんみてとれますね、しかもSystem testで落ちたという。
0001のnext numberは0010、0100のnext numberは1000。01100のnext numberは10100じゃなく10001。
冷静に考えたら、ビット列が'01'になっている部分を'10'にして、それより前に存在する'1'を前にきっちり詰めればOK。冷静に考えられませんでした。
ビット操作するのにStringの配列にしたりvector<int>使ったり、みんな工夫してる。すごい人はそのまま「ハッカーのたのしみ」的テクニックで解いちゃうんだろうけど。
頭からnビット1にするのは~((~0)<<n)でOKかな。先頭nビットに立ってる1の数を数えるテクニックもあったような気がする。