Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 336 LikelyWord

|  SRM 336 LikelyWord - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 336 LikelyWord - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7351

  • 辞書順でdictionaries[i]の前に来る、長さkの文字列を数え上げる。
    • 区間は引き算して求められる
      • この時、dictionaries[i]の文字数がkであった場合、あとで数えないようにフラグを立てておく
    • 最後の区間は 26^k から (dictionaries[len-1] の前に来る文字列数) を引いて求める
public class LikelyWord {
	public int likely(String[] dic, int k) {
		int len = dic.length;
		
		long[] pow26 = new long[11];
		pow26[0] = 1;
		for (int i = 1 ; i < 11 ; i++) {
			pow26[i] = pow26[i-1] * 26;
		}
		
		long total = pow26[k];
		long best = -1;
		int bestidx = -1;
		boolean sameflg = false;
		long prev = 0;
		long mflg = 0;
		System.out.println("total:" + total);
		for (int i = 0 ; i < len ; i++) {
			int sl = dic[i].length();
			long cnt = 0;
			for (int d = 0 ; d < Math.min(k, sl) ; d++) {
				int prevch = dic[i].charAt(d) - 'a';
				cnt += prevch * pow26[k-d-1];
			}
			if (sl > k) {
				cnt++;
			}
			long sc = cnt - prev - mflg;
			if (sl == k) {
				mflg = 1;
			} else {
				mflg = 0;
			}
			System.out.println(sc);
			if (best < sc) {
				best = sc;
				bestidx = i;
				sameflg = false;
			} else if (best == sc) {
				sameflg = true;
			}
			prev = cnt;
		}

		long last = total - prev - mflg;
		System.out.println(last);
		if (best < last) {
			return len;
		} else if (best == last) {
			sameflg = true;
		}
		return sameflg ? -1 : bestidx;
	}
}