はじめに

読み込み時間が長かったかと思いますが，じっと我慢していただきありがとうございます。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】に掲載されている50問(以下，上級50問精選)を解いていきます．

注意！

この記事には，間違い/非効率的なコードが多く含まれている可能性があります．ですが，ACをとれることは確認済です．
また，__問題135-138，141-146はまだ解いていません．__時間があったときに追記します．

関連記事

中級編はこちらかから
AtCoder100問精選をC言語で解く

問題101-110

101

問題のポイント

座標圧縮の実装をCでするのは大変でした！！！
中級編(精選100問の方)にも圧縮の問題は少しだけありましたが，今回のようにいもす法と合体した問題になると，余計複雑になりますね．

解答

# include<stdio.h>
# include <stdlib.h>
long long int sum[4001][4001];
int compare_int(const void *a, const void *b){return *(int*)a - *(int*)b;}
int main(void){
    int n;
    scanf("%d", &n);
    int xy[4][2000], xy_memo[2][4000];
    int i, j, k;
    for(i = 0; i < n; i++){
        scanf("%d%d%d%d", &xy[0][i], &xy[1][i], &xy[2][i], &xy[3][i]);
        xy_memo[0][i*2] = xy[0][i];
        xy_memo[1][i*2] = xy[1][i];
        xy_memo[0][i*2+1] = xy[2][i];
        xy_memo[1][i*2+1] = xy[3][i];
    }

    for(j = 0; j < 2; j++){
        qsort(xy_memo[j], 2*n, sizeof(int), compare_int);
    }
    
    int cnt[2];
    //xyd_memoをuniqueにする
    for(j = 0; j < 2; j++){
        cnt[j] = 1;
        for(i = 1; i < n*2; i++){
            if(xy_memo[j][cnt[j]-1] == xy_memo[j][i]){
                continue;
            }
            xy_memo[j][cnt[j]] = xy_memo[j][i];
            cnt[j]++;
        }
    }



    for(i = 0; i < 4001; i++){
        for(j = 0; j < 4001; j++){
            sum[i][j] = 0;
        }
    }
    int ind[4];
    for(i = 0; i < n; i++){
        
        //4つの座標について，それぞれの座圧後のindexを求める
        for(j = 0; j < 4; j++){
            int l = -1;
            int r = cnt[j%2];
            int mid;
            while(r - l > 1){
                mid = (r + l)/2;
                if(xy_memo[j%2][mid] <= xy[j][i]){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            l++;//累積和はindexが1だけずれるため
            ind[j] = l;
        }
        sum[ind[0]][ind[1]]++;
        sum[ind[2]][ind[1]]--;
        sum[ind[0]][ind[3]]--;
        sum[ind[2]][ind[3]]++;
    }
    for(i = 1; i <= cnt[0]; i++){
        for(j = 1; j <= cnt[1]; j++){
            sum[i][j] += sum[i-1][j];
        }
    }
    for(i = 1; i <= cnt[0]; i++){
        for(j = 1; j <= cnt[1]; j++){
            sum[i][j] += sum[i][j-1];
        }
    }
    long long int ans = 0;
    for(i = 1; i < cnt[0]; i++){
        for(j = 1; j < cnt[1]; j++){
            if(sum[i][j] > 0){
                long long int dx = xy_memo[0][i] - xy_memo[0][i-1];
                long long int dy = xy_memo[1][j] - xy_memo[1][j-1];
                ans += dx * dy;
            }
        }
    }

    printf("%lld\n", ans);

    
}

102

問題のポイント

問題の解説には，”C++ 言語では map というものが用意されている”とありますが，Cにはないんでしょうか．自作するしかない？

解答

# include<stdio.h>
# include<stdlib.h>
int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(void){
    int n;
    scanf("%d", &n);
    int i, a[100000], a_sort_tmp[100000], a_sort[100000];
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
        a_sort_tmp[i] = a[i];
    }
    if(n == 1){
        printf("0\n");
        return 0;
    }
    qsort(a_sort_tmp, n, sizeof(int), compare_int);
    //a_sort_tmpを一意の配列にする
    int cnt = 1;
    a_sort[0] = a_sort_tmp[0];
    for(i = 1; i < n; i++){
        if(a_sort[cnt - 1] == a_sort_tmp[i]){
            continue;
        }
        a_sort[cnt] = a_sort_tmp[i];
        cnt++;
    }
    for(i = 0; i < n; i++){
        //a[i]がa_sortの何番目かを調べる
        if(a[i] == a_sort[cnt-1]){
            printf("%d\n", cnt-1);
            continue;
        }
        int r = cnt-1;
        int l = 0;
        while(r - l != 1){
            int mid = (r + l)/2;
            if(a_sort[mid] <= a[i]){
                l = mid;
            }else{
                r = mid;
            }
        }
        printf("%d\n", l);
    }
}

103

問題のポイント

3次元座圧いもすですね．
2次元の場合とイメージするのが大変ですが，実装力があれば難しくはないと思います。

解答

# include <stdio.h>
# include <stdlib.h>
int compare_int(const void *a, const void *b){return *(int*)a - *(int*)b;}
long long int sum[101][101][101];
long long int sum_v[101][101][101];
int xyd_memo[3][100];
int main(void){
    int n, k;
    scanf("%d%d", &n, &k);
    int xyd[50][6];
    int i, j, ii, jj;
    int x1, y1, d1, x2, y2, d2;
    for(i = 0; i < n; i++){
        for(j = 0; j < 6; j++){
            scanf("%d", &xyd[i][j]);
            xyd_memo[j%3][2*i+j/3] = xyd[i][j];
        }
    }

    //xyd_memoをソートする
    for(j = 0; j < 3; j++){
        qsort(xyd_memo[j], n*2, sizeof(int), compare_int);
    }
    int cnt[3];
    //xyd_memoをuniqueにする
    for(j = 0; j < 3; j++){
        cnt[j] = 1;
        for(i = 1; i < n*2; i++){
            if(xyd_memo[j][cnt[j]-1] == xyd_memo[j][i]){
                continue;
            }
            xyd_memo[j][cnt[j]] = xyd_memo[j][i];
            cnt[j]++;
        }
    }
    long long int dx, dy, dd;
    //それぞれの枠の体積を求める
    for(i = 1; i < cnt[0]; i++){
        for(j = 1; j < cnt[1]; j++){
            for(ii = 1; ii < cnt[2]; ii++){
                dx = xyd_memo[0][i] - xyd_memo[0][i-1];
                dy = xyd_memo[1][j] - xyd_memo[1][j-1];
                dd = xyd_memo[2][ii] - xyd_memo[2][ii-1];
                sum_v[i][j][ii] = dx * dy * dd;
            }
        }
    }

    //いもす法の下準備をする
    for(i = 0; i < 101; i++){
        for(j = 0; j < 101; j++){
            for(ii = 0; ii < 101; ii++){
                sum[i][j][ii] = 0;
            }
        }
    }
    int ind[6];
    for(i = 0; i < n; i++){
        //6つの座標について，それぞれの座圧後のindexを求める
        for(j = 0; j < 6; j++){
            int l = -1;
            int r = cnt[j%3];
            int mid;
            while(r - l > 1){
                mid = (r + l)/2;
                if(xyd_memo[j%3][mid] <= xyd[i][j]){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            l++;//累積和はindexが1だけずれるため
            ind[j] = l;
        }
        sum[ind[0]][ind[1]][ind[2]]++;
        sum[ind[3]][ind[1]][ind[2]]--;
        sum[ind[0]][ind[4]][ind[2]]--;
        sum[ind[3]][ind[4]][ind[2]]++;

        sum[ind[0]][ind[1]][ind[5]]--;
        sum[ind[3]][ind[1]][ind[5]]++;
        sum[ind[0]][ind[4]][ind[5]]++;
        sum[ind[3]][ind[4]][ind[5]]--;
    }

    //累積和をとる
    for(i = 0; i < cnt[0]; i++){
        for(j = 0; j < cnt[1]; j++){
            for(ii = 0; ii < cnt[2]; ii++){
                sum[i+1][j][ii] += sum[i][j][ii];
            }
        }
    }
    for(i = 0; i < cnt[1]; i++){
        for(j = 0; j < cnt[2]; j++){
            for(ii = 0; ii < cnt[0]; ii++){
                sum[ii][i+1][j] += sum[ii][i][j];
            }
        }
    }
    for(i = 0; i < cnt[2]; i++){
        for(j = 0; j < cnt[0]; j++){
            for(ii = 0; ii < cnt[1]; ii++){
                sum[j][ii][i+1] += sum[j][ii][i];
            }
        }
    }
    long long int ans = 0;
    for(i = 1; i < cnt[0]; i++){
        for(j = 1; j < cnt[1]; j++){
            for(ii = 1; ii < cnt[2]; ii++){
                if(sum[i][j][ii] >= k){
                    ans += sum_v[i][j][ii];
                }
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

104

問題のポイント

重なった部分の面積/体積，ではなく，区切られた領域の個数を求める問題です．
そのため，幅探索を行う必要があります．
私のやり方が良くないのかもしれないのですが，座圧をまじめに実装するとなると苦労しますね．
入力データをscanf→座圧する際に記録すべき点を記録→ソートする→配列を一意にする(同じ値をもつ配列を除く)→圧縮後の値でいもす法の下準備(1とか―1とかを代入する，圧縮後の値と圧縮前の値を対応付けるためには二分探索が必要)→いもす法の適用→幅探索，という感じですかね．いかにpythonとかが便利かってよくわかります．

解答

# include<stdio.h>
# include <stdlib.h>
long long int sum[2004][2004];
int queue[2][4016016];
int compare_int(const void *a, const void *b){return *(int*)a - *(int*)b;}
int main(void){
    int w, h;
    scanf("%d%d", &w, &h);
    int n;
    scanf("%d", &n);
    int xy[4][1000], xy_memo[2][2002];
    int i, j, k;
    for(i = 0; i < n; i++){
        scanf("%d%d%d%d", &xy[0][i], &xy[1][i], &xy[2][i], &xy[3][i]);
        xy_memo[0][i*2] = xy[0][i];
        xy_memo[1][i*2] = xy[1][i];
        xy_memo[0][i*2+1] = xy[2][i];
        xy_memo[1][i*2+1] = xy[3][i];
    }
    xy_memo[0][n*2] = w;
    xy_memo[1][n*2] = h;
    xy_memo[0][n*2+1] = 0;
    xy_memo[1][n*2+1] = 0;

    for(j = 0; j < 2; j++){
        qsort(xy_memo[j], n*2+2, sizeof(int), compare_int);
    }
    
    int cnt[2];
    //xyd_memoをuniqueにする
    for(j = 0; j < 2; j++){
        cnt[j] = 1;
        for(i = 1; i < n*2+2; i++){
            if(xy_memo[j][cnt[j]-1] == xy_memo[j][i]){
                continue;
            }
            xy_memo[j][cnt[j]] = xy_memo[j][i];
            cnt[j]++;
        }
    }
    for(i = 0; i < 2004; i++){
        for(j = 0; j < 2004; j++){
            sum[i][j] = 0;
        }
    }
    int ind[4];
    for(i = 0; i < n; i++){
        //4つの座標について，それぞれの座圧後のindexを求める
        for(j = 0; j < 4; j++){
            int l = -1;
            int r = cnt[j%2];
            int mid;
            while(r - l > 1){
                mid = (r + l)/2;
                if(xy_memo[j%2][mid] <= xy[j][i]){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            l++;//累積和はindexが1だけずれるため
            ind[j] = l;
        }
        sum[ind[0]][ind[1]]++;
        sum[ind[2]][ind[1]]--;
        sum[ind[0]][ind[3]]--;
        sum[ind[2]][ind[3]]++;
    }
    
    for(i = 1; i <= cnt[0]; i++){
        for(j = 1; j <= cnt[1]; j++){
            sum[i][j] += sum[i-1][j];
        }
    }
    for(i = 1; i <= cnt[0]; i++){
        for(j = 1; j <= cnt[1]; j++){
            sum[i][j] += sum[i][j-1];
        }
    }
    for(i = 0; i <= cnt[0]; i++){
        sum[i][0] = 10;
        sum[i][cnt[1]] = 10;
    }
    for(i = 0; i <= cnt[1]; i++){
        sum[0][i] = 10;
        sum[cnt[0]][i] = 10;
    }
    int ans = 0;

    // for(i = 0; i <= cnt[0]; i++){
    //     for(j = 0; j <= cnt[1]; j++){
    //         printf("%2d ", sum[i][j]);
    //     }
    //     printf("\n");
    // }

    for(i = 1; i <= cnt[0]; i++){
        for(j = 1; j <= cnt[1]; j++){
            if(sum[i][j]){
                continue;
            }
            sum[i][j] = -2;
            ans++;
            int l = 0;
            int r = 1;
            queue[0][0] = i;
            queue[1][0] = j;
            while(l != r){
                int q[2];
                q[0] = queue[0][l];
                q[1] = queue[1][l];
                
                l++;
                int list[4][2] = {q[0] + 1, q[1], q[0] - 1, q[1], q[0], q[1] + 1, q[0], q[1] - 1};
                for(int ii = 0; ii < 4; ii++){
                    int qx = list[ii][0];
                    int qy = list[ii][1];
                    if(1 <= qx && qx <= cnt[0] && 1 <= qy && qy <= cnt[1] && sum[qx][qy] == 0){
                        queue[0][r] = qx;
                        queue[1][r] = qy;
                        r++;
                        sum[qx][qy] = -ans;
                    }
                }
            }
        }
    }

    printf("%d\n", ans);

    
}

105

問題のポイント

半分全列挙の実装です．
上級50問精選の解説記事には，ルーレットの出玉のように，同じ数字を何度も使っていいという問題が用いられていましたが，今回の問題は同じ数字は1度までしか使えず，使う回数も決まっているという制約条件があります．そのため，一ひねり必要でしょう．
ちなみにですが，私はデバッグのときにsortがうまくされないというバグでかなりの時間を取られました(ソートができていないとは思っておらず，そもそもこの原因にたどり着くのにも時間がかかりました・・・)．原因としては，qsortを使うときに呼ぶ関数(下の解答例だとcompare_int)の返り値をa-bとしていたのですが，どうやらqsort側はint型しか受け取ることができず(私の勝手な推測ですが)，a-bがint型に収まらない場合にオーバーフローしてしまう，ということが原因でした．

解答

# include <stdio.h>
# include <math.h>
# include <stdlib.h>
long long int a1[21][1048576];//前半
long long int a2[21][1048576];//後半
int compare_int(const void *a, const void *b){
    if (*(long long int*)a - *(long long int*)b > 0){
        return 1;
    }else if(*(long long int*)a - *(long long int*)b < 0){
        return -1;
    }
    return 0;}
int main(void){
    long long int N, K, L, R;
    scanf("%lld%lld%lld%lld", &N, &K, &L, &R);
    long long int i, j, k;
    long long int a[40];
    for(i = 0; i < N; i++){
        scanf("%lld", &a[i]);
    }
    if(N == 1){
        if(L <= a[0] && a[0] <= R){
            printf("1\n");
        }else{
            printf("0\n");
        }
        return 0;
    }
    //半分に分ける
    long long int bit;
    long long int first_cnt = N/2;
    long long int last_cnt = N - first_cnt;
    long long int cnt;
    long long int ind1[21];
    long long int ind2[21];
    for(i = 0; i < 21; i++){
        ind1[i] = 0;
        ind2[i] = 0;
    }

    for(bit = 0; bit < (1 << first_cnt); bit++){
        long long int tmp = 0;
        cnt = 0;
        for(i = 0; i < first_cnt; i++){
            if(bit & (1 << i)){
                tmp += a[i];
                cnt++;
            }
        }
        a1[cnt][ind1[cnt]] = tmp;
        ind1[cnt]++;
    }

    for(j = 0; j <= first_cnt; j++){
        qsort(a1[j], ind1[j], sizeof(long long int), compare_int);
    }

    for(bit = 0; bit < (1 << last_cnt); bit++){
        long long int tmp = 0;
        cnt = 0;
        for(i = 0; i < last_cnt; i++){
            if(bit & (1 << i)){
                tmp += a[i+first_cnt];
                cnt++;
            }
        }
        a2[cnt][ind2[cnt]] = tmp;
        ind2[cnt]++;
    }

    long long int ans = 0;
    for(j = 0; j <= last_cnt; j++){
        //相方は？K-j
        if(K - j < 0 || K - j > first_cnt){
            continue;
        }
        //? <= R - tmp を満たす最大の？をa1[]から見つける
        for(int ii = 0; ii < ind2[j]; ii++){
            long long int tmp = a2[j][ii];
            long long int r = ind1[K - j];
            long long int l = -1;
            long long int mid;
            while(r - l > 1){
                mid = (r + l)/2;
                if(a1[K - j][mid] <= R - tmp){
                    l = mid;
                }else{
                    r = mid;
                }
            }
            if(l == -1){
                continue;
            }
            long long int l_u = l;

            //L - tmp <= ? を満たす最小の？をa1[]から見つける
            r = ind1[K - j];
            l = -1;
            while(r - l > 1){
                mid = (r + l)/2;
                if(L - tmp <= a1[K - j][mid]){
                    r = mid;
                }else{
                    l = mid;
                }
            }
            if(r == ind1[K - j]){
                continue;
            }
            long long int l_d = r;
            if(l_d <= l_u){
                if(a1[K - j][l_u] < L - tmp|| a1[K - j][l_u] > R- tmp){
                    // printf("error1! \n");
                    // printf("%lld %lld\n", l_d, l_u);
                }
                if(a1[K - j][l_d] < L- tmp || a1[K - j][l_d] > R- tmp){
                    // printf("error2! \n");
                    // printf("%lld %lld\n", l_d, l_u);
                }
                
                
                ans += l_u - l_d + 1;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}

106

問題のポイント

これも，前の問題と同じく，前半，後半に分けます．

解答

注意：上級50問精選に記載の通り，34点の部分点が取れるコードです．そのため，ACはとれません．

# include <stdio.h>
# include <stdlib.h>
long long int w_s[32768], v_s[32768], index_s[32768];
long long int w_sort[32768], v_sort[32768];
int compare_int(const void *a, const void *b){
    long long int a1 = w_s[*(long long int*)a];
    long long int b1 = w_s[*(long long int*)b];
    if(a1 - b1 > 0){
        return 1;
    }else if(a1 - b1 < 0){
        return -1;
    }
    return 0;
    }

int main(void){
    int N, W;
    scanf("%d%d", &N, &W);
    int v[200], w[200];
    int i, j, k;
    for(i = 0; i < N; i++){
        scanf("%d%d", &v[i], &w[i]);
    }
    int first_half = N/2;
    int last_half = N - first_half;

    long long int bit = 0;
    long long int tmp, tmp_w;
    for(bit = 0; bit < (1 << first_half); bit++){
        tmp = 0;
        tmp_w = 0;
        for(i = 0; i < first_half; i++){
            if(bit & (1 << i)){
                tmp += v[i];
                tmp_w += w[i];
            }
        }
        w_s[bit] = tmp_w;
        v_s[bit] = tmp;
        index_s[bit] = bit;
    }

    qsort(index_s, 1 << first_half, sizeof(long long int), compare_int);
    for(i = 0; i < (1 << first_half); i++){
        w_sort[i] = w_s[index_s[i]];
        v_sort[i] = v_s[index_s[i]];
    }
    for(i = 1; i < (1 << first_half); i++){
        if(v_sort[i] < v_sort[i-1]){
            v_sort[i] = v_sort[i-1];
        }
    }
    long long int ans = 0;
    for(bit = 0; bit < (1 << last_half); bit++){
        tmp = 0;
        tmp_w = 0;
        for(i = 0; i < last_half; i++){
            if(bit & (1 << i)){
                tmp += v[i+first_half];
                tmp_w += w[i+first_half];
            }
        }
        //後半の重さ合計はtmp_wなので，前半の重さW-tmp_w以下のもののみ選べる
        int r = (1 << first_half);
        int l = -1;
        while(r - l > 1){
            int mid = (r + l)/2;
            if(w_sort[mid] <= W - tmp_w){
                l = mid;
            }else{
                r = mid;
            }
        }
        if(l == -1){
            continue;
        }
        long long int ans_tmp = v_sort[l] + tmp;
        ans = ans > ans_tmp ? ans : ans_tmp;
    }
    printf("%lld\n", ans);
}

107

問題のポイント

難しかったです．分からなくて解答を見たのですが，実装にも時間がかかりました．
精選100問の「派閥」の問題の逆バージョン，みたいな問題ですが，DPを3回もつかわんといけんのですね...

解答

# include <stdio.h>
int p_dp[1048576];//あるbitに対して，独立集合なら1
int u_dp[1048576];//s1の頂点と結ばれていない頂点の集合．値はS2の集合
int s_dp[1048576];//s2の頂点集合の最大独立集合
int m;
int n;
int max(int a, int b){return a > b ? a : b;}
int calc_p_dp(int bit){
    int p = n/2;
    int q = n - p;
    if(p_dp[bit] != -1){
        return p_dp[bit];
    }
    int i, bit_tmp;
    for(i = 0; i < p; i++){//2進数の桁数
        if(bit & (1 << i)){
            bit_tmp = (bit & ~(1 << i));
            if(calc_p_dp(bit_tmp) == 0){
                p_dp[bit] = 0;
                return 0;
            }
        }
    }
    p_dp[bit] = 1;
    return 1;
}
int calc_u_dp(int bit){
    int p = n/2;
    int q = n - p;
    if(u_dp[bit] != -1){
        return u_dp[bit];
    }
    int i, bit_tmp;
    for(i = 0; i < p; i++){//2進数の桁数
        if(bit & (1 << i)){
            bit_tmp = (bit & ~(1 << i));
            int bit1 = calc_u_dp(bit_tmp);
            int bit2 = calc_u_dp(1 << i);
            u_dp[bit] = bit1 & bit2;
            return u_dp[bit];
        }
    }
    printf("error\n");
    return -1;
}

int calc_s_dp(int bit){
    int p = n/2;
    int q = n - p;
    if(s_dp[bit] != -1){
        return s_dp[bit];
    }
    int i, j, bit_tmp;
    s_dp[bit] = 0;
    for(i = 0; i < q; i++){//2進数の桁数
        if(bit & (1 << i)){
            bit_tmp = bit & ~(1 << i);
            s_dp[bit] = max(calc_s_dp(bit_tmp), s_dp[bit]);
        }
    }
    return s_dp[bit];
}
int calc_s_tmp_dp(int bit){
    int p = n/2;
    int q = n - p;
    if(s_dp[bit] != -1){
        return s_dp[bit];
    }
    int i, bit_tmp, cnt = 0;
    for(i = 0; i < q; i++){//2進数の桁数
        if(bit & (1 << i)){
            bit_tmp = bit & ~(1 << i);
            if(calc_s_tmp_dp(bit_tmp) == 0){
                s_dp[bit] = 0;
                return 0;
            }
            cnt++;
        }
    }
    s_dp[bit] = cnt;
    return cnt;
}
int main(void){
    
    scanf("%d%d", &n, &m);
    int a[780], b[780];
    int i, j, k;
    int p = n/2;
    int q = n - p;
    if(n == 1){
        printf("1\n");
        return 0;
    }
    for(i = 0; i < (1 << q); i++){
        p_dp[i] = -1;
        u_dp[i] = -1;
        s_dp[i] = -1;
    }
    

    //pの初期化
    p_dp[0] = 1;
    for(i = 0; i < p; i++){
        p_dp[1 << i] = 1;
    }
    for(i = 0; i < p; i++){
        for(j = i + 1; j < p; j++){
            p_dp[(1 << i) | (1 << j)] = 1;
        }
    }

    //sの初期化
    for(i = 0; i < q; i++){
        s_dp[1 << i] = 1;
    }
    for(i = 0; i < q; i++){
        for(j = i; j < q; j++){
            if(i == j){
                continue;
            }
            s_dp[(1 << i) | (1 << j)] = 2;
        }
    }
    s_dp[0] = 0;

    for(i = 0; i < m; i++){
        scanf("%d%d", &a[i], &b[i]);
        a[i]--;
        b[i]--;
        if(a[i] < p && b[i] < p){
            p_dp[(1 << a[i]) | (1 << b[i])] = 0;
        }
        if(a[i] >= p && b[i] >= p){
            s_dp[(1 << (a[i] - p)) | (1 << (b[i] - p))] = 0;
        }
    }
    int bit;
    
    for(bit = 0; bit < (1 << p); bit++){
        calc_p_dp(bit);
    }


    //uの初期化
    u_dp[0] = (1 << q) - 1;
    for(i = 0; i < p; i++){
        bit = (1 << q) - 1;
        for(j = 0; j < m; j++){
            if(a[j] == i && b[j] >= p){
                bit &= ~(1 << (b[j] - p));
            }
            if(b[j] == i && a[j] >= p){
                bit &= ~(1 << (a[j] - p));
            }
        }
        u_dp[1 << i] = bit;
    }
    
    for(bit = 0; bit < (1 << p); bit++){
        calc_u_dp(bit);
    }
    for(bit = 0; bit < (1 << q); bit++){
        calc_s_tmp_dp(bit);
    }
    
    for(bit = 0; bit < (1 << q); bit++){
        if(s_dp[bit] == 0){
            s_dp[bit] = -1;
        }
    }
    s_dp[0] = 0;
    for(i = 0; i < q; i++){
        s_dp[1 << i] = 1;
    }
    for(i = 0; i < q; i++){
        for(j = i; j < q; j++){
            if(i == j){
                continue;
            }
            s_dp[(1 << i) | (1 << j)] = 2;
        }
    }
    for(i = 0; i < m; i++){
        if(a[i] >= p && b[i] >= p){
            s_dp[(1 << (a[i] - p)) | (1 << (b[i] - p))] = 1;
        }
    }
    for(bit = 0; bit < (1 << q); bit++){
        calc_s_dp(bit);
        
    }
    
    int ans = 0;
    for(bit = 0; bit < (1 << p); bit++){
        if(p_dp[bit] == 1){
            int cnt = s_dp[u_dp[bit]];
            for(i = 0; i < p; i++){
                if((1 << i) & bit){
                    cnt++;
                }
                
            }
            ans = ans > cnt ? ans : cnt;
        }
    }
    printf("%d\n", ans);
    return 0;

}

108

問題のポイント

計算時間が厳しいですね．
解法が分からず解答を見てやったんですが，それでも計算時間の壁が厚かったです．
あまり理解していないgcc optimizeとかいう文章を入れたりしたら，うまくいきました．
これも後でどんなコマンドなのかしっかり確認したいです．

解答



# include <stdio.h>
# include <math.h>
# include <stdlib.h>
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
long long int ab[14348907][2], cd[14348907][2];
long long int cd_s[14348907][2], x[30], y[30];
int index_list_cd[14348907];
long long int tree[90000000], f_half_3pow, l_half_3pow;
int compare_int_cd(const void *a, const void *b){
    return cd[*(int*)a][0] - cd[*(int*)b][0] > 0 ? 1 : -1;
}
int compare_llint(const void *a, const void *b){
    return x[*(int*)a] - x[*(int*)b] > 0 ? 1 : -1;
}
long long max(long long a, long long b){
    return a > b ? a : b;
}
long long min(long long a, long long b){
    return a > b ? b : a;
}
long long int tmp2;
void segment_tree(){
    long long int i;
    tmp2 = 1;
    long long int n_ = l_half_3pow;
    while(tmp2 <= l_half_3pow){
        tmp2 *= 2;
    }
    //fill_data
    for(i = 0; i < tmp2; i++){
        tree[i + tmp2 - 1] = -100000000000000000;
    }

    //initialize
    for(i = 0; i < l_half_3pow; i++){
        tree[i + tmp2 - 1] = cd_s[i][1];
    }
    for(i = tmp2 - 2; i >= 0; i--){
        tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]);
    }
}

long long int rmq(long long int a, long long int b, long long int k, long long int l, long long int r){//[x, y)(0オリジン)の配列内の最小値を求める
    if(l >= r){
        r = tmp2;
    }
    if(r <= a || b <= l){
        return -100000000000000000;
    }
    if(a <= l && r <= b){
        return tree[k];
    }
    long long int vl = rmq(a, b, 2*k + 1, l, (l + r)/2);
    long long int vr = rmq(a, b, 2*k + 2, (l + r)/2, r);
    return max(vl, vr);
}

int main(void){
    long long int n, d;
    scanf("%lld%lld", &n, &d);
    long long int i, j, k;
    for(i = 0; i < n; i++){
        scanf("%lld%lld", &x[i], &y[i]);
    }
    int index_[30];
    for(i = 0; i < n; i++){
        index_[i] = i;
    }
    qsort(index_, n, sizeof(int), compare_llint);
    long long int x_[30], y_[30];
    for(i = 0; i < n; i++){
        x_[i] = x[index_[i]];
        y_[i] = y[index_[i]];
    }
    for(i = 0; i < n; i++){
        x[i] = x_[i];
        y[i] = y_[i];
    }
    // qsort(y, n, sizeof(long long int), compare_llint);
    int f_half = n / 2;
    int l_half = n - f_half;
    f_half_3pow = powl(3, f_half);
    l_half_3pow = powl(3, l_half);
    long long int a, b, tmp;//a:市場価値，b:貴重度
    for(i = 0; i < f_half_3pow; i++){
        a = 0;
        b = 0;
        tmp = i;
        for(j = 0; j < f_half; j++){

            if(tmp % 3 == 0){//フラグが0：Aのもの
                a += -x[j];
                b += -y[j];
            }else if(tmp % 3 == 1){//フラグが1：Bのもの
                //pass
            }else{//フラグが2：取らない
                a += x[j];
                b += y[j];
            }
            tmp /= 3;
        }
        ab[i][0] = a;
        ab[i][1] = b;
    }
    for(i = 0; i < l_half_3pow; i++){
        a = 0;
        b = 0;
        tmp = i;
        for(j = f_half; j < f_half + l_half; j++){
            if(tmp % 3 == 0){//フラグが0：Aのもの
                a += -x[j];
                b += -y[j];
            }else if(tmp % 3 == 1){//フラグが1：Bのもの
            }else{//フラグが2：取らない
                a += x[j];
                b += y[j];
            }
            tmp /= 3;
        }
        cd[i][0] = a;
        cd[i][1] = b;
        index_list_cd[i] = i;
    }
    qsort(index_list_cd, l_half_3pow, sizeof(int), compare_int_cd);
    for(i = 0; i < l_half_3pow; i++){
        cd_s[i][0] = cd[index_list_cd[i]][0];
        cd_s[i][1] = cd[index_list_cd[i]][1];
    }
    long long int ans = 0;
    segment_tree();
    long long int all_max = rmq(0, l_half_3pow, 0, 0, 0);
    for(i = 0; i < f_half_3pow; i++){
        long long int low = -ab[i][0] - d;
        long long int high = -ab[i][0] + d;
        long long int b_i = ab[i][1];
        if(all_max + b_i < ans){
            continue;
        }
        //low <= cd_s[j][0] <= high　を満たすjから
        //kouho = cd_s[j][1] + b_i を計算し
        //ans =  max(ans, kouho)を計算
        
        //1：low <= cd_s[j][0]を満たすjを見つける
        int right = l_half_3pow;
        int left = 0;
        while(right - left > 1){
            int mid = (right + left)/2;
            if(low <= cd_s[mid][0]){
                right = mid;
            }else{
                left = mid;
            }
        }
        int j_low = right;
        // //2:cd_s[j][0] <= highを満たすjを見つける
        right = l_half_3pow;
        left = 0;
        while(right - left > 1){
            int mid = (right + left)/2;
            if(cd_s[mid][0] <= high){
                left = mid;
            }else{
                right = mid;
            }
        }
        int j_high = left;
        ans = max(rmq(j_low, j_high + 1, 0, 0, 0) + b_i, ans);
    }
    printf("%lld\n", ans);
    return 0;
}

109

問題のポイント

行列計算べた書きしちゃってすみません．
おそらくこの問題は解説にもある通り，行列累乗の考え方を使わずに解ける問題でしょう($O(n)$で間に合うため)．

解答

# include <stdio.h>

int main(void){
    long long int n, m;
    scanf("%lld%lld", &n, &m);
    long long int i;
    n -= 3;
    long long int k = 1;
    long long int a[2][2] = {1, 1, 1, 0};
    long long int f[2][2] = {1, 1, 1, 0};
    long long int f_n[2][2], a_n[2][2];
    for(i = 0; i < 25; i++){
        if((k << i) & n){
            a_n[0][0] = a[0][0] * f[0][0] + a[0][1] * f[1][0];
            a_n[0][1] = a[0][0] * f[0][1] + a[0][1] * f[1][1];
            a_n[1][0] = a[1][0] * f[0][0] + a[1][1] * f[1][0];
            a_n[1][1] = a[1][0] * f[0][1] + a[1][1] * f[1][1];
            a[0][0] = a_n[0][0] % m;
            a[1][0] = a_n[1][0] % m;
            a[0][1] = a_n[0][1] % m;
            a[1][1] = a_n[1][1] % m;
        }
        //fを2乗する
        f_n[0][0] = f[0][0] * f[0][0] + f[0][1] * f[1][0];
        f_n[0][1] = f[0][0] * f[0][1] + f[0][1] * f[1][1];
        f_n[1][0] = f[1][0] * f[0][0] + f[1][1] * f[1][0];
        f_n[1][1] = f[1][0] * f[0][1] + f[1][1] * f[1][1];
        for(int ii = 0; ii < 2; ii++){
            for(int jj = 0; jj < 2; jj++){
                f[ii][jj] = f_n[ii][jj] % m;
            }
        }
        

    }

    printf("%lld\n", a[0][0]);
    return 0;
}

110

問題のポイント

分からなくて解答見たのですが，こりゃ分かるわけないわって問題でした．
解答を読んで実装した上でもいくつか落とし穴があるので注意
具体的には，
1，mがk以下のときの処理の場合分けを忘れない
2，and，xorを行列のように計算するとき，1に相当するのは，二進数ですべての桁が1で埋まっているものなので気を付ける(ここらへん，解説スライドはミスリードを誘うような文章です)
3，int, unsigned int とかの扱い(フォーマット指定子が%uなの初めて知った・・・)

解答

# include <stdio.h>
unsigned int mat[32][100][100], mat_ans[2][100][100];//第一成分の分だけ掛けた場合の値を入れる
int main(void){
    int k, m;
    scanf("%d%d", &k, &m);
    int i, j, q, p, r, s;
    unsigned int a[100], c[100];
    for(i = 0; i < k; i++){
        scanf("%u", &a[i]);
    }
    for(i = 0; i < k; i++){
        scanf("%u", &c[i]);
    }
    if(m <= k){
        printf("%u\n", a[m-1]);
        return 0;
    }
    unsigned int one;
    one = (1 << 32) - 1;

    //行列をm-k乗した場合の値を求める
    
    
    for(i = 0; i < k; i++){
        mat[0][0][i] = c[i];
        mat_ans[0][0][i] = c[i];
    }
    for(i = 1; i < k; i++){
        for(j = 0; j < k; j++){
            //行数-1　=　列数なら1，それ以外は0
            if(i - 1 == j){
                mat[0][i][j] = one;
                mat_ans[0][i][j] = one;
            }else{
                mat[0][i][j] = 0;
                mat_ans[0][i][j] = 0;
            }
        }
    }

    for(p = 1; p < 32; p++){
        for(i = 0; i < k; i++){
            for(j = 0; j < k; j++){
                mat[p][i][j] = 0;
                for(r = 0; r < k; r++){
                    mat[p][i][j] ^= mat[p-1][i][r] & mat[p-1][r][j];
                    
                }
            }
        }
    }

    for(p = 0; p < 32; p++){
        if((1 << p) & (m - k - 1)){

            for(i = 0; i < k; i++){
                for(j = 0; j < k; j++){
                    mat_ans[1][i][j] = 0;
                    for(r = 0; r < k; r++){
                        mat_ans[1][i][j] ^= mat[p][i][r] & mat_ans[0][r][j];
                    }
                }
            }

            for(r = 0; r < k; r++){
                for(s = 0; s < k; s++){
                    mat_ans[0][r][s] = mat_ans[1][r][s];
                }
            }

        }
    }

    unsigned int ans = 0;
    for(r = 0; r < k; r++){
        ans ^= mat_ans[0][0][r] & a[k - r - 1];
    }

    printf("%u\n", ans);
    return 0;
}

問題111-120

111

問題のポイント

このサイトとか見ると詳しく書いてあって勉強になります．

解答

# include <stdio.h>
int par[17][100000];
int d[100000];
int depth(int a){
    if(d[a] != -1){
        return d[a];
    }else{
        d[a] = depth(par[0][a]) + 1;
        return d[a];
    }
}
int main(void){
    int n;
    scanf("%d", &n);
    int k[100000], c;
    int i, j, ii, jj;
    

    for(i = 0; i < n; i++){
        par[0][i] = -1;
        d[i] = -1;
    }
    for(i = 0; i < n; i++){
        scanf("%d", &k[i]);
        for(j = 0; j < k[i]; j++){
            scanf("%d", &c);
            par[0][c] = i;
        }
    }

    for(i = 1; i < 17; i++){
        for(j = 0; j < n; j++){
            par[i][j] = par[i-1][par[i-1][j]];
        }
    }

    d[0] = 0;
    //まず，それぞれの頂点の深さdを求める
    for(i = 0; i < n; i++){
        depth(i);
        //printf("%d \n", d[i]);
    }

    int q;

    scanf("%d", &q);
    int u, v;
    
    for(ii = 0; ii < q; ii++){
        scanf("%d%d", &u, &v);
        int large_v = d[u] > d[v] ? u : v;
        int small_v = d[u] > d[v] ? v : u;

        int diff = d[u] - d[v] > 0 ? d[u] - d[v] : d[v] - d[u];
        for(i = 0; i < 17; i++){
            if(diff & (1 << i)){
                large_v = par[i][large_v];
            }
        }
        u = large_v;
        v = small_v;
        //printf("%d %d is same\n", d[u], d[v]);
        if(u == v){
            printf("%d\n", u);
            continue;
        }
        for(i = 16; i >= 0; i--){
            if(par[i][v] != par[i][u]){
                v = par[i][v];
                u = par[i][u];
            }
        }
        printf("%d\n", par[0][u]);
    }
    return 0;
}

112

問題のポイント

最小共通祖先の問題に落とし込めると気づくと解けますね．
111をといたあとにこの問題を解いたので気づけますが，突然解けって言われると難しいかもしれないですね．

解答

# include <stdio.h>
# include <stdlib.h>

int x[99999], y[99999];
int d[100000];
int par[100000];
int cnt[100000], cnts[100000];
int *tree[100000];
int par_list[17][100000];
int DFS(int p, int q){
    int i;
    for(i = 0; i < cnt[p]; i++){
        if(q == tree[p][i]){
            continue;
        }
        par[tree[p][i]] = p;
        d[tree[p][i]] = d[p] + 1;
        DFS(tree[p][i], p);
    }
    return 0;
}

int main(void){
    int n;
    scanf("%d", &n);
    int i, j, k, a, b, q;
    for(i = 0; i < n; i++){
        cnt[i] = 0;
        cnts[i] = 0;
    }
    for(i = 0; i < n-1; i++){
        scanf("%d%d", &x[i], &y[i]);
        x[i]--;
        y[i]--;
        cnt[x[i]]++;
        cnt[y[i]]++;
    }

    for(i = 0; i < n; i++){
        tree[i] = (int *)malloc(sizeof(int) * (cnt[i] + 1));
    }
    for(i = 0; i < n; i++){
        tree[x[i]][cnts[x[i]]] = y[i];
        cnts[x[i]]++;
        tree[y[i]][cnts[y[i]]] = x[i];
        cnts[y[i]]++;
        d[i] = -1;
    }

    d[0] = 0;
    DFS(0, -1);
    
    // for(i = 0; i < n; i++){
    //     printf("par[%d] = %d\n", i, par[i]);
    // }
    // for(i = 0; i < n; i++){
    //     printf("d[%d] = %d\n", i, d[i]);
    // }

    for(i = 0; i < n; i++){
        par_list[0][i] = par[i];
    }

    for(i = 1; i < 17; i++){
        for(j = 0; j < n; j++){
            par_list[i][j] = par_list[i-1][par_list[i-1][j]];
        }
    }
    int v_max, v_min;
    scanf("%d", &q);
    for(int ii = 0; ii < q; ii++){
        scanf("%d%d", &a, &b);
        a--;
        b--;
        int ans = 1;
        v_max = d[a] > d[b] ? a : b;
        v_min = d[a] > d[b] ? b : a;
        int diff = d[v_max] - d[v_min];
        for(i = 0; i < 17; i++){
            if(diff & (1 << i)){
                v_max = par_list[i][v_max];
            }
        }
        ans += diff;
        if(v_max == v_min){
            printf("%d\n", ans);

            continue;
        }
        a = v_max;
        b = v_min;
        for(i = 16; i >= 0; i--){
            if(par_list[i][a] != par_list[i][b]){
                a = par_list[i][a];
                b = par_list[i][b];
                ans += (1 << i)*2;
            }
        }
        printf("%d\n", ans + 2);
    }

    return 0;
}

113

問題のポイント

ダブリングってこういう問題にも適用できるんですね．

解答

# include <stdio.h>
int x_go_max[17][100000];//2^17日>10^5日あれば，端の町から端の町まで移動できる
int a[100000], b[100000];
int main(void){
    int n, i, j;
    scanf("%d", &n);
    int x[100000];
    for(i = 0; i < n; i++){
        scanf("%d", &x[i]);
    }
    int l;
    scanf("%d", &l);
    int q;
    scanf("%d", &q);
    
    for(i = 0; i < q; i++){
        scanf("%d%d", &a[i], &b[i]);
        a[i]--;
        b[i]--;
    }
    
    for(i = 0; i < n; i++){
        //2分探索で，最大どこからどこまで移動できるかを計算
        if(x[n-1] - x[i] <= l){
            x_go_max[0][i] = n-1;
            continue;
        }
        int left = i+1;
        int right = n;
        while(right - left > 1){
            int mid = (right - left)/2 + left;
            if(x[mid] - x[i] <= l){
                left = mid;
            }else{
                right = mid;
            }
        }
        x_go_max[0][i] = left;
    }

    for(i = 1; i < 17; i++){
        for(j = 0; j < n; j++){
            x_go_max[i][j] = x_go_max[i-1][x_go_max[i-1][j]];
        } 
    }

    for(i = 0; i < q; i++){
        int ans = 0;
        int c = a[i] > b[i] ? b[i] : a[i];
        int d = a[i] > b[i] ? a[i] : b[i];
        //cからd(c < d)に移動することを考える
        for(j = 16; j >= 0; j--){
            if(x_go_max[j][c] < d){//(1 << j)日で移動できない場合
                c = x_go_max[j][c];
                ans += 1 << j;
            }
        }
        printf("%d\n", ans+1);
    }
    return 0;
}

114

問題のポイント

恐らくもっといい方法があるとは思いますが，なんとか解けました．
検索すれば，解説記事が多く落ちている問題なので，そちらを参考にした方がよいかと・・・

解答


# include <stdio.h>
# include <stdlib.h>
int a[200000], b[200000], l[200000], f[200000], s[100000], t[100000];
int l_min[200000];
int queue[100000000];
int cnt[200000], cnts[200000], *tree[200000], *tree_l[200000];
int *tree_s[200000], *tree_sd[200000],xi[200000], yi[200000];
int cnt_d[200000], cnts_d[200000];
int tree_d[200000];
int par[200000];
int next[200000][25], d[200000], next_min[200000][25];
int min(int x, int y){return x > y ? y : x;}
int root(int x){
    if(par[x] == x){return x;}
    return par[x] = root(par[x]);
}

int unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry){
        return 0;
    }
    par[rx] = ry;
    return 1;
}

int same(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry){
        return 1;
    }
    return 0;
}

int dfs(int x, int y){
    int i;
    for(i = 0; i < cnt_d[x]; i++){
        if(tree_s[x][i] == y){
            continue;
        }
        next[tree_s[x][i]][0] = x;
        d[tree_s[x][i]] = d[x] + 1;
        dfs(tree_s[x][i], x);
    }
    return 0;
}

int compare_int(const void *x, const void *y){
    return -l_min[*(int*)x] + l_min[*(int*)y];
}
int main(void){
    int n, m, k, q;
    scanf("%d%d%d%d", &n, &m, &k, &q);
    int i, j;
    for(i = 0; i < n; i++){
        cnt[i] = 0;
        cnts[i] = 0;
    }
    for(i = 0; i < n; i++){
        l_min[i] = 1000000001;
    }
    for(i = 0; i < m; i++){
        scanf("%d%d%d", &a[i], &b[i], &l[i]);
        a[i]--;
        b[i]--;
        cnt[a[i]]++;
        cnt[b[i]]++;
    }
    for(i = 0; i < k; i++){
        scanf("%d", &f[i]);
        f[i]--;
        queue[i] = f[i];
        l_min[f[i]] = 0;
    }

    for(i = 0; i < q; i++){
        scanf("%d%d", &s[i], &t[i]);
        s[i]--;
        t[i]--;
    }
    for(i = 0; i < n; i++){
        tree[i] = (int *)malloc(sizeof(int) * (cnt[i] + 1));
        tree_l[i] = (int *)malloc(sizeof(int) * (cnt[i] + 1));
    }
    for(i = 0; i < m; i++){
        tree[a[i]][cnts[a[i]]] = b[i];
        tree[b[i]][cnts[b[i]]] = a[i];
        tree_l[a[i]][cnts[a[i]]] = l[i];
        tree_l[b[i]][cnts[b[i]]] = l[i];

        cnts[a[i]]++;
        cnts[b[i]]++;
    }
    //ダイグストラ法である都市におけるお祭りしている都市からの最小距離dを求める
    int right = k;
    int left = 0;
    while(right != left){
        int tmp = queue[left];
        left++;
        for(i = 0; i < cnt[tmp]; i++){
            int tree_i = tree[tmp][i];
            if(l_min[tree_i] > tree_l[tmp][i] + l_min[tmp]){
                l_min[tree_i] = tree_l[tmp][i] + l_min[tmp];
                queue[right] = tree[tmp][i];
                right++;
            }
        }
    }
    //debug：最短距離
    // for(i = 0; i < n; i++){
    //     printf("--- i = %d, l_min = %d\n", i, l_min[i]);
    // }

    //l_min をソート
    int node_index[100000];
    for(i = 0; i < n; i++){
        node_index[i] = i;
    }
    //クラスカル法で,n-1個の辺を持つ最小全域木を作成する，
    //辺は，その重さが大きい順から張る
    qsort(node_index, n, sizeof(int), compare_int);
    for(i = 0; i < n; i++){
        par[i] = -1;
    }
    int v_cnt = 0;
    int flag = 0;
    for(i = 0; i < n; i++){
        cnt_d[i] = 0;
        cnts_d[i] = 0;
    }

    //DEBUG:祭りの町から距離が遠い順にソートした結果を確認
    // for(i = 0; i < n; i++){
    //     printf("%d ", node_index[i]);
    // }
    // printf("\n");
    for(i = 0; i < n; i++){
        par[node_index[i]] = node_index[i];
        for(j = 0; j < cnt[node_index[i]]; j++){
            if(par[node_index[i]] != -1 && par[tree[node_index[i]][j]] != -1 && same(node_index[i], tree[node_index[i]][j]) == 0 ){//違う親ならば
                unite(node_index[i], tree[node_index[i]][j]);
                xi[v_cnt] = node_index[i];
                yi[v_cnt] = tree[node_index[i]][j];
                cnt_d[xi[v_cnt]]++;
                cnt_d[yi[v_cnt]]++;
                v_cnt++;
                if(v_cnt == n-1){
                    flag = 1;
                    break;
                }
            }
        }
        if(flag == 1){
            break;
        }
    }
    for(i = 0; i < n; i++){
        tree_sd[i] = malloc(sizeof(int) * (cnt_d[i] + 1));
        tree_s[i] = malloc(sizeof(int) * (cnt_d[i] + 1));
    }
    for(i = 0; i < n - 1; i++){
        tree_sd[xi[i]][cnts_d[xi[i]]] = l_min[yi[i]];
        tree_sd[yi[i]][cnts_d[yi[i]]] = l_min[xi[i]];
        tree_s[xi[i]][cnts_d[xi[i]]] = yi[i];
        tree_s[yi[i]][cnts_d[yi[i]]] = xi[i];
        cnts_d[xi[i]]++;
        cnts_d[yi[i]]++;
    }
    next[0][0] = 0;
    d[0] = 0;
    dfs(0, -1);
    for(i = 0; i < n; i++){
        next_min[i][0] = l_min[next[i][0]];
    }

    for(i = 1; i < 25; i++){
        for(j = 0; j < n; j++){
            next[j][i] = next[next[j][i-1]][i-1];
        }
    }

    for(i = 1; i < 25; i++){
        for(j = 0; j < n; j++){
            next_min[j][i] = min(next_min[next[j][i-1]][i-1], next_min[j][i-1]);
        }
    }


    // for(i = 0; i < n; i++){
    //     printf("%d \n", d[i]);
    // }
    // for(i = 0; i < n; i++){
    //     printf("%d \n", next_min[i][0]);
    // }

    for(int ii = 0; ii < q; ii++){
        //s[ii]からt[ii]の頂点へ移動する
        int ans = min(l_min[s[ii]], l_min[t[ii]]);
        int v_max = d[s[ii]] > d[t[ii]] ? s[ii] : t[ii];
        int v_min = d[s[ii]] > d[t[ii]] ? t[ii] : s[ii];
        int diff = d[v_max] - d[v_min];
        for(i = 0; i < 25; i++){
            if(diff & (1 << i)){
                ans = min(ans, next_min[v_max][i]);
                v_max = next[v_max][i];
            }
        }
        if(v_max == v_min){
            printf("%d\n", ans);
            continue;
        }
        s[ii] = v_max;
        t[ii] = v_min;
        for(i = 24; i >= 0; i--){
            if(next[s[ii]][i] != next[t[ii]][i]){
                ans = min(ans, next_min[s[ii]][i]);
                ans = min(ans, next_min[t[ii]][i]);
                s[ii] = next[s[ii]][i];
                t[ii] = next[t[ii]][i];
            }
        }
        ans = min(ans, l_min[next[s[ii]][0]]);
        printf("%d\n", ans);
    }
    return 0;
}

115

問題のポイント

知っている人と知らない人で差がでる問題ですね．
上級50問精選にリンクのあった記事の問題(Nim)にうまく落とし込めることができます．
実装も楽でちょっとうれしい問題です(ならC使うなって話ですが．)

解答

# include <stdio.h>
int max(int a, int b){return a > b ? a : b;}
int min(int a, int b){return a > b ? b : a;}
int main(void){
    int n, i, j, k, xyz[3], m;
    int coord[3], coord_max[3], coord_min[3];
    int ans = 0;
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        for(j = 0; j < 3; j++){
            scanf("%d", &xyz[j]);
        }
        scanf("%d", &m);
        for(k = 0; k < 3; k++){
                coord_max[k] = -1;
                coord_min[k] = 1000000001;
            }
        for(j = 0; j < m; j++){
            scanf("%d%d%d", &coord[0], &coord[1], &coord[2]);
            for(k = 0; k < 3; k++){
                coord_max[k] = max(coord[k], coord_max[k]);
                coord_min[k] = min(coord[k], coord_min[k]);
            }
        }
        for(k = 0; k < 3; k++){
            ans ^= xyz[k] - coord_max[k] - 1;
            ans ^= coord_min[k];
        }
    }
    if(ans == 0){
        printf("LOSE\n");
    }else{
        printf("WIN\n");
    }
    return 0;
}

116

問題のポイント

複数の問題についてgrundy数を求めて，(理由はよくわからないが)xorをとる問題です．
grundyを求めるために，上級50問で紹介されていた記事の通り，遷移可能な状態のgrundyをメモ化再帰で求め，それらを集めたもののに含まれていない最小の非負整数を求める，とします．なんでこれで求まるかよく分からないですが．
ハマったポイントとして，メモ化再帰をするにあたり，grundy数をメモする行列matrix[whiteの個数][blackの個数]を定義したのですが，これの大きさを101×101としたらだめです．というのは，whiteの数は(黒が減る替わりに)増える可能性があるので，最大200個になる可能性があります．

解答

# include <stdio.h>

int mat[300][300];//-1:不明

int dfs(int w, int b){
    if(mat[w][b] != -1){
        return mat[w][b];
    }
    int g_list[300];
    for(int i = 0; i < 300; i++){
        g_list[i] = 0;
    }
    if(w){//1:白石を取り除く
        g_list[dfs(w-1, b)] = 1;
    }
    //3:黒石を1つ白石と交換
    if(b){
        g_list[dfs(w+1, b-1)] = 1;
    }
    //2:白石の数を超えない分だけ，黒石を1つ以上場から取り除く
    for(int i = 1; i <= w && i <= b; i++){//i:取り除く量
        g_list[dfs(w, b-i)] = 1;
    }
    for(int i = 0; i < 300; i++){
        if(g_list[i] == 0){
            mat[w][b] = i;
            return i;
        }
    }
}


int main(void){
    int i, j, n;
    scanf("%d", &n);
    int w, b;
    for(i = 0; i < 300; i++){
        for(j = 0; j < 300; j++){
            mat[i][j] = -1;
        }
    }
    int ans = 0;
    mat[0][0] = 0;//どちらの暮石も0個ならば負ける
    for(i = 0; i < n; i++){
        scanf("%d%d", &w, &b);
        ans ^= dfs(w, b);
    }
    if(ans == 0){
        printf("1\n");
    }else{
        printf("0\n");
    }
    return 0;
}

117

問題のポイント

こういう，実装にかかる時間>>>>>>解法を思いつくまでの時間，みたいな問題はいいですね．
問題をさらに小さな問題に分割して考えます．
頂点のみの場合はgrendy数が0だから，・・・という感じですね．

解答

# include <stdio.h>
# include <stdlib.h>
int x[100000], y[100000];
int cnt[100000], cnts[100000], *tree[100000];
int dfs(int a, int b){
    int ans = 0, i;
    for(i = 0; i < cnt[a]; i++){
        if(tree[a][i] == b){
            continue;
        }
        ans ^= dfs(tree[a][i], a) + 1;
    }
    return ans;
}

int main(void){
    int n, i, j;
    scanf("%d",&n);
    for(i = 0; i < n; i++){
        cnt[i] = 0;
        cnts[i] = 0;
    }
    for(i = 0; i < n-1; i++){
        scanf("%d%d", &x[i], &y[i]);
        x[i]--;
        y[i]--;
        cnt[x[i]]++;
        cnt[y[i]]++;
    }
    for(i = 0; i < n; i++){
        tree[i] = malloc((cnt[i] + 1) * sizeof(int));
    }
    for(i = 0; i < n-1; i++){
        tree[x[i]][cnts[x[i]]++] = y[i];
        tree[y[i]][cnts[y[i]]++] = x[i];
    }

    int ans = dfs(0, -1);
    if(ans == 0){
        printf("Bob\n");
    }else{
        printf("Alice\n");
    }
    return 0;
}

118

問題のポイント

ロリハことローリングハッシュの実装です．
ハッシュ値は1つでうまくいきましたが，確率で，ハッシュ値の衝突が起きてしまうため，複数のハッシュ値で検索した方がいいとか．
その分計算量も大きくなるんですけどね．

解答

# include <stdio.h>
# include <string.h>
int main(void){
    char t[1000001], p[10001];
    scanf("%s", t);
    scanf("%s", p);
    int i, j, k;
    int tlen, plen;
    tlen = strlen(t);
    plen = strlen(p);
    
    long long int thash = 0, phash = 0;
    long long int mod = 100000007;
    if(tlen < plen){
        return 0;
    }
    for(i = 0; i < plen; i++){
        phash += p[i];
        thash += t[i];
        if(i == plen - 1){
            continue;
        }
        phash *= 10;
        phash %= mod;
        thash *= 10;
        thash %= mod;
    }

    long long int tmp = 1;
    //10^(plen-2)%mod の値を求める
    for(i = 0; i < plen-1; i++){
        tmp *= 10;
        tmp %= mod;
    }
    for(i = 0; i < tlen - plen + 1; i++){
        if(thash == phash){
            printf("%d\n", i);
        }
        if(i == plen - tlen){
            continue;
        }
        thash = (thash - tmp * t[i])*10 + t[i+plen];
        while(thash < 0){
            thash += mod; 
        }
        thash %= mod;
        
    }

}

119

問題のポイント

二分探索で答えのlenを求めます
とはいっても，ロリハを使わずとも簡単にとけるっぽいのですが．
また，解答では，とりあえずbaseを適当な素数として10個くらい使っていますが，
いろいろ調べると，なんかいい決め方もあるそうです，よく理解できませんでしたが．
まあ，cは計算時間が余裕のある言語なので，baseを10個使って力業で解きました．
（ちなみに，baseは1つでmodを複数用意する，というやり方ではACが取れなかったのですが，何か理由があるのでしょうか？）
余談ですが，自分のPCの環境だとscanfで読みこめる文字数に制限があるらしく，今回の問題のように5000文字という長い文字列を扱う問題はテストができません．なので，長い文字列の入力例を使ってデバッグしたい場合は，AtCoderのコードテストを使ってデバッグする必要があります．

解答


# include <stdio.h>
# include <string.h>

long long int list[100][5001];
int main(void){
	int m = 10;
  	int base[] = {2, 3, 5, 7, 9, 11, 13, 17, 19, 23};
    int n;
    int i, j, k;
    char s[5001];
    scanf("%d", &n);
    scanf("%s", s);
	for(i = 0; i < n; i++){
    	s[i] -= 'a';
        s[i] += (char)1;
        if(s[i] <= 0){
            printf("errr");
        }
    }
    long long int mod = 9007199254740997;
    int left = 0;
    int right = n/2+1;
    int flag, mid;
    //lenを二分探索で求める
    //lenは，0以上，(文字列の長さ/2,を小数点以下切り捨てたもの)以下である
    while(right - left > 1){
        long long int hash[m];
		for(i = 0; i < m; i++){
	        hash[i] = 0;
		}
        mid = (left + right)/2;//文字列の長さ

        //以下midの検討

        //1:初期のhash値を計算
		for(j = 0; j < m; j++){
			for(i = 0; i < mid; i++){
				hash[j] += s[i];
				hash[j] %= mod;
				if(i == mid - 1){
					break;
				}
				hash[j] *= base[j];
				hash[j] %= mod;
			}
		}

        //2:10^(mid-1)%mod の値を求める
        long long int tmp[m];
		for(i = 0; i < m; i++){
	        tmp[i] = 1;
		}
		for(j = 0; j < m; j++){
			for(i = 0; i < mid - 1; i++){
				tmp[j] *= base[j];
				tmp[j] %= mod;
			}
		}

        //3:hash値のリストを作り，listに格納する
        //データ個数は，(文字列の長さn - 検証している文字列の長さmid)+1
		for(j = 0; j < m; j++){
        	list[j][0] = hash[j];
		}
		for(j = 0; j < m; j++){
			for(i = 0; i < n - mid; i++){
				hash[j] = (hash[j] - tmp[j] * s[i])*base[j] + s[i+mid];
				while(hash[j] < 0){
					hash[j] += mod; 
				}
				hash[j] %= mod;
				list[j][i + 1] = hash[j];
			}
		}
        //4:作成したhash値のリストにおいて，一致しているものがあるか検証
        //ただし，文字がかぶる箇所は検証しない
        flag = 0;
        for(i = 0; i < n - mid + 1; i++){
            for(j = i + mid; j < n - mid + 1; j++){
				int cnt = 0;
				for(k = 0; k < m; k++){
	            	if(list[k][i] == list[k][j]){
                   		cnt++;
               		}
				}
				if(cnt != m){
					continue;
				}
                //一致した場合
                flag = 1;
                break;
            }
            if(flag == 1){
              //printf("%d %d\n", i, j);
                break;
              
            }
        }

        //5:okなら(一致するものがあれば)flag = 1となっているので，r, lを更新
        if(flag == 1){
            left = mid;
        }else{
            right = mid;
        }
      	//printf("%d %d\n", mid, flag);
    }

    printf("%d\n", left);
    return 0;
}

120

問題のポイント

周期性のある文字列として，ロリハを使います．

解答

# include <stdio.h>
# include <string.h>
char s[500001];
char t[500001];
int match[500000];
int par[20][500000];
int tlen, slen;
int main(void){
    int i, j, k;
    int base[] = {2, 3, 5, 7, 9, 11, 13, 17, 19, 23};
    int m = 10;//baseの数
    scanf("%s", s);
    scanf("%s", t);

    tlen = strlen(t);
    slen = strlen(s);

    long long int mod = 1000000007;
    long long int thash[100], shash[100];

    //初期のハッシュ値を求める
    for(j = 0; j < m; j++){
        thash[j] = 0;
        shash[j] = 0;
        for(i = 0; i < tlen; i++){
            shash[j] += s[i%slen];
            thash[j] += t[i];
            if(i == tlen - 1){
                break;
            }
            thash[j] *= base[j];
            thash[j] %= mod;
            shash[j] *= base[j];
            shash[j] %= mod;
        }
    }

    long long int tmp[100];
    //base^(plen-1)%mod の値を求める
    for(j = 0; j < m; j++){
        tmp[j] = 1;
        for(i = 0; i < tlen-1; i++){
            tmp[j] *= base[j];
            tmp[j] %= mod;
        }
    }
    for(i = 0; i < slen; i++){
        match[i] = -1;
    }

    for(i = 0; i < slen; i++){
        int cnt = 0;
        for(j = 0; j < m; j++){
            if(thash[j] == shash[j]){
                cnt++;
            }
            shash[j] = (shash[j] - tmp[j] * s[i])*base[j] + s[(i+tlen)%slen];
            while(shash[j] < 0){
                shash[j] += mod; 
            }
            shash[j] %= mod;
        }
        if(cnt == m){
            match[i] = 0;
        }
    }

    //degub用，
    // for(i = 0; i < slen; i++){
    //     printf("%d\n", match[i]);
    // }

    //parの計算
    int chk[500000];
    for(i = 0; i < slen; i++){
        chk[i] = -1;
    }
    for(i = 0; i < slen; i++){
        if(chk[i] != -1){
            continue;
        }
        if(match[i] == -1){
            chk[i] = 0;
            continue;
        }
        int v = i;
        //前に探索
        int cnt = 1;
        while(1){
            v += tlen;
            v %= slen;
            if(match[v] != 0){
                break;
            }
            chk[v] = 1;
            cnt++;
            if(cnt > 500000){
                printf("-1\n");
                return 0;
            }
            continue;
        }

        //後ろに探索
        v = i;
        while(1){
            v -= tlen;
            while(v < 0){
                v += slen;
            }
            v %= slen;
            if(match[v] != 0){
                break;
            }
            chk[v] = 1;
            cnt++;
            if(cnt > 500000){
                printf("-1\n");
                return 0;
            }
            continue;
        }
        chk[i] = cnt;
    }
    int ans = 0;
    for(i = 0; i < slen; i++){
        ans = ans > chk[i] ? ans : chk[i];
    }
    printf("%d\n", ans);
    return 0;
}

問題121-130

121

問題のポイント

XORの問題は慣れが必要ですね・・・
ロリハを使わずに，KMP法でも解けるらしいので，それも勉強したいところです．

解答

# include <stdio.h>
//#pragma GCC optimize("O2")
long long int a[200000], b[200000];
long long int a_xor[200000], b_xor[200000];
int main(void){
    int n;
    int m = 15;//baseの数
    long long int base[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 43, 47, 53};
    long long int mod = 100000009;
    scanf("%d", &n);
    int i, j, k;
    for(i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    for(i = 0; i < n; i++){
        scanf("%lld", &b[i]);
    }
    //b_iとb_i+1のxorを求める, aも同様に求める
    for(i = 0; i < n; i++){
        b_xor[i] = (b[i] ^ b[(i+1)%n]) + 1;//b []が0になるのを防ぐため1を足す
        a_xor[i] = (a[i] ^ a[(i+1)%n]) + 1;
    }
    // for(i = 0; i < n; i++){
    //     printf("a: %d b: %d\n", a_xor[i], b_xor[i]);
    // }

    //初期(k=0)のhash値を求める
    long long int ahash[m], bhash[m];
    for(j = 0; j < m; j++){
        ahash[j] = 0;
        bhash[j] = 0;
        for(i = 0; i < n; i++){
            ahash[j] += a_xor[i];
            ahash[j] %= mod;
            bhash[j] += b_xor[i];
            bhash[j] %= mod;
            if(i == n - 1){
                break;
            }
            ahash[j] *= base[j];
            ahash[j] %= mod;
            bhash[j] *= base[j];
            bhash[j] %= mod;
        }
    }

    //base^(n-1)%mod の値を求める
    long long int tmp[m];
    for(j = 0; j < m; j++){
        tmp[j] = 1;
        for(i = 0; i < n - 1; i++){
            tmp[j] *= base[j];
            tmp[j] %= mod;
        }
    }

    //kでfor文を回す
    for(i = 0; i < n; i++){
        int cnt = 0;
        for(j = 0; j < m; j++){
            if(ahash[j] == bhash[j]){
                cnt++;
            }
        }
        
        if(cnt == m){
            printf("%lld %lld\n", i, b[0]^a[i]);
        }

        //ahashを1つずらす
        for(j = 0; j < m; j++){
            ahash[j] = (ahash[j] - tmp[j]*a_xor[i])*base[j] + a_xor[i];
          if(ahash[j] < 0){
          ahash[j] += -(ahash[j] / mod + 1)*mod;
          }
            while(ahash[j] < 0){
                ahash[j] += mod; 
            }
            ahash[j] %= mod;
        }
        
    }
    return 0;
}

122

問題のポイント

解説記事もわかりやすく(というか，難しいアルゴリズムではなく)仕組みを理解するのは簡単でしたが，実装とデバッグに思ったよりも時間がかかった問題でした．慣れと根性が必要でしょうね．

解答

# include <stdio.h>
# include <math.h>
long long int t[200000], l[200000], r[200000], h[200000];\
int main(void){
    int n;
    int m;
    int i, j, k;
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++){
        scanf("%lld%lld%lld", &t[i], &l[i], &r[i]);
        l[i]--;
        r[i]--;
    }
    int sq_n = pow(n, 0.5);
    int ind[1000];
    //indはcnt個のデータ(0からcnt-1)を持つ
    //区間の数は(cnt - 1)個

    ind[0] = -1;
    int cnt = 0;
    while(1){
        cnt++;
        ind[cnt] = ind[cnt-1] + sq_n;
        if(ind[cnt] >= n - 1){
            ind[cnt] = n - 1;
            cnt++;
            break;
        }
    }

    //DEBUG
    //for(i = 0; i < cnt; i++){
    //    printf("%d ", ind[i]);
    //}
    //printf("\n");
    //printf("cnt = %d \n", cnt);

    long long int same_h[1000];
    int flag[1000];//要素内の全部の高さが一致するならば1

    for(i = 0; i < n; i++){
        h[i] = 0;
    }
    for(i = 0; i < cnt - 1; i++){
        same_h[i] = 0;//要素数はcnt個
        flag[i] = 1;//flag = 1　ならば同じ区間のすべての高さが同じ
    }
    long long int ans = 0;
    for(i = 0; i < m; i++){
        //l[i]からr[i]までの番号の間の竹を切る
        //まず，indexの左右の番号を特定する
        for(j = 1; j <= cnt - 1; j++){
            if(l[i] <= ind[j]){
                break;
            }
        }
        int l_kukan = --j;
        for(j = 1; j <= cnt - 1; j++){
            if(r[i] <= ind[j]){
                break;
            }
        }
        int r_kukan = --j;
        //*_kukan は，0オリジンで何番目の区間にいるのかを示す(maxはcnt-1)

        //DEBUG
        //printf("i = %d, l[i] = %d, r[i] = %d, l_kukan = %d, r_kukan = %d\n", i, l[i], r[i], l_kukan, r_kukan);

        if(l_kukan == r_kukan){
            if(flag[l_kukan] == 1){
                ans += (r[i] - l[i] + 1) * (same_h[l_kukan] + t[i]);
                for(j = ind[l_kukan] + 1; j <= ind[l_kukan + 1]; j++){
                    h[j] = same_h[l_kukan];
                }
                for(j = l[i]; j <= r[i]; j++){
                    h[j] = -t[i];
                }
                flag[l_kukan] = 0;
            }else{//区間のすべての高さが同じでない場合：flag == 1の場合
                for(j = ind[l_kukan] + 1; j <= ind[l_kukan + 1]; j++){
                    if(l[i] <= j && j <= r[i]){
                        ans += h[j] + t[i];
                        h[j] = -t[i];
                    }
                }
            }
        }else{
            if(flag[l_kukan] == 1){
                ans += (ind[l_kukan + 1] - l[i] + 1) * (same_h[l_kukan] + t[i]);
                for(j = ind[l_kukan] + 1; j <= ind[l_kukan + 1]; j++){
                    h[j] = same_h[l_kukan];
                }
                for(j = l[i]; j <= ind[l_kukan + 1]; j++){
                    h[j] = -t[i];
                }
                flag[l_kukan] = 0;
            }else{//区間のすべての高さが同じでない場合：flag == 1の場合
                for(j = ind[l_kukan] + 1; j <= ind[l_kukan + 1]; j++){
                    if(l[i] <= j && j <= ind[l_kukan + 1]){
                        ans += h[j] + t[i];
                        h[j] = -t[i];
                    }
                }
            }


            for(j = l_kukan + 1; j <= r_kukan - 1; j++){
                if(flag[j] == 1){
                    ans += (ind[j+1] - ind[j]) * (same_h[j] + t[i]);
                    same_h[j] = -t[i];
                }else{
                    for(int ii = ind[j]+1; ii <= ind[j+1]; ii++){
                        ans += h[ii] + t[i];
                    }
                    flag[j] = 1;
                    same_h[j] = -t[i];
                }
            }

            if(flag[r_kukan] == 1){
                ans += (r[i] - (ind[r_kukan] + 1) + 1) * (same_h[r_kukan] + t[i]);
                for(j = ind[r_kukan] + 1; j <= ind[r_kukan + 1]; j++){
                    h[j] = same_h[r_kukan];
                }
                for(j = ind[r_kukan] + 1; j <= r[i]; j++){
                    h[j] = -t[i];
                }
                flag[r_kukan] = 0;
            }else{//区間のすべての高さが同じでない場合：flag == 1の場合
                for(j = ind[r_kukan] + 1; j <= ind[r_kukan + 1]; j++){
                    if(ind[r_kukan] + 1 <= j && j <= r[i]){
                        ans += h[j] + t[i];
                        h[j] = -t[i];
                    }
                }
            }

        }
        //printf("i = %d, ans = %lld\n", i, ans);
    }
    printf("%lld\n", ans);
    return 0;

}

123

問題のポイント

いろいろ応用が利くと聞いている最大流です．楽しいですね．

解答

# include <stdio.h>

int v1[1000], v2[1000], c[1000];
int d[1000][1000], cnt[1000];
int chk[1000];
int depth = 0;
int v, e;
int ans = 0;
int min(int a, int b){return a > b ? b : a;}
int dfs(int a, int f){
    depth++;
    int i, j;
    chk[a] = 0;
    for(i = v-1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == v - 1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            depth--;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            depth--;
            return tmp;
        }
    }
    depth--;
    return 0;
}
int main(void){
    
    scanf("%d%d", &v, &e);
    int i, j;
    
    for(i = 0; i < v; i++){
        for(j = 0; j < v; j++){
            d[i][j] = 0;
        }
    }
    for(i = 0; i < e; i++){
        scanf("%d%d%d", &v1[i], &v2[i], &c[i]);
        d[v1[i]][v2[i]] = c[i];
    }

    
    while(1){
        for(i = 0; i < v; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        dfs(0, 1000000000);
        if(ans == ans_before){
            break;
        }
    }
    printf("%d\n", ans);
    return 0;
}

124

問題のポイント

最大流最小フローの定理にうまく変換します．

解答

# include <stdio.h>
int min(int a, int b){return a > b ? b : a;}
int depth = 0;
int ans = 0;
int n, g, e;
int p[100], d[101][101], chk[101];
int dfs(int a, int f){
    depth++;
    int i, j;
    chk[a] = 0;
    for(i = n; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == n){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            depth--;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            depth--;
            return tmp;
        }
    }
    depth--;
    return 0;
}

int main(void){
    int a[10000], b[10000];
    scanf("%d%d%d", &n, &g, &e);
    int i, j, k;
    for(i = 0; i < n + 1; i++){
        for(j = 0; j < n + 1; j++){
            d[i][j] = 0;
        }
    }
    for(i = 0; i < g; i++){
        scanf("%d", &p[i]);
        d[p[i]][n] = 1;
    }
    for(i = 0; i < e; i++){
        scanf("%d%d", &a[i], &b[i]);
        d[a[i]][b[i]] = 1;
        d[b[i]][a[i]] = 1;
    }

    
    while(1){
        for(i = 0; i < n + 1; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        dfs(0, 1000000000);
        if(ans == ans_before){
            break;
        }
    }
    printf("%d\n", ans);
    return 0;

}

125

問題のポイント

もちろん，$(w \times h)$個のノードを考えるとTLEになりますので，どのように少なくするかがポイントです．
$(w + h)$個程度のノードにすればいいんじゃないかって考えたのですが，私には無理でした(おとなしく解説を見て実装しました)．

解答

# include <stdio.h>
int min(int a, int b){return a > b ? b : a;}
int ans = 0;
int chk[202];
int node;
int d[202][202];//最初のhは縦方向，次のwは横方向
int dfs(int a, int f){
    int i, j;
    chk[a] = 0;
    for(i = node-1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == node-1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            return tmp;
        }
    }
    return 0;
}
int main(void){
    int i, j, k;
    int h, w;
    int a[100][100];
    char tmp[100];
    int s_x, s_y, t_x, t_y;
    scanf("%d%d", &h, &w);
    for(i = 0; i < h; i++){
        scanf("%s", tmp);
        for(j = 0; j < w; j++){
            switch(tmp[j]){
            case '.':
                a[i][j] = 0;
                break;
            case 'o':
                a[i][j] = 1;
                break;
            case 'S':
                a[i][j] = 2;
                s_x = i;
                s_y = j;
                break;
            case 'T':
                a[i][j] = 3;
                t_x = i;
                t_y = j;
                break;
            default:
                printf("error!\n");
            }
        }
    }
    if(s_x == t_x || s_y == t_y){
        printf("-1\n");
        return 0;
    }
    node = h + w + 2;//0はs，1~hは縦，h+1~h+wは横，h+w+1はt
    
    for(i = 0; i < node; i++){
        for(j = 0; j < node; j++){
            d[i][j] = 0;
        }
    }
    //縦方向
    d[0][s_x+1] = 100000;//sをセット
    d[0][s_y+h+1] = 100000;
    d[t_x+1][node-1] = 100000;//tをセット
    d[t_y+h+1][node-1] = 100000;
    for(i = 0; i < h; i++){
        for(j = 0; j < w; j++){
            if(a[i][j] != 0){
                d[i+1][h+1+j] = 1;
                d[h+1+j][i+1] = 1;
            }
        }
    }

    // for(i = 0; i < node; i++){
    //     for(j = 0; j < node; j++){
    //         printf("%4d ", d[i][j]);
    //     }
    //     printf("\n");
    // }

    while(1){
        for(i = 0; i < node; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        dfs(0, 1000000000);
        if(ans == ans_before){
            break;
        }
    }

    printf("%d\n", ans);
    return 0;
    
}

126

問題のポイント

面白い問題ですね．ただ，今回の問題以外に2部グラフの使い道があまり思いつかないので，少し調べてみようと思いました．

解答

# include <stdio.h>
# include <stdlib.h>
int *tree[100000];
int cnt[100000], cnts[100000];
int colors[100000];
long long int black = 0, white = 0;
int dfs(int v, int color){
    colors[v] = color;
    if(color == 1){
        white++;
    }else if(color == -1){
        black++;
    }
    for(int i = 0; i < cnt[v]; i++){
        int v_i = tree[v][i];
        if(colors[v_i] == color){
            return 0;
        }
        if(colors[v_i] == 0 && dfs(v_i, -color) == 0){
            return 0;
        }
    }
    return 1;
}
int main(void){
    long long int n, m;
    scanf("%lld%lld", &n, &m);
    int a[100000], b[100000];
    int i, j;
    for(i = 0; i < n; i++){
        cnt[i] = 0;
        cnts[i] = 0;
        colors[i] = 0;//0:tbd -1:b 1:w
    }
    for(i = 0; i < m; i++){
        scanf("%d%d", &a[i], &b[i]);
        a[i]--;
        b[i]--;
        cnt[a[i]]++;
        cnt[b[i]]++;
    }
    for(i = 0; i < n; i++){
        tree[i] = malloc(sizeof(int) * (cnt[i] + 1));
    }
    for(i = 0; i < m; i++){
        tree[a[i]][cnts[a[i]]++] = b[i];
        tree[b[i]][cnts[b[i]]++] = a[i];
    }

    if(dfs(0, 1) == 0){
        printf("%lld\n", n*(n-1)/2 - m);
        
    }else{
        printf("%lld\n", black*white-m);
    }
    return 0;
}

127

問題のポイント

最大流・最小カットの内容を応用すれば解けます．
s→x，x→y，y→tは有向グラフなので，無向として実装しないように！

解答

# include <stdio.h>
int min(int a, int b){return a > b ? b : a;}
int d[202][202];
int X, Y, e;
int chk[202];
int x[100000], y[100000];
int ans = 0;
int dfs(int a, int f){
    int i, j;
    chk[a] = 0;
    for(i = X + Y + 1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == X + Y + 1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            return tmp;
        }
    }
    return 0;
}
int main(void){
    int i, j, k;
    scanf("%d%d%d", &X, &Y, &e);
    for(i = 0; i < X + Y + 2; i++){
        for(j = 0; j < X + Y + 2; j++){
            d[i][j] = 0;
        }
    }
    for(i = 0; i < e; i++){
        scanf("%d%d", &x[i], &y[i]);
        d[x[i] + 1][y[i] + 1 + X] = 1;
        d[0][x[i]+1] = 1;
        d[y[i] + 1 + X][X + Y + 1] = 1;
    }

    while(1){
        for(i = 0; i < X+Y+2; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        dfs(0, 100000);
        if(ans == ans_before){
            break;
        }
    }

    printf("%d\n", ans);
    return 0;
}

128

問題のポイント

二部マッチングの問題と知っていたら解法はおのずと見えると思います．

解答

# include <stdio.h>
int ans = 0;
int min(int a, int b){return a > b ? b : a;}
int d[202][202];
int chk[202];
int n;
int dfs(int a, int f){
    int i, j;
    chk[a] = 0;
    for(i = 2*n+1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == 2*n+1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            return tmp;
        }
    }
    return 0;
}

int main(void){
    scanf("%d", &n);
    int p[100], q[100];
    int r[100], s[100];
    int i, j, k;
    for(i = 0; i < 2*n + 2; i++){
        for(j = 0; j < 2*n + 2; j++){
            d[i][j] = 0;
        }
    }
    for(i = 0; i < n; i++){
        scanf("%d%d", &p[i], &q[i]);
        d[0][i+1] = 1; 
    }
    for(i = 0; i < n; i++){
        scanf("%d%d", &r[i], &s[i]);
        d[i+n+1][2*n+1] = 1;
    }

    

    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            if(p[i] < r[j] && q[i] < s[j]){
                d[i+1][j+1+n] = 1;//赤い点→青い点
            }
        }
    }



    while(1){
        for(i = 0; i < 2*n+2; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        dfs(0, 100000);
        if(ans == ans_before){
            break;
        }
    }

    printf("%d\n", ans);
    return 0;
}

129

問題のポイント

これも，二部マッチングの問題とわかれば，簡単に実装できます．
互いに素の実装を思い出す必要があります．

解答

# include <stdio.h>
int m, n;
int b[500], r[500];
int d[1002][1002];
int min(int x, int y){return x > y ? y : x;}
int gcd(int x, int y){
    if(x % y == 0){
        return y;
    }
    return gcd(y, x % y);
}


int chk[1002];
int ans;
int dfs(int a, int f){
    int i, j;
    chk[a] = 0;
    for(i = n + m + 1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == n + m + 1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            return tmp;
        }
    }
    return 0;
}

int main(void){
    int i, j, k;
    while(1){
        for(i = 0; i < m + n + 2; i++){
            for(j = 0; j < m + n + 2; j++){
                d[i][j] = 0;
            }
        }
        scanf("%d%d", &m, &n);
        if(m == 0 && n == 0){
            break;
        }
        for(i = 0; i < m; i++){
            scanf("%d", &b[i]);
            d[0][i+1] = 1;
        }
        for(i = 0; i < n; i++){
            scanf("%d", &r[i]);
            d[i+m+1][n+m+1] = 1;
            for(j = 0; j < m; j++){
                if(gcd(r[i], b[j]) != 1){
                    d[j+1][i+m+1] = 1;
                }
            }
        }

        // for(i = 0; i < m+n+2; i++){
        //     for(j = 0; j < m+n+2; j++){
        //         printf("%d ", d[i][j]);
        //     }
        //     printf("\n");
        // }
        ans = 0;
        while(1){
            for(i = 0; i < n + m +2; i++){
                chk[i] = -1;
            }
            int ans_before = ans;
            dfs(0, 100000);
            if(ans == ans_before){
                break;
            }
            
        }
        printf("%d\n", ans);
    }
    return 0;
}

130

問題のポイント

二部グラフの最大独立集合のサイズを求めます．

解答

# include <stdio.h>
int min(int a, int b){return a > b ? b : a;}
int r, c;
int mat[40][40];
int d[1602][1602];//始点:0　i行目j列目: i*c+j+1 終点:r*c+1
int chk[1602];
int dfs(int x, int y, int val){
    mat[x][y] = val;
    int xy[] = {x+1, y, x-1, y, x, y+1, x, y-1};
    for(int i = 0; i < 4; i++){
        int x_i = xy[i*2];
        int y_i = xy[i*2+1];
        if(x_i < 0 || x_i >= r || y_i < 0 || y_i >= c){
            continue;
        }
        if(mat[x_i][y_i] == 2){
            continue;
        }

        if(mat[x_i][y_i] == val){
            return 0;
        }
        if(mat[x_i][y_i] == 0 && dfs(x_i, y_i, -val) == 0){
            return 0;
        }
        if(mat[x][y] == 1 && mat[x_i][y_i] == -1){
            d[x*c+y+1][x_i*c+y_i+1] = 1;
        }else if(mat[x][y] == -1 && mat[x_i][y_i] == 1){
            d[x_i*c+y_i+1][x*c+y+1] = 1;
        }

    }
    return 1;
}



int ans = 0;
int b_dfs(int a, int f){
    int i, j;
    chk[a] = 0;
    for(i = c*r+1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == c*r+1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            return flow;
        }
        int tmp = b_dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            return tmp;
        }
    }
    return 0;
}

int main(void){
    
    int i, j, k;
    scanf("%d%d", &r, &c);
    
    char tmp[41];
    int v_cnt = 0;
    for(i = 0; i < r; i++){
        scanf("%s", tmp);
        for(j = 0; j < c; j++){
            if(tmp[j] == '.'){
                mat[i][j] = 0;
                v_cnt++;
            }else{
                mat[i][j] = 2;
            }
        }
    }

    for(i = 0; i < r*c+2; i++){
        for(j = 0; j < r*c+2; j++){
            d[i][j] = 0;
        }
    }

    for(i = 0; i < r; i++){
        for(j = 0; j < c; j++){
            if(mat[i][j] == 0){
                dfs(i, j, 1);
            }
            if(mat[i][j] == 1){
                d[0][i*c+j+1] = 1;
            }else if(mat[i][j] == -1){
                d[i*c+j+1][r*c+1] = 1;
            }
        }
    }

    // for(i = 0; i < c*r+2; i++){
    //     for(j = 0; j < c*r+2; j++){
    //         printf("%d ", d[i][j]);
    //     }
    //     printf("\n");
    // }

    while(1){
        for(i = 1; i < c*r+2; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        b_dfs(0, 100000);
        if(ans == ans_before){
            break;
        }
    }

    // for(i = 0; i < c; i++){
    //     for(j = 0; j < r; j++){
    //         printf("%d ", mat[i][j]);
    //     }
    //     printf("\n");
    // }


    printf("%d\n", v_cnt - ans);
    return 0;
}

問題131-140

131

問題のポイント

こういう，二部マッチングっぽくないけど，二部マッチングでとける問題って，面白いですね．
本家のサイトに解説がなかったので，私の解法を簡単に説明すると，
1．生成される可能性のある重さをリストアップ→ソートして重複するものを除く
2．s→(重さのリスト(1つ目))，(重さのリスト(2つ目))→tで重さ1の有向グラフを張る
3．切ることのできる(重さのリスト(1つ目))→(重さのリスト(2つ目))の組で重さ1の有向グラフを張る
4．最大マッチングを求める
5．必要な鉄塊は，最大マッチングの数＋最大マッチングで結ばれなかった頂点の数
として解きました．

解答

# include <stdio.h>
# include <stdlib.h>
int d[6002][6002];
int compare_int(const void* a, const void* b){
    return *(int *)a - *(int *)b;
}
int chk[6002];
int min(int a, int b){return a > b ? b : a;}
int ans = 0;
int m;
int dfs(int a, int f){
    int i, j;
    chk[a] = 0;
    for(i = 2*m+1; i >= 0; i--){
        if(chk[i] != -1 || d[a][i] == 0){
            continue;
        }
        if(i == 2*m+1){
            int flow = min(f, d[a][i]);
            ans += flow;
            d[i][a] += flow;
            d[a][i] -= flow;
            return flow;
        }
        int tmp = dfs(i, min(f, d[a][i]));
        if(tmp != 0){
            d[i][a] += tmp;
            d[a][i] -= tmp;
            return tmp;
        }
    }
    return 0;
}

int main(void){
    int n;
    scanf("%d", &n);
    int i, j, x[100], y[100], z[100];
    int w_tmp[6000], w[6000];
    for(i = 0; i < n; i++){
        scanf("%d%d%d", &x[i], &y[i], &z[i]);
    }
    //1個の鉄で最大60通りの切り方
    //最大100個なので，6000個が最大個数
    int cnt = 0;
    for(i = 0; i < n; i++){
        for(j = 1; j < x[i]; j++){
            w_tmp[cnt++] = j*y[i]*z[i];
        }
        for(j = 1; j < y[i]; j++){
            w_tmp[cnt++] = j*x[i]*z[i];
        }
        for(j = 1; j < z[i]; j++){
            w_tmp[cnt++] = j*y[i]*x[i];
        }
    }
    if(cnt == 0){
        printf("0\n");
        return 0;
    }
    qsort(w_tmp, cnt, sizeof(int), compare_int);
    m = 1;
    w[m-1] = w_tmp[0];
    for(i = 1; i < cnt; i++){
        if(w[m-1] == w_tmp[i]){
            continue;
        }else{
            w[m++] = w_tmp[i];
        }
    }
    //m個の異なる重さのおもりがある
    //そのため，2×m+2個の頂点で，最大フローを考える
    //始点：0，片方：1~m　もう片方：m+1~2×m，終点：2×m+1
    for(i = 0; i < 2*m+2; i++){
        for(j = 0; j < 2*m+2; j++){
            d[i][j] = 0;
        }
    }
    for(i = 1; i <= m; i++){
        d[0][i] = 1;
    }
    for(i = m+1; i <= 2*m; i++){
        d[i][2*m+1] = 1;
    }
    int w1, w2;
    int w1i, w2i;
    //切れるもの同士で有向辺を張る
    for(i = 0; i < n; i++){
        int x_comb = x[i] - 1;
        int y_comb = y[i] - 1;
        int z_comb = z[i] - 1;
        int vol = x[i]*y[i]*z[i]; 
        for(j = 0; j < x_comb + y_comb + z_comb; j++){
            if(j < x_comb){
                w1 = (j+1)*y[i]*z[i];
                w2 = vol - w1;
            }else if(j < x_comb + y_comb){
                w1 = (j-x_comb+1)*x[i]*z[i];
                w2 = vol - w1;
            }else{
                w1 = (j - x_comb - y_comb + 1)*x[i]*y[i];
                w2 = vol - w1;
            }
            //w[w1i] = w1, w[w2i] = w2を満たすw1i, w2iを求める
            for(int ii = 0; ii < 2; ii++){
                int w_tmp;
                if(ii == 0){
                    w_tmp = w1;
                }else{
                    w_tmp = w2;
                }
                int right = m;
                int left = 0;
                while(right - left > 1){
                    int mid = (right + left)/2;
                    if(w[mid] <= w_tmp){
                        left = mid;
                    }else{
                        right = mid;
                    }
                }
                if(ii == 0){
                    w1i = left;
                }else{
                    w2i = left;
                }
            }
            d[w1i+1][w2i + m + 1] = 1;
        }
    }

    while(1){
        for(i = 1; i < 2*m+2; i++){
            chk[i] = -1;
        }
        int ans_before = ans;
        dfs(0, 100000);
        if(ans == ans_before){
            break;
        }
    }
    printf("%d\n", (2*m-ans*2) + ans);//最大マッチングの数＋残ったノード数

}

132

問題のポイント

BITの基本的な実装問題です．
途中で値を変える場合の区間和→BIT
変えない場合の区間和→累積和
といった使い分けをすればよいそうですね．

実装には以下のサイトを参考にしました→
Binary Indexed Tree のはなし

解答

# include <stdio.h>
int n;
int bit[1000010];
void add(int a, int w){
    for(int x = a; x <= n; x += x & -x){
        bit[x] += w;
    }
}
int sum(int a){
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x){
        ret += bit[x];
    }
    return ret;
}
int main(void){
    int q;
    int x, y, com;
    scanf("%d%d", &n, &q);
    int i, j, k;
    for(i = 0; i < 1000010; i++){
        bit[i] = 0;
    }
    for(i = 0; i < q; i++){
        scanf("%d%d%d", &com, &x, &y);
        if(com == 0){
            add(x, y);
        }else{
            int ans = sum(y) - sum(x-1);
            printf("%d\n", ans);
        }
    }
    return 0;
}

133

問題のポイント

区間和，1変数の更新の場合は，1つのbitで済みますが，
区間和，区間で指定された変数の更新の場合は，2つのbitを持つ必要があります．

解答

# include <stdio.h>
int n;
int bit[2][100000];

void add(int a, int w){
    for(int x = a; x <= n; x += x & -x){
        bit[0][x] += w;
    }
}

void add_1(int a, int w){
    for(int x = a; x <= n; x += x & -x){
        bit[1][x] += w;
    }
}

void add_range(int a, int b, int w){
    add(a, -w*(a-1));
    add(b+1, w*b);
    add_1(a, w);
    add_1(b+1, -w);
}

int sum(int a){
    int ret1 = 0, ret2 = 0;
    for(int x = a; x > 0; x -= x & -x){
        ret1 += bit[0][x];
        ret2 += bit[1][x];
    }
    return ret1 + ret2*a;
}

int main(void){
    int q;
    int com, x, y;
    scanf("%d%d", &n, &q);
    int i, j, k;
    int s, t;
    for(i = 0; i < 100001; i++){
        bit[0][i] = 0;
        bit[1][i] = 0;
    }
    for(i = 0; i < q; i++){
        scanf("%d", &com);
        if(com == 0){
            scanf("%d%d%d", &s, &t, &x);
            add_range(s, t, x);
        }else{
            scanf("%d", &k);
            int ans = sum(k) - sum(k-1);
            printf("%d\n", ans);
        }
    }
    return 0;
}

134

問題のポイント

バブルソートの交換回数の計算にもbitが使える，という問題です．
ちょっと需要がニッチな気もしますが…

解答

# include <stdio.h>
# include <stdlib.h>

int n;
int list[200000];
long long int bit[1000010];
int ind[200000];
void add(int a, int w){
    for(int x = a; x <= n; x += x & -x){
        bit[x] += w;
    }
}
long long int sum(int a){
    long long int ret = 0;
    for(int x = a; x > 0; x -= x & -x){
        ret += bit[x];
    }
    return ret;
}
int compare_int(const void* a, const void* b){
    return list[*(int*)a] - list[*(int*)b];
}
int main(void){
    scanf("%d", &n);
    int i, j, k;
    for(i = 0; i < 1000010; i++){
        bit[i] = 0;
    }
    for(i = 0; i < n; i++){
        scanf("%d", &list[i]);
    }
    for(i = 0; i < n; i++){
        ind[i] = i;
    }
    qsort(ind, n, sizeof(int), compare_int);
    int a_ind[200000];
    for(i = 0; i < n; i++){
        a_ind[ind[i]] = i+1;
    }
    long long int ans = 0;
    for(i = 0; i < n; i++){
        ans += i - sum(a_ind[i]);
        add(a_ind[i], 1);
    }
    printf("%lld\n", ans);
    
    return 0;
}

139

問題のポイント

RMQって奥深いですね

# include <stdio.h>
# include <math.h>
long long int min(long long int x, long long int y){
    return x > y ? y : x;
}
long long int tree[400000], n;
long long int a_init;
long long int inf;
void segment_tree(){
    long long int i;
    long long int tmp = 1;
    long long int n_ = n;
    while(tmp <= n){
        tmp *= 2;
    }
    n = tmp;
    //fill_data
    for(i = 0; i < n; i++){
        tree[i + n - 1] = inf;
    }

    //initialize
    for(i = 0; i < n_; i++){
        tree[i + n - 1] = a_init;
    }
    for(i = n - 2; i >= 0; i--){
        tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
    }
}

void segment_tree_update(int x, int y){//配列xを値yに更新する
    long long int i;
    i = x + n - 1;
    tree[i] = y;
    // for(i = n - 2; i >= 0; i--){
    //     tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
    // }
    
    
    while(1){
        i = (i - 1)/2;
        tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
        if(i == 0){
            break;
        }
    }
}

long long int rmq(int a, int b, int k, int l, int r){//[x, y)(0オリジン)の配列内の最小値を求める
    if(l >= r){
        r = n;
    }
    if(r <= a || b <= l){
        return a_init;
    }
    if(a <= l && r <= b){
        return tree[k];
    }
    long long int vl = rmq(a, b, 2*k + 1, l, (l + r)/2);
    long long int vr = rmq(a, b, 2*k + 2, (l + r)/2, r);
    return min(vl, vr);
}

int main(void){
    long long int q, i, j;
    a_init = (1 << 31) - 1;
    inf = a_init;
    long long int com, x, y;
    scanf("%lld%lld", &n, &q);
    segment_tree();
    for(i = 0; i < q; i++){
        scanf("%lld%lld%lld", &com, &x, &y);
        if(com == 1){
            printf("%lld\n", rmq(x, y+1, 0, 0, 0));
        }else{
            segment_tree_update(x, y);
        }

        // printf("tree len is %d:", 2*n - 1);
        // for(j = 0; j < 2*n - 1; j++){
        //     printf("%lld ", tree[j]);
        // }
        // printf("\n");
    }
    return 0;
}

140

問題のポイント

これもRMQで解きます．
ただ，配列がループするので，その処理が少し厄介です．

RMQにbinary treeを使っても解けるのですが，もっと簡単に，
(a[i]の最小値，iは[i, i-k]の範囲) = $b_i(k)$とすると
$b_i(k) = min(a[i-k], b_i(k-1))$
として，メモ化再帰なりすれば，$O(N^2)$オーダーで解けるはずです．おそらく．

解答

# include <stdio.h>
int min(int a, int b){
    return a > b ? b : a;
}
long long int minll(long long int a, long long int b){
    return a > b ? b : a;
}
int a[2000];
int tree[400000], n;
int inf;
void segment_tree(){
    inf = 2000000000;
    long long int i;
    long long int tmp = 1;
    long long int n_ = n;
    while(tmp <= n){
        tmp *= 2;
    }
    n = tmp;
    //fill_data
    for(i = 0; i < n; i++){
        tree[i + n - 1] = inf;
    }
    //initialize
    for(i = 0; i < n_; i++){
        tree[i + n - 1] = a[i];
    }
    for(i = n - 2; i >= 0; i--){
        tree[i] = min(tree[2 * i + 1], tree[2 * i + 2]);
    }
}
int rmq(int a, int b, int k, int l, int r){//[x, y)(0オリジン)の配列内の最小値を求める
    if(l >= r){
        r = n;
    }
    if(r <= a || b <= l){
        return inf;
    }
    if(a <= l && r <= b){
        return tree[k];
    }
    int vl = rmq(a, b, 2*k + 1, l, (l + r)/2);
    int vr = rmq(a, b, 2*k + 2, (l + r)/2, r);
    return min(vl, vr);
}
int main(void){
    long long int x;
    scanf("%d%d", &n, &x);
    int n_init = n;
    long long int i, j, k;
    long long int ans;
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    segment_tree();
    //魔法をかける回数(0からn―1回)で全探索
    long long int Ans = 100000000000001;
    for(i = 0; i < n; i++){
        //1,魔法をかけるためのコストを計算
        ans = i*x;

        //2,それぞれのスライムjを召喚する最小のコストを計算し，足す
        for(j = 0; j < n_init; j++){
            long long int tmp = 2000000000;

            //a[j - i, j]の最小値を求める
            // for(k = 0; k <= i; k++){//k：返信させる回数
            //     int ind = j - k;
            //     if(ind < 0){
            //         ind += n;
            //     }
            //     tmp = min(tmp, a[ind]);
            // }
            //上記を高速化
            long long int tmp1 = inf;
            long long int tmp2 = inf;
            if(j - i < 0){
                tmp1 = rmq(0, j+1, 0, 0, 0);
                tmp2 = rmq(j - i + n_init, n_init, 0, 0, 0);
                tmp = min(tmp1, tmp2);
            }else{
                tmp = rmq(j - i, j + 1, 0, 0, 0);
            }
            ans += tmp;
        }
        Ans = minll(ans, Ans);
    }
    printf("%lld\n", Ans);
}

問題141-150

147

問題のポイント

最初はatan2関数を用いて偏角ソートをしたのですが，ACがとれませんでした．
おそらくatan2の精度の問題だと思われます．
外積，内積を計算する解法でACを取りました．

解答

# include <stdio.h>
# include <math.h>
# include <stdlib.h>
int x[2000], y[2000];
int x_i, y_i;
long long int n;
int ind[4000], ind_2[8000];
int compare_angle(const void* a_, const void* b_){//(1, 0)を基準に偏角ソートを厳密に行う関数(qsortで呼び出されることを想定)
    int a = *(int *)a_;
    int b = *(int *)b_;
    int x_a = x[a] - x_i;
    int y_a = y[a] - y_i;
    int x_b = x[b] - x_i;
    int y_b = y[b] - y_i;
    if(y_a == 0 && x_a > 0){
        return -1;
    }
    if(y_b == 0 && x_b > 0){
        return 1;
    }

    if(y_a > 0 && y_b < 0){
        return -1;
    }
    if(y_a < 0 && y_b > 0){
        return 1;
    }

    if(x_a * y_b - y_a * x_b > 0){
        return -1;
    }else{
        return 1;
    }
}
int naiseki(int a, int b){
    int x_a = x[ind_2[a]] - x_i;
    int y_a = y[ind_2[a]] - y_i;
    int x_b = x[ind_2[b]] - x_i;
    int y_b = y[ind_2[b]] - y_i;
    return x_a*x_b + y_a*y_b;
}
int gaiseki(int a, int b){
    int x_a = x[ind_2[a]] - x_i;
    int y_a = y[ind_2[a]] - y_i;
    int x_b = x[ind_2[b]] - x_i;
    int y_b = y[ind_2[b]] - y_i;
    return x_a * y_b - y_a * x_b;
}
int isUnder90(int a, int b){
    if(naiseki(a, b) > 0 && gaiseki(a, b) > 0){
        return 1;
    }else{
        return 0;
    }
}

int is270orUp(int a, int b){
    if(naiseki(a, b) >= 0 && gaiseki(a, b) < 0){
        return 1;
    }else{
        return 0;
    }
}
int main(void){
    int i, j, k;

    scanf("%lld", &n);
    for(i = 0; i < n; i++){
        scanf("%d%d", &x[i], &y[i]);
    }
    
    int cnt;
    int left, right, mid;
    long long int don = 0, tyo = 0, ei = 0;
    for(i = 0; i < n; i++){//中心となる点
        cnt = 0;
        for(j = 0; j < n; j++){
            if(j == i){
                continue;
            }
            ind[cnt++] = j;
        }
        x_i = x[i];
        y_i = y[i];
        qsort(ind, n - 1, sizeof(int), compare_angle);//偏角ソート，ベクトル(1, 0)からCCWに
        for(j = 0; j < n - 1; j++){
            ind_2[j] = ind[j];
        }
        for(j = 0; j < n - 1; j++){
            ind_2[j + n - 1] = ind[j];
        }
        for(j = 0; j < n - 1; j++){
            //90度未満のものをleft, 90度以上のものをrightとする
            int left = j;
            int right = j + n - 1;
            while(right - left > 1){
                int mid = (right + left)/2;
                if(isUnder90(j, mid)){
                    left = mid;
                }else{
                    right = mid;
                }
            }
            while(naiseki(j, right) == 0 && gaiseki(j, right) > 0){
                tyo++;
                right++;
            }

            int left2 = j;
            int right2 = j + n - 1;
            while(right2 - left2 > 1){
                int mid = (right2 + left2)/2;
                if(is270orUp(j, mid)){
                    right2 = mid;
                }else{
                    left2 = mid;
                }
            }
            while(naiseki(j, right2) == 0 && gaiseki(j, right2) < 0){
                tyo++;
                right2++;
            }
            don += (left2 - right) + 1;
        }
    }
    don /= 2;
    tyo /= 2;
    ei = n * (n - 1) * (n - 2) / 6 - don - tyo;
    printf("%lld %lld %lld\n", ei, tyo, don);
    return 0;
}

148

問題のポイント

上と同じ，内積，外積を計算することで解けます．

解答

# include <stdio.h>
# include <math.h>
# include <stdlib.h>
long long int x[100], y[100];
int ind[100], ind2[200];

long long int naiseki(int a, int b){
    long long int x_a = x[ind2[a]];
    long long int y_a = y[ind2[a]];
    long long int x_b = x[ind2[b]];
    long long int y_b = y[ind2[b]];
    return x_a*x_b + y_a*y_b;
}
long long int gaiseki(int a, int b){
    long long int x_a = x[ind2[a]];
    long long int y_a = y[ind2[a]];
    long long int x_b = x[ind2[b]];
    long long int y_b = y[ind2[b]];
    return x_a * y_b - y_a * x_b;
}
int compare_angle(const void* a_, const void* b_){
    //(1, 0)を基準に偏角ソートを厳密に行う関数(qsortで呼び出されることを想定)
    //同じ角度の場合や(0，0)の入力は想定していない(が，ソートする上では-1でも1でも問題ないはず)
    int a = *(int *)a_;
    int b = *(int *)b_;
    long long int x_a = x[a];
    long long int y_a = y[a];
    long long int x_b = x[b];
    long long int y_b = y[b];
    if(y_a == 0 && x_a >= 0){
        return -1;
    }
    if(y_b == 0 && x_b >= 0){
        return 1;
    }

    if(y_a > 0 && y_b < 0){
        return -1;
    }
    if(y_a < 0 && y_b > 0){
        return 1;
    }

    if(x_a * y_b - y_a * x_b > 0){
        return -1;
    }else{
        return 1;
    }
}
int isUnder180(int a, int b){
    //外積を計算
    return gaiseki(a, b) >= 0;
}
double dist(int a, int b){
    return pow(pow(a, 2) + pow(b, 2), 0.5);
}
int main(void){
    int n;
    scanf("%d", &n);
    double d_max = 0;
    int i, j, k;
    long long int x_tmp, y_tmp;
    for(i = 0; i < n; i++){
        scanf("%lld%lld", &x[i], &y[i]);
    }
    for(i = 0; i < n; i++){
        ind[i] = i;
    }
    qsort(ind, n, sizeof(int), compare_angle);
    for(j = 0; j < n; j++){
        ind2[j] = ind[j];
    }
    for(j = 0; j < n; j++){
        ind2[j+n] = ind[j];
    }

    for(i = 0; i < n; i++){
        int right = i + n;
        int left = i;
        while(right - left > 1){
            int mid = (right + left)/2;
            if(isUnder180(i, mid)){
                left = mid;
            }else{
                right = mid;
            }
        }
        x_tmp = 0;
        y_tmp = 0;
        for(j = i; j <= left; j++){
            x_tmp += x[ind2[j]];
            y_tmp += y[ind2[j]];
            d_max = d_max > dist(x_tmp, y_tmp) ? d_max : dist(x_tmp, y_tmp);
        }
        
    }
    printf("%.20lf\n", d_max);
}

149

問題のポイント

拡張ダイグストラ法を用いて解きます．
ダイグストラ法の実装にて，本来であれば優先度キューを使って解くべきところを実装が面倒だったので普通のキューを使ってといています．
ですので，ちょっと計算時間がぎりぎりです．

解答

# include <stdio.h>
# include <stdlib.h>
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
int min(int a, int b){return a > b ? b : a;}
int compare_int(const void *a, const void *b){
    return *(int *)a - *(int *)b;
}
int *tree[10000], *tree_d[10000], cnt[10000], cnts[10000], queue[4][10000000], dist[10000][201][2], edge[20000][3];
int main(void){
    int n, m, x;
    scanf("%d%d%d", &n, &m, &x);
    int i, j, k, t[10000];
    for(i = 0; i < n; i++){
        scanf("%d", &t[i]);
    }
    for(i = 0; i < n; i++){
        cnt[i] = 0;
        cnts[i] = 0;
    }
    int a, b, d;
    for(j = 0; j < m; j++){
        scanf("%d%d%d", &a, &b, &d);
        a--;
        b--;
        cnt[a]++;
        cnt[b]++;
        edge[j][1] = a;
        edge[j][2] = b;
        edge[j][0] = d;
    }
    qsort(edge, m, sizeof(int)*3, compare_int);
    for(i = 0; i < n; i++){
        tree[i] = malloc(sizeof(int)*(cnt[i] + 1));
        tree_d[i] = malloc(sizeof(int)*(cnt[i] + 1));
    }
    for(i = 0; i < m; i++){
        a = edge[i][1];
        b = edge[i][2];
        d = edge[i][0];
        tree[a][cnts[a]] = b;
        tree[b][cnts[b]] = a;
        tree_d[a][cnts[a]] = d;
        tree_d[b][cnts[b]] = d;
        cnts[a]++;
        cnts[b]++;
    }
    
    int left = 0;
    int right = 1;
    queue[0][0] = 0;//頂点
    queue[1][0] = 0;//最後に訪れた快適でない部屋が暑かった(2)か寒かった(0)か
    queue[2][0] = 0;//移動距離
    queue[3][0] = 0;//最後に訪れた快適でない部屋からの移動距離
    int inf = 2000000001;
    for(i = 0; i < n; i++){
        for(j = 0; j <= x; j++){
            dist[i][j][0] = inf;
            dist[i][j][1] = inf;
        }
    }
    dist[0][0][0] = 0;
    while(left != right){
        int q = queue[0][left];//探索の原点となる頂点
        int last_t = queue[1][left];//最後に訪れた快適ではない部屋が暑かったか寒かったか
        int last_d = queue[2][left];//移動距離
        int kaiteki_d = queue[3][left];//最後に訪れた快適ではない部屋からの移動距離
        left++;
        left %= 10000000;
        for(i = 0; i < cnt[q]; i++){
            int q_new = tree[q][i];
            int d_tmp = last_d + tree_d[q][i];//移動後の移動距離
            int kaiteki_d_tmp = kaiteki_d + tree_d[q][i];//移動先の頂点に到着した時点での，快適ではない部屋からの移動距離

            //慣れていなければスキップ
            if(((last_t == 0 && t[q_new] == 2) || (last_t == 2 && t[q_new] == 0)) && (kaiteki_d_tmp < x)){
                continue;
            }
            if(kaiteki_d_tmp > x){
                kaiteki_d_tmp = x;
            }
            if(t[q_new] == 0 || t[q_new] == 2){
                kaiteki_d_tmp = 0;
            }

            int t_tmp;//移動後の，最後に訪れた快適ではない部屋が暑いか寒いか
            if(t[q_new] == 0 || t[q_new] == 2){
                t_tmp = t[q_new];
            }else{
                t_tmp = last_t;
            }
            int t_tmp_01;
            if(t_tmp == 0){
                t_tmp_01 = 0;
            }else{
                t_tmp_01 = 1;
            }
            //距離を更新できなければスキップ
            int flag = 0;
            for(j = x; j >= kaiteki_d_tmp; j--){
                if(d_tmp >= dist[q_new][j][t_tmp_01]){
                    flag = 1;
                    break;
                }
            }
            if(flag == 1){
                continue;
            }
            
            dist[q_new][kaiteki_d_tmp][t_tmp_01] = d_tmp;
            queue[0][right] = q_new;
            queue[1][right] = t_tmp;
            queue[2][right] = d_tmp;
            queue[3][right] = kaiteki_d_tmp;
            right++;
            right %= 10000000;
        }

    }
    int ans = inf;
    for(i = 0; i <= x; i++){
        ans = min(ans, dist[n-1][i][0]);
        ans = min(ans, dist[n-1][i][1]);
    }
    printf("%d\n", ans);
}

150

問題のポイント

拡張ダイグストラで解くという点は変わりませんが，細かいところに気を付ける必要があります．
桁落ちはもちろんのこと，x=0の場合もあることや，同じ駅を結んでいる異なる路線があったり，行き→帰りの町が同じだったり(ウエスタンリバー鉄道かよ！)するので，気をつけなければいけません(桁落ち以外は入力例で確認できますが)．

解答

# include <stdio.h>
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")

long long int price[1001][1000];    //第一成分：本数，第二成分：駅
int ticket[1000][1000];
int qmod;
long long int queue[3][10000000]; //第一成分：金額，第二成分：本数，第三成分：現在地
int main(void){
    int n, m, k;
    int i, j;
    long long int inf = 1000000000000;
    long long int x[1000], y[1000];
    int a, b, c;
    qmod = 10000000;
    scanf("%d%d%d", &n, &m, &k);
    for(i = 0; i < n; i++){
        for(j = 0; j < n; j++){
            ticket[i][j] = -1;
        }
    }
    for(i = 0; i < m; i++){
        scanf("%d%d%d", &a, &b, &c);
        a--;
        b--;
        if(a == b){
            continue;
        }
        if(ticket[a][b] == -1){
            ticket[a][b] = c;
            ticket[b][a] = c;
        }else{
            if(ticket[a][b] > c){
                ticket[a][b] = c;
                ticket[b][a] = c;
            }
        }
    }

    for(i = 0; i < n; i++){
        scanf("%lld%lld", &x[i], &y[i]);
    }
    int right = 0;
    int left = 0;
    for(i = 0; i <= k; i++){
        for(j = 0; j < n; j++){
            price[i][j] = inf;
        }
    }
    long long int new_p = 0;
    long long int new_h = 0;
    int flag = 0;
    while(1){
        if(new_h >= k){
            new_h = k;
            flag = 1;
        }
        price[new_h][0] = new_p;
        queue[0][right] = new_p;
        queue[1][right] = new_h;
        queue[2][right] = 0;
        right++;
        if(flag == 1 || x[0] == 0){
            break;
        }
        new_p += y[0];
        new_h += x[0];
    }

    while(right != left){
        long long int p = queue[0][left];//price
        long long int h = queue[1][left];//honsuu
        int v = queue[2][left];//vertex
        left++;
        left %= qmod;
        for(i = 0; i < n; i++){
            if(ticket[v][i] == -1){
                continue;
            }
            //vからiに移動することを考える

            new_p = p + ticket[v][i];
            //printf("%lld, v = %d, i = %d\n", ticket[v][i], v, i);
            new_h = h;
            flag = 0;
            while(1){
                if(new_h >= k){
                    new_h = k;
                    flag = 1;
                }
                if(price[new_h][i] > new_p){
                    queue[0][right] = new_p;
                    queue[1][right] = new_h;
                    queue[2][right] = i;
                    right++;
                    right %= qmod;
                    price[new_h][i] = new_p;
                }
                if(flag == 1 || x[i] == 0){
                    break;
                }
                new_p += y[i];
                new_h += x[i];
            }
        }
    }
    long long int ans = inf;
    if(x[n-1] == 0){
        if(price[k][n-1] == inf){
            printf("-1\n");
        }else{
            printf("%lld\n", price[k][n-1]);
        }
        return 0;
    }
    for(i = 0; i <= k; i++){
        if(price[i][n-1] == inf){
            continue;
        }
        new_p = price[i][n-1];
        new_h = i;
        while(new_h < k){
            new_h += x[n-1];
            new_p += y[n-1];
        }
        if(ans > new_p){
            ans = new_p;
        }
    }


    if(ans == inf){
        printf("-1\n");
    }else{
        printf("%lld\n", ans);
    }
    return 0;
}