Google Code Jam 2012 Qual
GCJもさり気なく参加してました，Dはむりぽでした．
Problem A Speaking in Tongues
問題
アルファベットの集合からアルファベットの集合への全単射fによって定義されるような新言語がある．要するに，普通の英文Tと新言語f(T)が対応してる感じ．
サンプルを見ながら，英文を新言語に翻訳するプログラムを書け
考えたこと
サンプルから推測される関数fを使えば良いってことに最初気づかなかったが，それに気づいて以降はやるだけ．
コード
int main(){ int n_case; cin >> n_case; string line; getline( cin, line ); map<char,char> map_of_alphabet; map_of_alphabet['a'] ='y'; map_of_alphabet['b'] ='h'; map_of_alphabet['c'] ='e'; map_of_alphabet['d'] ='s'; map_of_alphabet['e'] ='o'; map_of_alphabet['f'] ='c'; map_of_alphabet['g'] ='v'; map_of_alphabet['h'] ='x'; map_of_alphabet['i'] ='d'; map_of_alphabet['j'] ='u'; map_of_alphabet['k'] ='i'; map_of_alphabet['l'] ='g'; map_of_alphabet['m'] ='l'; map_of_alphabet['n'] ='b'; map_of_alphabet['o'] ='k'; map_of_alphabet['p'] ='r'; map_of_alphabet['q'] ='z'; map_of_alphabet['r'] ='t'; map_of_alphabet['s'] ='n'; map_of_alphabet['t'] ='w'; map_of_alphabet['u'] ='j'; map_of_alphabet['v'] ='p'; map_of_alphabet['w'] ='f'; map_of_alphabet['x'] ='m'; map_of_alphabet['y'] ='a'; map_of_alphabet['z'] ='q'; for( int i = 0; i < n_case ; i++ ){ getline( cin, line ); int size = line.size(); for( int j = 0 ; j < size; j++ ){ if( line[j] >= 'a' && line[j] <= 'z' ){ line[j] = map_of_alphabet[line[j]]; } } cout << "Case #" << i+1 << ": " << line<<endl; } return 0; }
Problem B Dancing With the Googlers
問題
沢山のGooglerたちのダンスを３人の審査員が評価する．
各Googlerに対し審査員の得点が３以上離れることはなく，２離れている時にはsurprisingであるという．
評価したあとの合計点数とsurprisingな点を貰った人数S，入力pに対し
少なくとも一人からp以上の評価をもらっている人数が，最大で何人いるを応えよ．
考えたこと
点数のパターンが限られてる事に注目．
(a,a,a), (a,a+1,a+2),
(a,a,a+1),(a,a+2,a+2),
(a,a,a+2),(a,a+1,a+1),
各行が得点総和のmod 3が0,1,2の場合に対応する．
総和から「surprisingな点数でなくてもp以上の点数をもらえるもの」「surprisingにしたらp以上の点数がもらえるもの」を別に数え，Sとの整合性をとるだけでよさそう
コード
; int main(){ int n_case; cin >> n_case; int scores[101]; for( int i = 0 ; i < n_case ; i++ ){ int N,S,p; cin >> N >> S >>p; int possible=0; int surprise_possible=0; //not suprising... [a, a, a](a) or [a, a, a+1]...(a+1) or [a, a+1, a+1]...(a+1) //surprising... [a, a, a+2] or [a, a+1, a+2] or [a, a+2, a+2] for( int j = 0 ; j < N; j++ ){ cin >> scores[j]; if( scores[j]%3==0 ){ //[a,a,a] or [a-1,a,a+1] if( scores[j]/3 >= p ) possible++; else if( scores[j]/3 +1 >= p && scores[j]/3-1 >= 0 )surprise_possible++; } else if( scores[j]%3 == 1){ //[a,a,a+1] or [a-1, a+1, a+1] if( scores[j]/3+1 >= p ) possible++; } else{ //[a,a+1,a+1] or [a, a, a+2] if( scores[j]/3+1 >= p ) possible++; else if( scores[j]/3 + 2 >= p ) surprise_possible++; } } //cout << possible << "," << surprise_possible<< "," <<S << endl;; cout << "Case #" << i+1 << ": " << possible+min(surprise_possible,S)<<endl; } return 0; }
Problem C Recycled Numbers
問題
ある数のペア（a,b)がrecyclingであるとは，
a
考えたこと
a,bとa,cがrecyclingなら，b,cもrecyclingになる．
だからエラトステネスの篩っぽくガシガシやればよいだろう．
たしかA<=a
コード
int main(){ int n_case; cin >> n_case; bool checked[2000001]; for( int i = 0 ; i < n_case ; i++ ){ int A,B; cin >> A >> B; ll ans = 0; memset( checked, false, sizeof( checked ) ); for( int j = A ; j <=B ; j++ ){ if( checked[j] ) continue; else{ ll sum = 1; int l = length(j); int num = j; int mask=1; for( int k = 0 ; k+1 < l; k++ ){ mask *= 10;} checked[num] = true; for( int k = 0 ; k < l ; k++ ){ int bit = num/mask; num = (num-bit*mask)*10+bit; if( num < mask || num > B || num < A ) continue; if( !checked[num] ){ sum++; checked[num] = true; } } ans += sum*(sum-1)/2; } } cout << "Case #" << i+1 << ": " << ans << endl; } return 0; }
Problem D. Hall of Mirrors
問題
鏡が散りばめられた部屋がある．自分の位置も入力で示される
鏡は少し曇っているので，距離D（入力で与えられる）以内の光までしか自分には届かない．
自分の像がいくつ見えるか答えよ
考えたこと
鏡ってことは定番のmapをパタパタ折り返すアプローチなんだとは思うけれど…
効率の良い方法が思い浮かばないなあ．
終了後
効率良いもなにも距離D以内の格子点に対して逐一mapをパタパタ折り返す方法で良いらしい．光の交差点求めるところって誤差発生しないのだろうか…誰かのコード読んで綺麗な実装あったら書こうと思う．
