OUPC β

www.hackerrank.com

阪大の現役・OBの人たちの有志コン！
面白い問題ばかりで楽しかった

Grundy Number

Grundy数の定義がわかる
FAを狙って手元でコンパイルせずに出したけど11秒負けた（早くない？）

[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> A(101);
    REP(i,N){
        int a;
        cin >> a;
        A[a]++;
    }
    REP(i,101){
        if(A[i] == 0){
            cout << i << endl;
            return 0;
        }
    }
}

Doubling Step

これ結構好き
DPをすればよくて
移動先の上限はくらいで十分足りるので で解ける

[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> dp(101010);
    dp[1] = 1;
    for(int i=2;i<=N;i++){
        for(int j=0;j<=33;j++){
            if(i < (1LL << j)) continue;
            if(dp[i - (1LL << j)] == 0) continue;
            dp[i] += dp[i - (1LL << j)];
            dp[i] %= 998244353;
        }
    }
    cout << dp[N] << endl;
}

Power Number

ぱっと見DPすれば良さそう
部分文字列列挙してDPしていけばいい？って思ったけど
よくわからず飛ばした

解説によるとこの方針でいいっぽくて、候補の文字列の長さが高々10だから全列挙しちゃっていいっぽい
良い問題だなーとなったので後でちゃんと解きます

[追記]
以前書いていたように、文字列の候補とそのスピリチュアル度を前処理で全列挙する
その後dpをすればいい

[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, M, B;
    string S;
    cin >> N >> M >> B >> S;
    map<string, ll> mp;
    REP(i,M){
        string a;
        ll v;
        cin >> a >> v;
        ll val = 0;
        for(int i=1;i<(1<<(int)a.size());i++){
            string tmp = "";
            REP(j,(int)a.size()) if(i >> j & 1) tmp += a[j];
            val = v - ((ll)a.size() - (ll)tmp.size()) * B;
            if(mp.count(tmp)) chmax(mp[tmp], val);
            else mp[tmp] = val;
        }
    }

    vector<ll> dp(N+10, -LINF);
    dp[0] = 0;
    for(int i=1;i<=N;i++){
        string tmp = "";
        for(int j=0;j<10;j++){
            if(i + j > N) continue;
            tmp += S[i+j-1];
            if(mp.count(tmp)) chmax(dp[i+j], dp[i-1] + mp[tmp]);
        }
    }
    cout << dp[N] << endl;
}

Product Grid

これも難しい
とりあえず最小なのでを考える
素数がデカイと死にそうなのでmapにして素因数を管理
その後、各列の並べ方1行目を除いて で、素因数が同じものだったり、1が複数あるとその階上分割ったりを考えないといけない
ある程度のベースを計算しておいて各列ごとに掛けたり割ったりでいけないかなーってごちゃごちゃしてるうちに終了
これもちゃんと解説見て通しておきます

[追記]
素因数をmapで管理して差分更新する方針はあってた
まず、baseとして1行目が全て1と仮定したときの値を求めておく
その後各列に対し、1行目の素因数の数を差分更新していく

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W;
    cin >> H >> W;
    vector<int> A(W);
    vector<vector<pair<ll, ll>>> pA(W);
    map<int, ll> mp;
    REP(i,W){
        cin >> A[i];
        if(A[i] == 1) continue;
        auto res = prime_factorize(A[i]);
        pA[i] = res;
        for(auto x : res){
            if(mp[x.first] < x.second) mp[x.first] = x.second;
        }
    }
    mint base = 1;
    for(auto e : mp){
        ll N = e.second;
        base *= bc.com(N+H-2, N);
    }

    mint ans = 1;
    REP(i,W) ans *= base;

    REP(i,W){
        for(auto e : pA[i]){
            ll N = mp[e.first];
            ans /= bc.com(N+H-2, N);

            ll M = mp[e.first] - e.second;
            ans *= bc.com(M+H-2, M);
        }
    }
    cout << ans << endl;
}

Increasing Path

これ好き（解けたので）
500点の中で一番これが解けそうだったので解いたら一発で通ってFAだった（嬉しい）

まず、単一始点の最短距離だからダイクストラを考える
制約として、今まで通った辺のコストより小さいものは通れない
なので、状態として今まで通った距離、一個前に通った辺のコストを持たせて上げる
あとは最短距離になるように、今の距離と前に通った辺のコストの昇順になるようにpriority_queueで管理しながらダイクストラしていくとAC
一発ですっきりしたコードかけてよかった
[提出コード]

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, ll>>> G(N);
    REP(i,M){
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        G[a].emplace_back(b, c);
        G[b].emplace_back(a, c);
    }
    priority_queue<tuple<ll, ll, int, int>, vector<tuple<ll, ll, int, int>>, greater<tuple<ll, ll, int, int>>> pq;
    pq.emplace(0, 0, 0, -1); //dist, pre_cost, cur_v, pre_v
    while(!pq.empty()){
        ll dist, preCost, cur, pre;
        tie(dist, preCost, cur, pre) = pq.top(); pq.pop();
        if(cur == N-1){
            cout << dist << endl;
            return 0;
        }
        for(auto nv : G[cur]){
            if(nv.first == pre) continue;
            if(nv.second <= preCost) continue;
            pq.emplace(dist + nv.second, nv.second, nv.first, cur);
        }
    }
    cout << -1 << endl;
}

ビブンケイスウ

問題文が好き
ぱっと見セグ木の形をしているんだけど、どう載せるんだこれとなり残りの500の考察をしてた
どうもギャグらしく、2次以上の項を無視すればセグ木で殴れるらしい（言われると確かにそう…）
これもちゃんと通しておかないとね

おわりに

どの問題も面白くてクオリティ高いなあとなりました
EのFA取れて嬉しかったけど、もう一問通したかったね