Tenka1 Programmer Contest 2019 - 競プロやります。

C - Stones
D - Three Colors
- 方針
- ソースコード

C - Stones

https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_c

方針

「黒い石のすぐ右に白い石があるような箇所がない」ような石の並び方は、以下のようなものになります ( $N=9$ )。

.........   ....#####
........#   ...######
.......##   ..#######
......###   .########
.....####   #########

与えられた並べ方を以上のどれに一致させるかでそれぞれ操作回数を求め、最も小さいものを出力します。ここで愚直に数えていくと計算量が $O(N^2)$ になってTLEしてしまうので、累積和を使います。

以下では
　　 $b_i = S$ の 0 ~ i 番目にある黒い石の数
　　 $w_i = S$ の i ~ N-1 番目にある白い石の数
とします。

目標とする並べ方を「左から見て $n$ 番目以降が黒石」としたときの手数を求めます。
(1) n 番目が黒石のとき
0 ~ n-1 番目までにある黒石の数は、 $b_n - 1$ 個、n ~ N-1 番目にある白石の数は $w_n$ 個ですので、手数は $b_n + w_n - 1$ 回となります。
ここで、0 ~ n-1 番目までの黒石の数を $b_{n-1}$ とすることもできますが、 $n=0$ のときに場合分けしたくないので、こうしています。

(2) n 番目が白石のとき
0 ~ n-1 番目までにある白石の数は、 $b_n$ 個、n ~ N-1 番目にある黒石の数は、 $w_n + 1$ 個ですので、手数は $b_n + w_n + 1$ 回となります。

以上の議論の中には、すべてが白石となるような並べ方にする場合が考慮されていません。このときは、 $S$ に含まれるすべての黒石を白石にすればよいので、手数は $b_{N-1}$ となります。

ソースコード

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

int main(){
    int N;  string S;
    cin >> N >> S;
    vector<int> w(N,0), b(N,0);
    // b[i] を求める
    for(int i=0; i<N; i++){
        if(S[i]=='#') b[i]++;
        if(i>0) b[i]+=b[i-1];
    }
    // w[i] を求める
    for(int i=N-1; i>=0; i--){
        if(S[i]=='.') w[i]++;
        if(i<N-1) w[i]+=w[i+1];
    }

    int ans = N;
    for(int n=0; n<N; n++){
        // n ~ N-1番目がすべて黒になる並べ方
        if(S[n]=='#'){
            ans = min(ans, b[n]-1 + w[n]);
        }else{
            ans = min(ans, b[n] + w[n]+1);
        }
    }
    // すべて白石になる場合
    ans = min(ans, b[N-1]);

    cout << ans << endl;
}

反省

はじめは、以下の２通りの中で手数が少ない方を出力すれば良いと考えました：

$S$ を左から見ていき、一番最初に出てくる黒石よりも右にある白石を全て黒に変える
$S$ を右から見ていき、一番最初に出てくる白石よりも左にある黒石を全て白に変える

WAになったので間違っていると思うのですが、反例は何になるんでしょうか……？

D - Three Colors

https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_d

方針

$S = \sum a_i$ 、 $M = \max(R,G,B)$ とします。 $M \geq S/2$ となるとき、三角形を作れません。それ以外の時は常に作ることが出来ます。そこで色の塗分け方の場合の数 $3^N$ 通りから、 $M \geq S/2$ となるような場合の数を引くことを考えます。

(1) $M > S/2$ のとき
このとき残りの 2 つは必ず $S/2$ 未満になります。よって $M > S/2$ となる場合の数は、 $R>S/2$ となる場合の数の 3 倍です。

(2) $M = S/2$ のとき
このときは (1) と同様に $R=S/2$ となる場合の数の 3 倍と考えることは出来ません。
$R = S/2 > G, B$ である場合はそれでよいのですが、G, B のいずれかが S/2 に等しいとき、
　 $(R,G,B) = (S/2, S/2, 0),~(S/2,0,S/2),~(0,S/2,S/2)$
のうち前 2 つが $R=S/2$ の場合に含まれているためです。
よって $M=S/2$ の場合の数は、 $R=S/2$ となる場合の数の 3 倍から、 $R=G=S/2$ となる場合の数の 3 倍を引けば求められます。

