Google Code Jam Round 1A 2022 参加記

2022.04.09

競技プログラミング

Google Code Jam

1時間9分2完で1454位でした。誤読したり無駄なペナを食らったりしましたが、Round 1通過したっぽいのでよかったです。

A

問題

文字列$S$が渡されます。あなたはこの中のいくつかの文字をハイライトすることができます。ハイライトされていない文字は新しい文字列に1度だけ付与され、ハイライトされている文字は新しい文字列に2度付与されます。この操作でできる辞書順最小の文字列を出力してください。

たとえば、“HELLOWORLD"のH、最初と最後のL、最後のOをハイライトすると、“HHELLLOWOORLLD"となります。

$1 \leq T \leq 100$

$1 \leq |S| \leq 100$

考察

後ろから愚直にシミュレーションしていきました。

提出コード

void solve(){
    string S; cin >> S;
    int N = S.length();
    string ans = "";
    
    repd(i, N){
        string tmp1 = S[i] + ans;
        string tmp2 = S[i] + tmp1;
        if(tmp1 < tmp2) ans = tmp1;
        else ans = tmp2;
    }
    cout << ans << endl;
}

int main(){
    int T; cin >> T;
    rrep(t, T){
        cout << "Case #" << t << ": ";
        solve();
    }
}

B

問題

整数$N$が与えられます。まず$N$個の異なる整数を選択し出力してください。ジャッジからそれらとは異なる$N$個の整数が出力されます。これら$2N$個の整数を2つの部分集合に分割してください。ただし、その両方の和が等しくなるようにしなければなりません。$2N$個の整数は$1$から$10^9$までの整数であり、和が偶数になることが保証されます。

$1 \leq T \leq 100$

$N = 100$

$2N$個の整数はすべて異なり、$1$から$10^9$までの整数

考察

$2^0, 2^1, 2^2, … 2^{30}$があると$10^9$以下のすべての数を作ることができます。よってこれらは確定です。残りですが、適当に$10^9, 10^9-1, 10^9 - 2, …$ を入れました。焦りながら書いたのでだいぶ汚いです、ごめんなさい><

インタラクティブな問題なので、フラッシュをしなくてはなりません。僕はフラッシュを忘れて1TLEしました。

提出コード

void solve(){
	int N; cin >> N;
    //出力する整数のリスト
    vll L;
    ll k = 1;
    while(k < 1000000000){
        L.pb(k); k *= 2;
    }
    ll add = 1000000000;
    while(L.size() < N){
        L.pb(add); add--;
    }
    
    //出力
    rep(i, L.size()){
        cout << L[i];
        if(i != L.size() - 1) cout << " ";
        else cout << endl;
    }
    
    //入力
    rep(i, N){
        ll a; cin >> a;
        L.pb(a);
    }
    
    sort(all(L));
    ll su = sum(L);
    //部分集合の和となるべき数
    ll go = su / 2;
    //答えの集合
    vll Ans;
    
    //1e9以下になるまで大きい数から追加していく
    while(go > 1000000000){
        go -= L.back();
        Ans.pb(L.back());
        L.pop_back();
    }
    
    rep(i, 32){
        if((go >> i) & i) Ans.pb(1 << i);
    }
    
    //出力
    rep(i, Ans.size()){
        cout << Ans[i];
        if(i != Ans.size() - 1) cout << " ";
        else cout << endl;
    }
    
}

int main(){
    int T; cin >> T;
    rep(t, T) solve();
}

C

誤読していたりしていて解けませんでした(誤読していなくても解けていなさそうでした)。