atcoderの問題で、原因不明のエラー

Question

前提

atcoderの問題で、バグが発生しましたが、原因がつかめていません。

実現したいこと

バグの原因を突き止める。

発生している問題・エラーメッセージ

該当のソースコード

ソースコード
#include<stdio.h>

int max_kohuku(int a,int b,int c);//3つの中から最大を返す
int second_kohuku(int a,int b,int c);//3つの中から2番目に大きい数を返す

int main(){
    int N;
    int kohuku[100010][3];//i日目の行動jをした時の幸福度はkohuku[i][j]
    int sum_kohuku[100010][2];//i日目に行動jをしたときにそれを含めた最大の幸福度はsum_kohuku[i][j]
    int sss;
    sss = scanf("%d",&N);
    for(int i = 0;i < N;i++){
        sss = scanf("%d %d %d",&kohuku[i][0],&kohuku[i][1],&kohuku[i][2]);
        sum_kohuku[i][0] = -1;//初期化
        sum_kohuku[i][1] = -1;//初期化
    }

    sum_kohuku[0][1] = max_kohuku(kohuku[0][0],kohuku[0][1],kohuku[0][2]);
    sum_kohuku[0][0] = second_kohuku(kohuku[1][0],kohuku[1][1],kohuku[1][2]);
    for(int i = 1;i < N;i++){
        sum_kohuku[i][1] = max_kohuku(kohuku[i][0],kohuku[i][1],kohuku[i][2]) + sum_kohuku[i-1][0];
        sum_kohuku[i][0] = second_kohuku(kohuku[i][0],kohuku[i][1],kohuku[i][2]) + sum_kohuku[i-1][1];
    }
    int pri;
    if(sum_kohuku[N-1][0] > sum_kohuku[N-1][1]){
        pri = sum_kohuku[N-1][0];
    }else{
        pri = sum_kohuku[N-1][1];
    }
    printf("%d",pri);
    return 0;
}

int max_kohuku(int a,int b,int c){
    int ret = a;
    if(ret < b){
        ret = b;
    }
    if(ret < c){
        ret = c;
    }
    return ret;
}

int second_kohuku(int a,int b,int c){
    int ret = a;
    if(ret == max_kohuku(a,b,c)){
        ret = b;
    }
    if((ret < b) && b != max_kohuku(a,b,c)){
        ret = b;
    }
    if((ret < c) && c != max_kohuku(a,b,c)){
        ret = c;
    }
    return ret;
}

試したこと

まず、前に質問した時にscanfの返り値にsssをつけずに、(void)scanfとすればいいと教えてくださった方がいたのですが、atcoderのシステムの関係なのか、それでもバグが出たので返り値をつけさせていただきました。

変数のオーバーフローかと思ってkohuku,sum_kohukuの要素を5倍くらいに増やしたのですが、実行結果は変わりませんでした。

自分の環境で、サンプルを入力すると正しく動作します。

補足情報（FW/ツールのバージョンなど）

問題のURLです
https://atcoder.jp/contests/dp/tasks/dp_c
もし、ほかに必要な情報があれば教えてください。
回答よろしくお願いします。

Comments

[int32_t]

どういう入力で問題が出るかはわからないのですか?

[jimbe]

scanf の返り値を受け取っているかどうかだけで異常動作というのは考えられません。
(atcoder の他の問題でそのようなことは聞いたことが無いと思います。)

[shamsham]

int32_tさん、コメントありがとうございます。
私の知る限りでは、どの入力でエラーするのかわかりません。

Answer 1

3
1 2 3
1 3 2
1 2 3

なる入力を与えると、C, B, C で 9になるべきですが、質問文のコードでは8になります。
おそらくロジックを間違えているかと思います

sum_kohuku[i][0]は
(0日目で一番目に幸福度の高い行動) + (1日目で二番目に幸福度の高い行動) + (2日目で一番目に幸福度の高い行動) + ...
sum_kohuku[i][1]は
(0日目で二番目に幸福度の高い行動) + (1日目で一番目に幸福度の高い行動) + (2日目で二番目に幸福度の高い行動) + ...

となっていますが、問題は「同じ行動を連続してはならない」ということであって、「一番目に高い行動を連続してはならない」ではありません

「i日目に行動jをしたときの幸福度の総和が取りうる最大値」をdp[i][j]としたら
「i+1日目に行動jをしたときの幸福度の総和が取りうる最大値」dp[i+1][j]は

dp[i+1][j] = (dp[i][k]、k != jの大きい方) + (i+1 日目の行動 j の幸福度)

Comments

[shamsham]

なるほど！
確かに言われてみればそうですね。
わかりやすい説明ありがとうございました。