kmjp's blog

競技プログラミング参加記です

TopCoder SRM 560 Div1 Easy TomekPhone

このSRM、まさかのDiv1で11位と絶好調。
Mediumが順調に解けたのが良かった。
そんな中まずは1問目。
http://community.topcoder.com/stat?c=problem_statement&pm=12296

携帯電話の様に、あるアルファベットを出すのに同じキーを何度か押す必要があるキーボードを考える。
各アルファベットの出現頻度と、各キーの最大割り当て文字数があるときに、総キー打鍵数を減らす。

…この問題、どこかで見たことがある。
そうhttp://kmjp.hatenablog.jp/entry/2012/10/17/235037:GCJ R1CのAとほぼ同じ。
打鍵数の多いアルファベットから順に1キー、2キー…で押せば文字が出るように割り当てていく。


元々難易度が低く、これは正答率9割越え。230点以上取ってる人も多数。
Div2 Mediumにもなってたけど、Div2でも8割以上正解していた。
実際アリーナでも「これ250じゃなくて225点でいいんじゃないの?」と言われていた。

class TomekPhone {
	public:
	int minKeystrokes(vector <int> occurences, vector <int> keySizes) {
		int nk=0,tk;
		int i,j;
		sort(occurences.begin(),occurences.end());
		reverse(occurences.begin(),occurences.end());
		sort(keySizes.begin(),keySizes.end());
		reverse(keySizes.begin(),keySizes.end());
		FOR(i,keySizes.size()) nk+=keySizes[i];
		if(nk<occurences.size()) return -1;
		
		int loop=1;
		int cp=0;
		tk=0;
		FOR(i,occurences.size()) {
			
			tk += loop*occurences[i];
			cp++;
			if(cp>=keySizes.size() || loop > keySizes[cp]) {
				cp=0;loop++;
			}
		}
		return tk;
	}

};

まとめ

まさかGCJと同じような問題が出るとは思わなかった。
回答だけじゃなく問題設定もかなり似てるしね。