接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

三井住友信託銀行プログラミングコンテスト2019

ABC級の企業コン!
5完1WAでパフォ1287
Eまで解き終わった時の満足度は高かったけどパフォが微妙だったうーん

A - November 30

次の日の月が変わっていたら月末日になるのでM_1 \lt M_2なら1
大丈夫とわかっててもこういうのちょっと怖くない?
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int M1,M2,D1,D2;
    cin >> M1 >> D1 >> M2 >> D2;
    if(M1 < M2) cout << "1" << endl;
    else cout << "0" << endl;
}

B - Tax Rate

制約が小さいので全探索する
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for(int i=1;i<=505050;i++){
        int res = i * 1.08;
        if(res == N){
            cout << i << endl;
            return 0;
        }
    }
    cout << ":(" << endl;
}

C - 100 to 105

DP出来そうだけど算数したほうが早そう
下2桁しか見る必要はなくて、下2桁を合わせられたら後は100円のものを買えばいい
105円のものから取れるだけ取っていって、条件を満たせばおっけー
クソみたいな実装でごめんなさい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X;
    cin >> X;
    if(X < 100){
        cout << 0 << endl;
        return 0;
    }
    int cnt = X / 100;
    int res = X % 100;
    cnt -= res / 5;
    res %= 5;
    if(res == 0 && cnt >= 0){
        cout << 1 << endl;
        return 0;
    }
    if(cnt < 0){
        cout << 0 << endl;
        return 0;
    }
    //cout << res << endl;
    cnt -= res / 4;
    res %= 4;
    if(res == 0 && cnt >= 0){
        cout << 1 << endl;
        return 0;
    }
    if(cnt < 0){
        cout << 0 << endl;
        return 0;
    }
    cnt -= res / 3;
    res %= 3;
    if(res == 0 && cnt >= 0){
        cout << 1 << endl;
        return 0;
    }
    if(cnt < 0){
        cout << 0 << endl;
        return 0;
    }
    cnt -= res / 2;
    res %= 2;
    if(res == 0 && cnt >= 0){
        cout << 1 << endl;
        return 0;
    }
    if(cnt < 0){
        cout << 0 << endl;
        return 0;
    }
    cnt -= res;
    res = 0;
    if(res == 0 && cnt >= 0){
        cout << 1 << endl;
        return 0;
    }
    if(cnt < 0){
        cout << 0 << endl;
        return 0;
    }

}

提出コード(DP解)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X;
    cin >> X;
    vector<bool> dp(101010, false);
 
    dp[0] = true;
    for(int i=0;i<100000;i++){
        if(dp[i]){
            for(int j=0;j<=5;j++){
                dp[i+100+j] = true;
            }
        }
    }
    
    if(dp[X]) cout << 1 << endl;
    else cout << 0 << endl;
}

D - Lucky PIN

これ難しい
部分文字列っぽいので部分文字列DPをググる
次の記事が出てくるのでこれをもとにDPする
これだけだと全列挙になるので、個数の情報を付け足してDPする
答えとなる候補は高々1000通りだから全探索天才過ぎませんか
qiita.com

提出コード

vector<vector<int> > calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(10, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 10; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'0'] = i;
    }
    return res;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    vector<vector<int>> next = calcNext(S);
    vector<vector<ll>> dp(N+1, vector<ll>(4));
    dp[0][0] = 1;
    for (int i = 0; i < N; ++i) {
        for(int k = 0;k <= 2; k++){
            for (int j = 0; j < 10; ++j) {
                if (next[i][j] >= N) continue;
                add(dp[next[i][j] + 1][k+1], dp[i][k]);
            }
        }
    }
    ll res = 0;
    REP(i, N+1){
        add(res, dp[i][3]);
    }
    cout << res << endl;
}

提出コード(全探索解)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;

    REP(i,10) REP(j,10) REP(k,10){
        bool fi = false, se = false;
        REP(l, N){
            if(!fi && S[l] == i + '0'){
                fi = true;
                continue;
            }
            if(fi && !se && S[l] == j + '0'){
                se = true;
                continue;
            }
            if(fi && se && S[l] == k + '0'){
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
}

提出コード(にぶたん解)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    vector<int> idx[10];
    REP(i,N){
        idx[S[i]-'0'].push_back(i);
    }

    REP(i,10) REP(j,10) REP(k,10){
        auto itr = lower_bound(idx[i].begin(), idx[i].end(), 0);
        if(itr == idx[i].end()) continue;
        auto itr2 = lower_bound(idx[j].begin(), idx[j].end(), *itr + 1);
        if(itr2 == idx[j].end()) continue;
        auto itr3 = lower_bound(idx[k].begin(), idx[k].end(), *itr2 + 1);
        if(itr3 == idx[k].end()) continue;
        ans++;
    }
    cout << ans << endl;
}

E - Colorful Hats 2

これも難しいけど1200人も通すのか〜
考えたことは0が出てくると(3 - cnt[0])をかければ良さそう
次に1が出てくると0の出た個数とすでに出た1の個数から(cnt[0] - cnt[1])かければ良さそう
これを抽象化し、今見ている数字に注目すると、その数字-1とその数字がこれまでに何個出てきたかをmapとかで持っていれば大丈夫
これをそのまま実装するとサンプルが合ってAC
本番中気づいてなかったんですが、答えが0になる(辻褄が合わない)場合があるっぽくてたまたま0になる実装してて本番後ちょっと焦ったね
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    map<ll,ll> mp;
    ll ans = 1;
    REP(i,N){
        int num;
        cin >> num;
        if(num == 0) ans *= (3 - mp[num]);
        else{
            ans *= (mp[num-1] - mp[num]);
        }
        mp[num]++;
        ans %= MOD;
    }
    ans %= MOD;
    cout << ans << endl;
}

F - Interval Running

見た目からし{\mathcal{O}(1)}がありそう
とりあえず1サイクルでどれだけの差がつくかを確認する
1サイクルの合計が0になるとinfinityになる
本番は時間足りなくてここまでしか考察できなかった
解説のほうが詳しくてわかりやすいので割愛しますが、1サイクルに注目するのは間違ってなくて、その後に場合分けし、適切に計算するとACできる
人々こういう算数強くて勝てね〜
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll T1, T2, A1, A2, B1, B2;
    cin >> T1 >> T2 >> A1 >> A2 >> B1 >> B2;

    ll A = T1*A1 - T1*B1;
    ll B = T2*A2 - T2*B2;
    if(A > 0){
        A *= -1;
        B *= -1;
    }

    if(A + B < 0){
        cout << 0 << endl;
    }
    else if(A + B == 0){
        cout << "infinity" << endl;
    }
    else{
        ll S = -A / (A+B);
        ll T = -A % (A + B);
        if(T == 0) cout << S * 2 << endl;
        else cout << S * 2 + 1 << endl;
    }
}

おわりに

DをDPで解けたし、Eもこういうの苦手だけど通せたので内容的には満足
Dは全探索解もあったし、DP解も方針間違ってなかったけどバグらせて時間かかったのは反省かなあ
こういう回苦手傾向にあるので、パフォ下がらなかっただけマシかな?
5完でパフォ1200代はびっくりしちゃうね