SRM532 Div1 300

問題

3文字の組がいくつか与えられる。各文字は数字か「.」。
この3文字の並びは変えることができないが、組の順番は自由に並べることができる。

全部の組を適当に並べたときに、1つ以上連続する数字の和で最大のものを返す。
例えば、「4.5」「5.3」ならば「4.55.3」で連続する数字の和で最大のものは真ん中の「55」で5+5=10。

考え方

やるだけ。

3文字の組のパターンは高々8パターン。「?」が何らかの数字だとすると、
「...」→無視
「..?」→左にしかこない
「.?.」→単体でしか現れない
「.??」→左にしかこない
「?..」→右にしかこない
「?.?」→左または右に来る場合がある
「??.」→右にしかこない
「???」→真ん中にしかこない

あらかじめ、左しかこないもの、右にしかこないもの、単体でしか現れないもの、の最大値をそれぞれ求めておく。
真ん中にしかこないものはいつでもつなげることができるので、和を計算しておく。
両方に来る場合がある「?.?」だけは別配列に入れておく。

すると、「左にくるものの最大値」＋「真ん中にしか来ないものの和」＋「右にくるものの最大値」の最大値または単体でしか現れないもので大きいほうが答えになる。

「左にくるものの最大値」は、左にしかこないものの最大値または両方に来る場合のあるもの。
右側も同様。

両方に来る可能性のあるものをすべて条件分岐で書こうとすると、結構パターンが多くなってしまう。
しかし、ループですべて確認すれば、高々50^2なので、全然問題ない。

//イメージ
//leftmax : 左にしかこないものの最大値
//ret : 真ん中にしかこないものの和
//rightmax : 右にしかこないものの最大値
//dbl : 両方来る場合があるもののみの配列
//middlemax : 「.?.」の?の最大値

    int res = leftmax + ret + rightmax;

    //両方に来る場合があるものについてチェック
    rep(i,dbl.size()) res = max(res, leftmax + ret + (dbl[i][0]-'0')); //右側だけ
    rep(i,dbl.size()) res = max(res, (dbl[i][2]-'0') + ret + rightmax); //左側だけ

    //両側
    rep(i,dbl.size()){
      rep(j,dbl.size()){
        if(i==j) continue;
        res = max(res, (dbl[i][2]-'0') + ret + (dbl[j][0]-'0'));
      }
    }
    
    return max(res, middlemax);

反省

あんまり複雑な条件分岐にならないかなと思って書き出したら複雑＆抜け漏れの嵐。
複雑な条件分岐を書きそうになったら、ループなどで全パターンを確認できるかどうかを考える。