この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と同じような問題が出るとは思わなかった。
回答だけじゃなく問題設定もかなり似てるしね。