ながめも

競技プログラミングについて

AtCoder Beginner Contest 178 ABC178 参加記

5完で水パフォでした。青パフォstreakが切れて悲しいですね。

提出したコードへのリンク

A - Not

問題へのリンク

解説

1とのxorを取ると逆転します。

実装

int main() {
    int x;
    cin >> x;
    cout << x^1 << endl;
}

B - Product Max

問題へのリンク

解説

こういう問題最近よく見ます。大抵区間の端のみを見ればよいです。

実装

int main() {
    ll a, b;
    ll c, d;
    cin >> a >> b;
    cin >> c >> d;
    ll ans = -INFLL;
    chmax(ans, a * c);
    chmax(ans, a * d);
    chmax(ans, b * c);
    chmax(ans, b * d);
    if(a <= 0 && 0 <= b)chmax(ans, 0LL);
    if(c <= 0 && 0 <= d)chmax(ans, 0LL);
    cout << ans << endl;
}

C - Ubiquity

問題へのリンク

解説

dp[どこまで見たか][0が出たか][9が出たか]でdpします。

実装

mint dp[1000100][2][2];
int main() {
    int N;
    cin >> N;
    rep(i,N+1)rep(j,2)rep(k,2)dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    rep(i,N){
        rep(j,2)rep(k,2){
            for(int nxt = 0; nxt <= 9; nxt++){
                dp[i+1][j || nxt == 0][k || nxt == 9] += dp[i][j][k];
            }
        }
    }
    cout << dp[N][1][1] << endl;
}

D - Redistribution

問題へのリンク

解説

 \Theta(S^{3})のdpしか見えなくて雑に枝刈りしたら通りました。許してください。

実装

mint dp[2500][2500];
int main() {
    ll S;
    cin >> S;
    rep(i,2222)rep(j,2222)dp[i][j] = 0;
    dp[0][0] = 1;
    rep(i,2221)rep(j,S){
        if(dp[i][j].x == 0)continue;
        for(int add = 3; add + j <= S; add++){
            dp[i+1][add + j] += dp[i][j];
        }
    }
    mint ans = 0;
    rep(i,2222)ans += dp[i][S];
    cout << ans << endl;
}

E - Dist Max

問題へのリンク

解説

既出っぽいし典型っぽいので「マンハッタン距離 最大」とかでググると色々ヒットします。 マンハッタン距離なら45°回転は典型っぽいので、抑えておきたいところです。

実装

int main() {
    int N;
    cin >> N;
    vector<ll> v, w;
    rep(i,N){
        int x, y;
        cin >> x >> y;
        v.emplace_back(x-y);
        w.emplace_back(x+y);
    }
    sort(all(v));
    sort(all(w));
    ll maxx = 0;
    chmax(maxx, v.back() - v[0]);
    chmax(maxx, w.back() - w[0]);
    cout << maxx << endl;
}

F - Contrast

問題へのリンク

解説

ある数 i A Bに渡って N個以上あるとき、不可能で、それ以外は可能です。 構築は難しいですが、 Bをreverseすると重なるのは一つだけなので、そこを雑に調整すると良さそうです。

実装

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    cin >> A >> B;
    map<int, int> mpa, mpb;
    rep(i,N){
        mpa[A[i]]++;
        mpb[B[i]]++;
    }
    for(int i = 1; i <= N; i++){
        ll cnta = mpa[i];
        ll cntb = mpb[i];
        if(cnta + cntb > N){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    reverse(all(B));
    int idx = 0;
    rep(i,N){
        if(A[i] == B[i]){
            while(B[idx] == B[i] || A[idx] == B[i]){
                idx++;
                idx %= N;
            }
            swap(B[i], B[idx]);
        }
    }
    rep(i,N){
        cout << B[i] << " ";
    }
    cout << endl;
}