Codeforces #402 (Div.2)

Codeforces Round #402 (Div. 2)

Codeforces#402に出たので、なんとなく眠気もないしつける
最近レートが下がってばっかで悲しみ界のtouristになってたんですが、またさがったのでもうダメ
とりあえず前回のコドフォでYESとYesを間違えたり、JOI本選でllにし忘れたりとかそういうの多いのだめ

ちゃんと精進して地力付けていこうな👊

A問題

なんか2つの数列が与えられるからスワップして各数字が含まれる数を等しくしなさいみたいな
スワップ回数の最小値を求めなさい、等しく出来なければ-1を出力
等しく出来ないのは自明で全体である数字が奇数個しかなかったとき
等しくできるときは、その数字がある個数/2-数列Aにある個数の絶対値をそれぞれの数字でやる
そして半分にすればOK

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N;
    int a[114], b[114], numA[5] = {}, numB[5] = {}, num[5] = {};
    int res = 0;
    cin >> N;
    REP(i, N){
        cin >> a[i];
        numA[a[i]-1]++;
        num[a[i]-1]++;
    }
    REP(i, N){
        cin >> b[i];
        numB[b[i]-1]++;
        num[b[i]-1]++;
    }
    REP(i, 5){
        if(num[i] % 2 != 0){
            cout << -1 << endl;
            return 0;
        }
    }
    REP(i, 5){
        res += abs(num[i]/2-numA[i]);
    }
    cout << res/2 << endl;
}

B問題

正の整数Nから好きなだけ桁を取り除いて10^kで割り切れるようにしなさい
下から貪欲
もしも0の個数が足りなければ0にするためにNの桁数-1が答えになる
絶対に0は存在するからね（答えが必ず存在するため）

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    string num;
    int k;
    cin >> num >> k;
    int zero = 0;
    reverse(all(num));
    REP(i, num.size()){
        if(num[i] == '0')
            zero++;
        if(zero >= k){
            cout << i+1-zero << endl;
            return 0;
        }
    }
    if(zero < k){
        cout << num.size()-1 << endl;
    }
    return 0;
}

C問題

セールしてるよ、セール中にk個は少なくとも買ってね
セール後の方がやすくなってる商品もあるからそっちで買ってもいいよ
できるだけ総額を安くしてくれ

セール中とセール後の差でソートして貪欲
a[i]-b[i]をfirstにしたpairでやるとうまくいくはず
実装は汚い

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    int a[214514], b[214514], dif[214514];
    PII pd[214514];
    ll res = 0;
    cin >> n >> k;
    REP(i, n){
        cin >> a[i];
    }
    REP(i, n){
        cin >> b[i];
        dif[i] = a[i]-b[i];
        pd[i] = {dif[i], i};
    }
    int buy = 0;
    sort(pd, pd+n);
    while(pd[buy].first <= 0 && buy < n){
        res += a[pd[buy].second];
        buy++;
    }
    while(buy < k){
        res += a[pd[buy].second];
        buy++;
    }
    FOR(i, buy, n){
        res += b[pd[i].second];
        
    }
    cout << res << endl;
}

D問題

C問題を解くまでにかかったのが21分でそこから空白の1時間40分を過ごし死んだ
ここまで最高の流れでC問題解き終わった時点では2桁位だったのにな…

文字列TとPがあります。Tから与えられる順番で文字を消していくけど、いくつまでなら消してもPを部分列として含んでいるでしょう

ずっと部分列として含むか判定の高速化を考えてたけど実際はいくつとるかの試行を減らす方向だった
もっと頭を柔軟にできるようにしたい…
にぶたんだった
あたまをなーやわらかくなーできたらなー
部分列として含むかがO(|T|)でできるから全体でO(|T| log |T|)かな？
これからは最大化最小化を見たらすぐにぶたんに結びつけてやるぞ(死亡の音)

実装では消すのではなく逆順にして使える文字を増やしていった（なんか楽そうに見えたから）

string t, p;
vector<int> a;
bool canuse[214514] = {};

bool ok(int tm){
    memset(canuse, 0, sizeof canuse);
    REP(i, tm){
        canuse[a[i]] = true;
    }
    int in = 0;
    REP(i, p.size()){
        while(in < t.size() && (!canuse[in] || t[in] != p[i])) in++;
        if(in == t.size()){
            return false;
        }
        in++;
    }
    return true;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> t >> p;
    REP(i, t.size()){
        int A; cin >> A; A--;
        a.push_back(A);
    }
    reverse(all(a));
    int l = 0, r = t.size();
    while(r-l > 1){
        int m = (l+r)/2;
        if(ok(m)){
            r = m;
        }else{
            l = m;
        }
    }
    cout << t.size()-(l+r)/2-1 << endl;
}

もっと精進して解法レパートリー増やそうな