Google Code Jam 2020 Round 1A 参加記

Google Code Jam 2020 Round 1Aに参加しました。

A - Pattern Matching
B - Pascal Walk
C - Square Dance

abしか解けませんでした。精進します。

f:id:coonevo:20200411170416p:plain — 順位表

A - Pattern Matching

各文字列を $*$ でsplitし、最初と最後の要素、つまりprefixとsuffixに注目して議論します。prefixは、最も長さの長い文字列に対して、他の文字列を一致しない箇所があるかどうかを判定します。あれば、当てはまる文字列はありません。 suffixも文字列を反転して同様に処理します。

prefixとsuffix以外ですが、どのように並べても条件を満たします。

コンテスト中は $*$ が2つ以上あるときの処理がわかっていませんでした。 $*$ に挟まれた場合は前後はどのようになってもいいということなので、適当に並べても良いということに気付きたかったです。

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

int N;
vec<string> S;
vvec<string> A;
string match(vector<string>& B){
    string maxst = "";
    rep(i,B.size()){
        if(maxst.size() < B[i].size()){
            maxst = B[i];
        }
    }
    bool ok = true;
    rep(j, maxst.size()){
        rep(i,N){
            if(j >= (int)B[i].size())continue;
            if(maxst[j] != B[i][j])ok = false;
        }
    }
    return ok ? maxst: "-";
}

void Case(int t){
    cout << "Case #" << t << ": ";
}
void input(){
    cin >> N;
    S.resize(N);
    A.assign(N, vec<string>());
    rep(i,N){
        cin >> S[i];
        S[i].push_back('*');
    }
}
void solve(){
    input();
    string ans[3] = {"", "", ""};
    rep(i,N){
        string tmp = "";
        for(auto c: S[i]){
            if(c == '*'){
                A[i].push_back(tmp);
                tmp = "";
            }
            else tmp.push_back(c);
        }
    }
    //prefix
    {
        vector<string> x;
        rep(i,N)x.push_back(A[i].front());
        ans[0] = match(x);
    }
    //suffix 
    {
        vector<string> x;
        rep(i,N)x.push_back(A[i].back());
        rep(i,N)reverse(all(x[i]));
        ans[2] = match(x);
        reverse(all(ans[2]));
    }
    //middle
    {
        rep(i,N){
            for(int j = 1; j < (int)A[i].size()-1;j++){
                for(auto &c: A[i][j]){
                    ans[1].push_back(c);
                }
            }
        }
    }
    if(ans[0] == "-"|| ans[2] == "-"){
        cout << "*" << endl;
    }
    else{
        cout << ans[0] << ans[1] << ans[2] << endl;
    }
}
int main() {
    
    int t;
    cin >> t;
    rep1(i, t+1){
        Case(i);
        solve();
    }
}

和が $N$ になるようにパスカルの三角形上を動く問題。パスカルの三角形の行の和が二冪であることを利用して、 $N$ を表そうとする。ただし、その行にたどり着くまでに無駄な値が足されてしまう。ここで、直接 $N$ に合わせようとすると和が多くなってしまうことを考えれば、少し小さい値で揃えて、あとで辻褄を合わせれば良いのではないかと考えられる。移動できるマスの数が500であるが、30行目までのマスの総数は $\frac{30 * (30+1)}{2} = 465$ なので、仮に全て使ったとしても、余分に35回下に潜ることができる。このことを利用して、あらかじめ34を $N$ から引いておき、そのbit表現によって移動方法を決め、最後に左か右の $1$ を使って辻褄を合わせる。

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define bit(k) (1LL<<(k))
typedef long long ll;

void solve(){
    ll N;
    cin >> N;
    if(N <= 500){
        rep1(i,N+1){
            cout << i << " " << 1 << endl;
        }
        return;
    }
    ll tmpN = N - 34;
    ll sum = 0;
    int r = 0;
    vector<pair<int, int>> ans;
    ans.push_back({0,0});
    sum++;
    for(int i = 1; i <= 30;i++){
        //i行目を走査するかどうかを決める
        if(bit(i) & tmpN){
            sum += bit(i);
            //今左側にいる
            if(r == 0){
                for(int j = 0;j <= i;j++){
                    ans.push_back({i, j});
                }
                r = 1;
            }
            else{
                for(int j = i; j>= 0;j--){
                    ans.push_back({i, j});
                }
                r = 0;
            }
        }
        else{
            sum++;
            if(r == 0){
                ans.push_back({i, 0});
            }
            else{
                ans.push_back({i, i});
            }
        }
    }
    while(N - sum > 0){
        auto tmp = ans.back();
        if(tmp.second == 0){
            ans.push_back({tmp.first+1, 0});
        }
        else if(tmp.first == tmp.second){
            ans.push_back({tmp.first+1, tmp.second+1});
        }
        sum++;
    }
    for(auto& p: ans){
        cout << p.first + 1 << " " << p.second + 1 << endl;
    }
}
int main() {
    int t;f
    cin >> t;
    rep1(i, t+1){
        cout << "Case #" << i << ":" << endl;
        solve();
    }
}