以上より、
$dp1[i][r] = a_1 \text{～} a_i$ までで、赤色に塗った値の和が $r$ であるような場合の数
$dp2[i][r] = a_1 \text{～} a_i$ までで、赤色に塗った値の和が $r$ で、赤以外を全て緑に塗るような場合の数
とすると、答えは以下のようにあらわされます：
　　 $\displaystyle 3^N - 3 \times \sum_{r = S/2}^{S} dp1[N][r] + 3 \times dp2[N][S/2]$

以下では $dp1,~dp2$ を求めていきます。
$i = 0$ のときは $r = 0$ とすることしかできず、 $dp1[0][0] = dp2[0][0] = 1$ 、 $r \neq 0$ のとき $dp1[0][r] = dp2[0][r] = 0$ です。

$1, 2, \dots i$ について $dp1[i][r],~dp2[i][r]$ が求まっているときに、 $dp1[i+1][r],~dp2[i+1][r]$ がどのように決まるかを考えます。
(1) $a_{i+1} > r$ のとき
このとき $a_{i+1}$ に赤色を塗ってしまうと $r$ にすることが出来ず、 $a_1, \dots a_{i}$ までで $r$ を作る必要があります。
$a_{i+1}$ を赤色に塗らない場合、青に塗るか緑に塗るかの2択ですから、
　 $dp1[i+1][r] = 2 \times dp1[i][r]$
　 $dp2[i+1][r] = dp2[i][r]$
となります

(2) $a_{i+1} \leq r$ のとき
以下の2通りが考えられます：
　・ $a_1, \dots a_{i}$ までで $r$ を作っておき、 $a_{i+1}$ は緑か青に塗る
　・ $a_1, \dots a_{i}$ までで $r - a_{i+1}$ を作っておき、 $a_{i+1}$ は赤に塗る
よって、次のようになります。
　 $dp1[i+1][r] = 2 \times dp1[i][r] + dp1[i][r-a_{i+1}]$
　 $dp2[i+1][r] = dp2[i][r] + dp2[i][r-a_{i+1}]$

ソースコード

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int N;  cin >> N;
    int S = 0;
    int mod = 998244353;
    vector<int> a(N+1,0);
    for(int i=1; i<=N; i++){
        cin >> a[i];
        S += a[i];
    }

    vector<vector<ll>> dp1(N+1, vector<ll>(S+1,0));
    vector<vector<ll>> dp2(N+1, vector<ll>(S+1,0));
    dp1[0][0] = dp2[0][0] = 1;
    for(int i=0; i<N; i++){
        for(int r=0; r<=S; r++){
            dp1[i+1][r] = 2*dp1[i][r]%mod;
            dp2[i+1][r] = dp2[i][r]%mod;

            if(r>=a[i+1]){
                dp1[i+1][r] = (dp1[i+1][r] + dp1[i][r-a[i+1]]) % mod;
                dp2[i+1][r] = (dp2[i+1][r] + dp2[i][r-a[i+1]]) % mod;
            }
        }
    }

    ll ans = 1;
    // 3^N をもとめる
    for(int i=0; i<N; i++){
        ans = (ans*3)%mod;
    }

    // R > S/2 の場合の数の3倍を引く
    for(int r=S/2+1; r<=S; r++){
        ans = ans - 3*dp1[N][r];
        while(ans<0) ans += mod;
        ans%=mod;
    }

    // R = S/2 の場合の数の3倍を引き、R = G = S/2 の場合の数の3倍を足す
    if(S%2==0){
        ans = ans - 3*dp1[N][S/2];
    	while(ans<0) ans += mod;
    	ans = (ans + 3*dp2[N][S/2]) % mod;
    }
    cout << ans << endl;
}