Tenka1 Programmer Contest 参加記録

CD解けたのにunratedになり悲しいコンテストでした

C - 4/N

3変数あるが式変形して2変数の値を全探索O(N²)

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N; cin >> N;
  FOR(n,1,3501) {
    FOR(w,1,3501) {
      if(4 * n * w > N * (w + n)) {
        if((N * n * w) % (4 * n * w - N * (w + n)) == 0) {
          cout << (N * n * w) / (4 * n * w - N * (w + n)) << " " << n << " " << w << endl;
          return 0;
        }
      }
    }
  }
}

D - IntegerotS

bitwise orがKのビットが立っているとこだけ1になるようにする。もしくはKのビットが立っているところ1つは1にならないようにするとそのビットより下位のビットを全て1にできるので有利かもしれない。1にならないようにする桁を全て試せばOK。

int main()
{
  ll N, K; cin >> N >> K;
  ll A[N], B[N]; FOR(i,0,N) cin >> A[i] >> B[i];
  ll ans = 0;
  FOR(j,0,32) {
    // jより上は1のとこしかだめ
    if((K>>j)&1) {
      ll mx = 0;
      FOR(l,0,N) {
        bool ok = true;
        FOR(i,j,32) {
          if((!((K>>i)&1)||(i==j)) && (A[l]>>i)&1) ok = false;
        }
        if(ok) mx += B[l];
      }
      ans = max(ans, mx);
    }
  }
  ll mx = 0;
  FOR(l,0,N) {
    bool ok = true;
    FOR(i,0,32) {
      if(!((K>>i)&1) && (A[l]>>i)&1) ok = false;
    }
    if(ok) mx += B[l];
  }
  ans = max(ans, mx);
  cout << ans << endl;
  return 0;
}