D. Ticket Game

1700
  • Quiz
  • AC
  • 解説
    • editorialと違う解法
    • 左の数字の和＝＝右の数字の和の時は自明とし、以降は数字の和に差があるものとする
    • 左の？が多いとする（違うならswapする）
    • 左の数字の和＞右の数字の和なら、先行は左に９を置き続ければ勝てる
    • 左の数字の和＜右の数字の和なら、先行は左に９を置いて一致させようとするが、後攻は左に０を置くことで邪魔をすることができる
    • ？？？？？　VS　？　のように？が左右に分かれている時は、後攻はマネをすることで
    • ？？？？ VS (なし) の状態に持っていくことができる
// 例
???? .
0 18

9090となって左右一致
先手が4などを置いても、後手は5を置きます（和が9）
4545となって左右一致
＝＞後手の勝ち

---

// 別の例
???? .
0 17

先手は9を置くことで必ず18を達成できる（左右一致を阻止できる）
＝＞先手の勝ち

---

// 別の例
???? .
0 19

先手は0を置く。後手は揃えようとすべてに9を出したとしても19は達成できない（左右一致できない）
＝＞先手の勝ち
void win(){
  p("Monocarp"); exit(0);
}

void lose(){
  p("Bicarp"); exit(0);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    string s;cin>>s;

    ll left_sum = 0;
    ll right_sum = 0;
    ll left_q = 0;
    ll right_q = 0;

    rep(i,N/2){
      if(s[i]=='?'){
        left_q++;
      }else{
        left_sum += s[i]-'0';
      }
    }
    FOR(i,N/2,N){
      if(s[i]=='?'){
        right_q++;
      }else{
        right_sum += s[i]-'0';
      }
    }

    // easy case
    if(left_sum==right_sum){
      if(left_q == right_q){
        // mimic
        lose();
      }else{
        win();
      }
    }

    // 左の?が多いとする
    if(left_q < right_q){
      swap(left_q, right_q);
      swap(left_sum, right_sum);
    }

    // ????? vs ?
    // => ???? vs .
    ll q = (left_q - right_q)/2;
    ll w = right_sum - left_sum;
    if(q*9 == w){
      lose();
    }else{
      win();
    }

    return 0;
}

editorial version

void win(){
  p("Monocarp"); exit(0);
}

void lose(){
  p("Bicarp"); exit(0);
}

// left sum - right sum
ll f(string s){
  ll N = s.size();
  ll l = 0;
  ll r = 0;
  rep(i,N){
    ll v = s[i]-'0';
    if(i<N/2){
      l += v;
    }else{
      r += v;
    }
  }
  return l-r;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;
    string s;cin>>s;

    ll q_cnt = 0;
    for(char c : s){
      if(c=='?') q_cnt++;
    }

    // ???? => 0099
    ll L;
    {
      ll cnt=0;
      string t = s;
      rep(i,N){
        if(t[i]=='?'){
          if(cnt<q_cnt/2){
            t[i]='0';
          }else{
            t[i]='9';
          }
          cnt++;
        }
      }
      L = f(t);
    }

    // ???? => 9900
    ll R;
    {
      ll cnt=0;
      string t = s;
      rep(i,N){
        if(t[i]=='?'){
          if(cnt<q_cnt/2){
            t[i]='9';
          }else{
            t[i]='0';
          }
          cnt++;
        }
      }
      R = f(t);
    }

    if(L+R==0){
      lose();
    }else{
      win();
    }

    return 0;
}