2012-03 << 2012-04 >> 2012-05

2012-04-15 (日)

*Google Code Jam 2012 Qualification Round

A,B,CとDのsmallだけやる．Dのlargeは結構実装に時間がかかりそうな問題．解きたいけどQualification Roundだし，まぁいいか．20pt取ればよいらしい．

A,B,Cは飛行機の中と空港でバス待ってる間にやる．3Gk回線が遅くて提出も一苦労．Dは放置しようと思ったけど，スキーの後で見たら，smallだけ簡単だったのでやっておく．

B,Cはlargeとsmallの違いが良くわからないし，Dはもう別の問題と言って良いし，Aに至ってはsmallしか無い．largeとは何なのか．

A

Aはsmallしか無いっぽい．sampleのデータセットから変換テーブル作ると，qとzが含まれて無いので注意．問題文に出てくる．

確認は，smallのデータを食わせた結果を読んでみると安心できる．

#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    string g;
    cin >> N;

    char map[128] = {0};
    string gg = "qz ejp mysljylc kd kxveddknmc re jsicpdrysi rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd de kr kd eoya kw aej tysr re ujdr lkgc jv";
    string en = "zq our language is impossible to understand there are twenty six factorial possibilities so it is okay if you want to just give up";
    for (int i = 0;i < gg.size(); i++) {
        map[gg[i]] = en[i];
    }
    for (int i = 'a' ; i <= 'z' ; i++) {
        if (map[i] == 0) {
            cerr << "NOT FOUND " << (char)i << endl;
        }
    }
    
    cin.get(); // skip LF
    for (int i = 0; i< N; i++) {
        char g_[1024];
        cin.getline(g_,sizeof(g_));
        g = g_;
        
        string ans;
        for (int j=0; j < g.size(); j++) {
            ans.push_back(map[g[j]]);
        }
        cout << "Case #" << (i+1) << ": " << ans << endl;
    }
    return 0;
}

B

英語の読解問題？ただ，条件に合うやつを数えるだけ．

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T;
    cin >> T;
    
    for (int i = 0; i< T; i++) {
        int N,S,p;
        cin >> N >> S >> p;
        vector<int> tt;
        int sup = 0;
        int ans = 0;
        for (int j=0 ; j< N ; j++) {
            int t;
            cin >> t;
            tt.push_back(t);
            if (t >= p*3-2) {
                ans ++ ;
            } else if (sup < S && t > 1 && t<=28 && t >= p*3-4) { // min: 0 0 2 max: 8 10 10
                ans ++;
                sup ++;
            }
        }

        cout << "Case #" << (i+1) << ": " << ans << endl;
    }
    return 0;
}

C

桁を入れ替えて別の数作る．これもただ数えるだけか．桁数も少ないので全部見るだけ．

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    int T;
    cin >> T;

    for (int i = 0; i< T; i++) {
        int A,B;
        cin >> A >> B;
        int ans = 0;
        for (int n = A; n <= B; n++) {
            int dd = 1;
            while(dd<=n) {
                dd*=10;
            }
            dd /=10;
            set<int> ss;
            for (int d=10; d <= B; d*=10) {
                int m = n/d + (n%d)*dd;
                if (m > n && m <= B && ss.find(m) == ss.end()) {
                    ss.insert(m);
                    ans++;
                }
                dd/=10;
            }
            
        }

        cout << "Case #" << (i+1) << ": " << ans << endl;
    }
    return 0;
}

D(smallだけ)

smallの制約を見てみると，ただの長方形の部屋しか有り得ない設定なので，もう問題文とまったく別の問題になってる．反射の仕方とか深く考えず，合せ鏡で無限に繰り返されているパターンの中から条件に合う点を探していくだけ．どうせ最大の視界が50しか無いので，100*100の範囲の点全部に対してやる．

角度をもう少しうまく表現すれば綺麗にかけたな．

というわけで，smallだけやっておく．largeになってもどの点で反射するかが複雑になるだけで同じ方法でいい気はする．

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <cmath>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i< T; i++) {
        int w,h,d;
        int px,py;
        cin >> h >> w >> d;
        cin.get();
        for (int y=0;y<h;y++) {
            char s[256];
            cin.getline(s,sizeof(s));
            for (int x=0; x<w ; x++) {
                if (s[x]=='X') {
                    px = x; py = y;
                }
            }
        }
        vector<double> degs;
        for (int y=-55; y<55; y++) {
            for (int x=-55; x<55; x++) {
                if (x == 0 && y == 0) continue;
                int tx = (w-2)*x + ((x%2)?((w-2)-(px)):(px-1)) + 1;
                int ty = (h-2)*y + ((y%2)?((h-2)-(py)):(py-1)) + 1;
                
                if ( (tx-px)*(tx-px) + (ty-py)*(ty-py) <= d*d ) {
                    double d = atan2(tx-px*1.0,ty-py*1.0);
                    for (auto it=degs.begin(); it!=degs.end(); ++it) {
                        if (abs(*it-d) < 0.00000000000001) {
                            d = 99;
                            break;
                        }
                    }
                    if (d < 10.0) {
                        degs.push_back(d);
                    }
                }
            }
        }

        cout << "Case #" << (i+1) << ": " << degs.size() << endl;
    }
    return 0;
}
2012-03 << 2012-04 >> 2012-05