Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

Google Code Jam Qual.

A-small/large
B-small/large
C-small/large1まで解いて115点でした。

A

やるだけ

B

逆順に考えていく。

1,最小値を調べる
2,全ての最小値のセルを調べる
3,任意の最小値のセルが、(すべてのセルが最小値であるような行または列)に含まれているか調べる。
含まれていないセルがあれば作成不能
4,全ての最小値のセルに+1、最小値が100になれば終了、そうでなければ2へ

実際には4のincrementは2番目に小さい値に増やしてもよいとか、
終了条件は全てのセルが同じ長さになればそこで打ち切ってよいとか。

int n,m;

int findMin(vector<vector<int> > f){
    int ret = (1ll << 31) - 1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            ret = min(ret, f[i][j]);
        }
    }
    return ret;
}



int main(){
    int cases;

    cin >> cases;
    for(int x=0;x<cases;x++){
        bool ret = true;
        cin >> n >> m;
        vector<vector<int> > f(n, vector<int>(m, 0));
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cin >> f[i][j];
            }
        }
        while(1){
            vector<vector<int> > minMap(n, vector<int>(m, 0));
            vector<vector<int> > mask(n, vector<int>(m, 0));
            int min = findMin(f);
            if(min == 100) break;
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(f[i][j] == min){
                        minMap[i][j] = 1;
                    }
                }
            }
            //for each rows
            for(int i=0;i<n;i++){
                bool isok = true;
                for(int j=0;j<m;j++){
                    if(f[i][j] != min){
                        isok = false;
                        break;
                    }
                }
                if(isok){
                    for(int j=0;j<m;j++){
                        mask[i][j] = 1;
                    }
                }
            }
            //for each cols;
            for(int i=0;i<m;i++){
                bool isok = true;
                for(int j=0;j<n;j++){
                    if(f[j][i] != min){
                        isok = false;
                        break;
                    }
                }
                if(isok){
                    for(int j=0;j<n;j++){
                        mask[j][i] = 1;
                    }
                }
            }
            //compare minMap and mask
            bool isok = true;
            for(int i=0;i<n && isok ;i++){
                for(int j=0;j<m && isok ;j++){
                    if(minMap[i][j] != mask[i][j]){
                        isok = false;
                    }
                }
            }
            if(isok){
                for(int i=0;i<n;i++){
                    for(int j=0;j<m;j++){
                        if(f[i][j] == min) f[i][j]++;
                    }
                }
            }else{
                ret = false;
                break;
            }
        }
        cout << "Case #" << x+1 << ": ";
        if(ret == true){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
}

C

事前に全探索しておけば各クエリに対してlog(palindrome and squareの個数)で答えられる

vector<ll> ps;

bool isPs(ll arg){
    int n = ceil(log10(arg+1)) + 1, cnt = 0;
    char str[n];
    while(arg > 0){
        str[cnt] = arg % 10 + '0';
        arg /= 10;
        cnt++;
    }
    for(int i=0;i<cnt/2;i++){
        if(str[i] != str[cnt-1-i]){
            return false;
        }
    }
    return true;
}

int main(){
    int cases;
    ll tmp;
    cin >> cases;
    for(int i=0;i<1000000001;i++){
        if(isPs(i)){
            tmp = (ll)i*i;
            if(isPs(tmp)){
                cerr << i << " * " << i << " = " << tmp << endl;
                ps.push_back(tmp);
            }
        }
    }
    cerr << "calc end" << endl;
    for(int x=1;x<=cases;x++){
        ll a,b;
        cin >> a >> b;
        printf("Case #%d: %d\n", x, upper_bound(ps.begin(),ps.end(), b) - lower_bound(ps.begin(), ps.end(), a));
    }
}

C++で全列挙したら0,1,2で構成されるpalindrome数の2乗がpalindromeかつsquareになりそうだったので事前に3^25ぐらい列挙するのかなぁと思ったけどpythonで多倍長使ってごりごりやってたら
間に合いそうになかったので諦めました。

D

問題読んでません…