キーエンス プログラミング コンテスト 2020

atcoder.jp

入水しました（3回目）

A - Painting

を取っていけばいい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, W, N;
    cin >> H >> W >> N;
    if(H < W) swap(H, W);
    cout << (N + H - 1) / H << endl;
}

B - Robot Arms

ぱっと見imosっぽい、制約見る、座圧とかしなきゃじゃん
mapで区間が重なっているmaxを数えたりしたけど頭バグってたね
一回C行った後冷静になると区間スケジューリングじゃんとなる
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> X(N), L(N);
    vector<pair<ll, ll>> v;
    REP(i,N){
        cin >> X[i] >> L[i];
        v.emplace_back(X[i]+L[i], X[i]-L[i]);
    }
    sort(v.begin(), v.end());
    ll cur = -LINF;
    int ans = 0;
    for(auto x : v){
        if(cur <= x.second){
            cur = x.first;
            ans++;
        }
    }
    cout << ans << endl;
}

C - Subarray Sum

気づいた瞬間ギャグじゃんと画面に向かって言ってしまった
なのでK個Sを置いて、後は残りの連続部分列でSが出来ないように置く
制約見逃して適当にLINFで置いて1WA生やした（アホ）
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K, S;
    cin >> N >> K >> S;
    vector<ll> ans(N);
    REP(i,N){
        if(K > 0){
            ans[i] = S;
            K--;
        }
        else{
            if(S != INF) ans[i] = INF;
            else ans[i] = INF - 1;
        }
    }
    REP(i,N) cout << ans[i] << " ";
    cout << endl;
}

D - Swap and Flip

制約をみてbit系じゃーんとなるも中々考察が進まなかった
ぐっと睨むと表裏決め打ちができそうなのでbit全探索をする
その後出来る配列をソートして、実際に操作を行ってそのように出来るか判定
出来るなら、転倒数を数えれば良いじゃん天才、WAが出て凡才…
公式解説はbitDPだけどTL眺めてた感じこの方針でも通してる人がいたので詰めきれなかっただけっぽい
bitDPのほうが良さそうかな？ちゃんと復習します
[追記] コンテスト後に表裏全探索で取り敢えず通ったので載せておきます
基本的にはコンテスト中の考え方で、まとめてソートしていたところを偶数奇数に分けてソートするとAC
bitDPも何となく理解できたので後で通しておきたい
提出コード

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> A(N), B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    int ODD = (N + 1) / 2;
    int EVEN = N / 2;

    int ans = INF;
    REP(bits, 1<<N){
        vector<pair<int,int>> even, odd;
        REP(j,N){
            if((bits >> j) & 1){
                if(j & 1) odd.emplace_back(B[j], j);
                else even.emplace_back(B[j], j);
            }
            else{
                if(j & 1) even.emplace_back(A[j], j);
                else odd.emplace_back(A[j], j);
            }
        }
        if(ODD != (int)odd.size() || EVEN != (int)even.size()) continue;
        sort(odd.begin(), odd.end());
        sort(even.begin(), even.end());
        vector<pair<int,int>> v;
        REP(i,ODD){
            v.emplace_back(odd[i]);
            if(i < EVEN) v.emplace_back(even[i]);
        }
        bool ok = true;
        for(int i=1;i<N;i++) if(v[i-1].first > v[i].first) ok = false;
        if(!ok) continue;
        int cnt = 0;
        REP(i,N) for(int j=i+1;j<N;j++) if(v[i].second > v[j].second) cnt++;
        chmin(ans, cnt);
    }
    if(ans == INF) ans = -1;
    cout << ans << endl;
}

おわりに

Bで区間スケジューリングぱっと出てこなくて1WA生やしてCも制約見落として1WA生やして反省…
Dも考察は良かったっぽい（公式解説と違うけど）ので通したかったね〜残念
そろそろ水色継続streak伸ばしたくない？伸ばしたい