Tenka1 Programmer Contest 2019

結果

 C問題だけの1完で711位だった。青あたりのレート帯だとC問題早解きゲームと化していて、24分(1WA)では良い順位を望むべくもなく。レート変動は1748→1720(-29)。

C問題 Stones

f:id:tokumini:20190421144421j:plain

 最初はメモの前半のように文字列を「B...BW...W」の繰り返しと考えて、これらを個別に見て少ない方を全部反転すれば良いと思って1WA。これだとたとえば「BBBWBWWW」のとき、前半4文字「BBBW」ではWの方が少ないので4文字目をBへ、後半4文字「BWWW」ではBの方が少ないのでBをWへという操作になるが、結果として得られるのは「BBBBWWWW」でBWが残ってしまっている。

 ジャッジが詰まっていたのもあって提出の後結果が出るまでにかなり時間がかかった。D問題を考えていたが戻って考え直して、最終的に「...WB...」という形になるしかないのでこのWBの切れ目を全探索すれば良いと気づく。無駄に累積和の配列を構築して範囲を考えて……とかやっていたら混乱してしまい実装に時間もかかった。WAを出してしまった焦りもあったんだと思う。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    string S;
    cin >> N >> S;

    vector<ll> b(N + 1, 0), w(N + 1, 0);
    for (ll i = 0; i < N; i++) {
        if (S[i] == '#') {
            b[i + 1] = b[i] + 1;
            w[i + 1] = w[i];
        } else {
            b[i + 1] = b[i];
            w[i + 1] = w[i] + 1;
        }
    }

    ll ans = INT_MAX;
    for (ll i = 0; i <= N; i++) {
        ans = min(ans, b[i] + w[N] - w[i]);
    }
    cout << ans << endl;
}

 最初の方針は確かに不安な感じもあったが、この程度の不安感なら通ることもあるという判断で提出してしまった。せめて「B...BW...W」が2回繰り返されるケースはやるべきだったし、大小の組み合わせで

  • BBBWBBBW
  • BBBWBWWW
  • BWWWBBBW
  • BWWWBWWW

の4通りくらいは考えるべき。怪しい解法に対する敏感さというのも実践感覚の一種だと思っていて、最近あまり問題を解いていないから鈍っているのだろう。

D問題 Three Colors

f:id:tokumini:20190421150433j:plain

 最初いくらか性質を考えて、まずはパッと思い浮かぶDPを疑う(青線上部)。感覚的には間に合わないんだけど、具体的にどういう計算量になるのかはっきりと示せなくてひょっとしたら(最大値の制約とかで枝刈りを入れれば)通るんじゃないかと思ったりもする。

 あとはRの値を全探索して残りをG,Bに振り分けるという形で解けないか考えていた(青線以下)。Rを特定の値にするときにどれを使うかはDPで求まりそうだと思ったがG,Bへの振り分けが上手くいきそうにない。大小関係に仮定を入れて対称性から考えるにも等号が入ったりするとめちゃくちゃになるなぁというところで進まなくなってしまった。そもそも場合の数を考えられていないので全然ダメな方針だった。

 残り時間が少なくなったところで、とりあえず最初のDP方針で解けてしまうのだったら後で悔しいので実装して提出。当然TLE。下の方針でも実はRの範囲が狭いからなんとか間に合うとかそういうことがあるのかもしれないと思いつつ実装しているところで時間切れ。解けそうな雰囲気があまりしなかった。

 振り返ってみても根本的にメモの量が少ない。しかし具体例をいじるタイプの問題でもないと思うので考察の進め方がよくわからなかった。

 解説を見るとまず「R, G, B のうち一番大きいものが S/2 以上となるような塗り分け方の個数を求めて全体から引くことを考え」ることに思い至っていないので初手からダメだったようだ。条件に合わないものを引く考え方があまりできていない気がする。

 解説だとさらっとDPでできると書いてあるが、実装がよくわからなかったので他の人の提出をだいたい写す感じでAC。これは難しいなぁ。

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

int main() {
    constexpr ll MOD = 998244353;

    ll N;
    cin >> N;
    vector<ll> a(N);
    for (ll i = 0; i < N; i++) {
        cin >> a[i];
    }

    ll sum = accumulate(a.begin(), a.end(), (ll)0);

    vector<vector<ll>> dp1(N + 1, vector<ll>(sum + 1, 0));
    vector<vector<ll>> dp2(N + 1, vector<ll>(sum + 1, 0));

    ll ans = 1;

    for (ll i = 0; i < N; i++) {
        //全通りは3のN乗
        (ans *= 3) %= MOD;

        //rが0ならそれまでのものはg or bに振り分けられていた→2のi乗
        dp1[i][0] = (i == 0 ? 1 : dp1[i - 1][0] * 2 % MOD);

        //dp2はgしか使わないので1で初期化
        dp2[i][0] = 1;

        for (ll j = 0; j <= sum; j++) {
            //a[i]をr以外に足す
            //dp1ではg or bに足す(2倍される)
            (dp1[i + 1][j] += dp1[i][j] * 2) %= MOD;

            //dp2ではgに足す(1倍のまま)
            (dp2[i + 1][j] += dp2[i][j]) %= MOD;

            if (j + a[i] > sum) {
                continue;
            }

            //a[i]をrに足す
            (dp1[i + 1][j + a[i]] += dp1[i][j]) %= MOD;
            (dp2[i + 1][j + a[i]] += dp2[i][j]) %= MOD;
        }
    }

    for (ll i = (sum + 1) / 2; i <= sum; i++) {
        ans = (ans + MOD - dp1[N][i] * 3 % MOD) % MOD;
    }

    if (sum % 2 == 0) {
        //重複して引きすぎたものを戻す
        ans = (ans + dp2[N][sum / 2] * 3 % MOD) % MOD;
    }

    cout << ans << endl;
}