B - Curiosity Has No Limits

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

    // input
    ll N; 
    cin>>N;

    VI A(N-1);
    rep(i, N-1) cin >> A[i];

    VI B(N-1);
    rep(i, N-1) cin >> B[i];

    // N==2は全探索
    if(N==2){
      rep(a,4){
        rep(b,4){
          bool f = (a|b)==A[0]; // ビット演算の優先度は低いので括弧を使うこと
          bool g = (a&b)==B[0];
          if(f&&g){
            // found
            p("YES");
            p2(a,b);return 0;
          }
        }
      }
    }

    // N>2とする
    VI C(N);
    rep(a,4){
      rep(b,4){
        C[0]=a;
        C[1]=b;
        if(((C[0]|C[1])==A[0]) && ((C[0]&C[1])==B[0])){
          // ok
        }else{
          continue;
        }
        FOR(i,2,N){
          // iについて決めよう
          bool found=false;
          rep(c,4){
            // cならどうか
            if(((C[i-1]|c)==A[i-1]) && ((C[i-1]&c)==B[i-1])){
              found=true;
              C[i]=c;
            }
          }
          if(!found)break;
          if(i==N-1){
            // 決まった
            p("YES");
            print_vector(C); return 0;
          }
        }
      }
    }
    p("NO");
    
    return 0;
}

C. Smallest Word

  • Quiz
  • AC
  • 解説
    • aaaaabbbbbの形にできる
    • aの塊ごとに見て、その後端で1度flipすると、そのaの塊が先頭に来る
    • 次のaの塊の直前にあるbで1度flipすると、先頭に集まっていたaの塊が後ろに来て、合体する(下図参照)
    • flipタイミングはコードの通り、"ab", "ba"を見ればいい。文字列の後端には番兵のように'b'を足した

f:id:peroon:20201202060050p:plain

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

    // input
    string s;cin>>s;
    ll N = s.size();
    
    s.push_back('b');
    set<ll> se;
    rep(i,N){
      // tail a
      if(s[i]=='a' && s[i+1]=='b') se.insert(i);

      if(s[i]=='b' && s[i+1]=='a') se.insert(i);
    }

    VI Ans(N);
    rep(i,N){
      if(se.count(i))Ans[i]=1;
    }
    print_vector(Ans);

    return 0;
}

A. Music

  • Quiz
  • AC
  • 問題理解
    • 音楽をダウンロード(DL)しようとしている。S秒分の曲をDLしたら、Playを開始する
    • DLが完了するまで、何度も曲を聞く
    • 聞いている間、常にDLは進んでいる
    • 何回聞いたらDL完了するか?
  • 解説
    • S秒DLした時にPlayして、次は何秒後に曲が止まるか(DLできた右端まで行って止まる)をxとおく
    • 下記画像の式が立つので解けます

f:id:peroon:20201202000130p:plain

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

    // input
    ll T,S,q;
    cin>>T>>S>>q;

    ll cnt=0;
    while(S<T){
      S *= q;
      cnt++;
    }
    p(cnt);
    
    return 0;
}

1080C - Masha and two friends ~白黒タイルを塗る。領域の重なり~

f:id:peroon:20201201043144p:plain

// (x,y)
ll w(ll a, ll b){
  if(a<=0 or b<=0) return 0;
  // 以降、a>0 && b>0
  return ceil_div(a,2) * ceil_div(b,2) + (a/2) * (b/2);
}

struct area{
  ll x0,y0; // 左下
  ll x1,y1; // 右上

  // 左下と右上の位置関係がおかしい場合はfalse
  bool is_valid(){
    if(x1<x0 or y1<y0)return false;
    return true;
  }

  string ToString(){
    stringstream ss;
    ss << x0 << ' ' << y0 << ' ' << x1 << ' ' << y1;
    return ss.str();
  }
};

// 領域内 white (a,b) to (c,d)
ll WH(area r){
  ll a = r.x0;
  ll b = r.y0;
  ll c = r.x1;
  ll d = r.y1;
  return w(c,d) - w(a-1,d) - w(c,b-1) + w(a-1,b-1);
}

// 領域内 black
ll BL(area r){
  ll w = r.x1 - r.x0 + 1;
  ll h = r.y1 - r.y0 + 1;
  return w*h - WH(r);
}

// 重なる領域
area cross_area(area a, area b){
  // 左下はmaxを取るのです
  ll x = max(a.x0, b.x0);
  ll y = max(a.y0, b.y0);
  // 右上はminを取るのです
  ll x2 = min(a.x1, b.x1);
  ll y2 = min(a.y1, b.y1);
  return {x,y,x2,y2};
}

void test(){
  area a0 = {2,2,4,4};
  area a1 = {4,0,7,6};
  debug(cross_area(a0,a1).ToString());
}

area get_area(){
  ll x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  return {x1,y1,x2,y2};
}

// for codeforces
void solve(){
  ll H,W;cin>>H>>W;

  area area0 = get_area();
  area area1 = get_area();
  area area2 = cross_area(area0, area1);

  ll white = w(W,H);
  ll black = W*H-white;

  // whiteに塗ります
  // その領域のblackの数だけ変化するが、重なる領域に注意する
  {
    ll b = BL(area0);
    if(area2.is_valid()){
      b -= BL(area2); // 重なる領域分の黒を数えない
    }
    white += b;
    black -= b;
  }

  // blackに塗ります
  {
    ll w = WH(area1);
    white -= w;
    black += w;
  }

  p2(white,black);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    // input
    ll N;cin>>N;    
    while(N--)solve();
    return 0;
}

B. Valuable Paper ~Hopcroft–Karp algorithm~ 条件付き2部マッチングでO(E sqrt(V))

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

    // input
    ll N,M;
    cin>>N>>M;

    VI A(M);
    VI B(M);
    VI C(M);
    rep(i,M){
      cin>>A[i]>>B[i]>>C[i];
      A[i]--;
      B[i]--;
    }
    ll max_cost = MAX(C);

    // 辺コストをlimitまで制限した時のマッチング数を返す
    auto f = [&](ll limit){
      Bipartite_Matching graph(2*N, 2*N);
      rep(i,M){
        if(C[i]>limit)continue;
        graph.add_edge(A[i],B[i]+N);
      }
      return graph.bipartite_matching();
    };

    if(f(max_cost)<N){
      p(-1); return 0;
    }

    ll left = 0; // can't
    ll right = max_cost; // can
    while(left+1!=right){
      ll center = (left+right)/2;
      if(f(center)==N){
        right = center;
      }else{
        left = center;
      }
    }

    p(right);
   
    return 0;
}