ABC147

atcoder.jp

結果

問題	ACまでに要した時間	AC	WA	TLE
A	01:51	0	0	0
B	07:05	0	0	0
C	:	0	0	0
D	:	0	0	0

Rating	順位
567 (+17)	2736

ABは7分ちょいでACできたがC,Dが全く手が出なかった．

解答

A

そのまま

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  int a_1, a_2, a_3;
  cin >> a_1 >> a_2 >> a_3;

  if (a_1 + a_2 + a_3 >= 22) {
    cout << "bust" << endl;
  } else {
    cout << "win" << endl;
  }

  return 0;
}

B

そのまま

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

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

  string S;
  cin >> S;

  int ans = 0;
  int l = S.length();
  REP(i, l / 2) {
    if (S[i] != S[l - 1 - i]) {
      ++ans;
    }
  }

  cout << ans << endl;

  return 0;
}

C

総当りで全ての 人 について列挙する方法が分からなかった． この場合はbit全探索という手法を使うらしい．

qiita.com

とある整数 bit を0からN-1までループを回して，bitを2進数として見たときに REP(i, N) bit & (1<<i)で各フラグの状態をチェックしながら処理を行うと，N bitのフラグについて全パターンを網羅した処理が実行できるというもの．

この問題ではこれを使ってすべての 人 に対して正直者か不親切者かを全列挙して，各bitパターンで親切な人の証言をすべて検証して矛盾がないかどうかを調べる． 計算量は だが，Nは最大で15なので十分間に合う．

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> A(n);
  vector<vector<int>> X(n, vector<int>(n));
  vector<vector<int>> Y(n, vector<int>(n));

  REP(i, n) {
    cin >> A[i];
    REP(j, A[i]) {
      cin >> X[i][j] >> Y[i][j];
      X[i][j]--;
    }
  }

  int ans = 0;
  bool ok = true;
  REP(bits, (1 << n)) {
    ok = true;
    REP(i, n) {
      if (!(bits & (1 << i)))
        continue;
      REP(j, A[i]) {
        if (bits & (1 << X[i][j]))
          ok &= Y[i][j];
        else
          ok &= !Y[i][j];
      }
    }
    if (ok)
      ans = max(ans, (int)__builtin_popcount(bits));
  }
  cout << ans << endl;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  solve();
  return 0;
}

D

解説pdf読んだが分からんので解説放送を２，３回繰り返し観てようやく理解した．

結論としてはbitごとにxor取った和を計算して最後に10進数に戻せばよかった． このbitごとにxor取った和は，各のk桁目における1と0の全組み合わせのみがxorの結果が1となるため， をk桁目ごとに計算して総和を取れば10進数に復元することができる．なるほどな〜〜〜

アライグマ「ABC147のA,D,E問題を作ったのだ！　C問題は、誰が正直者か2^N通りを全探索するのだ！　D問題は、bit毎に別々に考えればいいのだ！」
フェネック「検索サイトで"sum of xor"まで入れると"sum of xor of all pairs"がサジェストされてほとんど答えに近いコードが出てくるねー」

— 競技プログラミングをするフレンズ (@kyopro_friends) 2019年12月8日

#include <bits/stdc++.h>

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

const ll MOD = 1e9 + 7;

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

  int N;
  cin >> N;
  vector<ll> A(N);
  REP(i, N) { cin >> A[i]; }

  ll ans = 0, now = 0;
  ll x = 0;

  REP(i, 60) {
    x = 0;
    REP(j, N) {
      if (A[j] >> i & 1) {
        ++x;
      }
    }
    now = x * (N - x) % MOD;
    REP(j, i) { now = now * 2 % MOD; }
    ans = ans + now;
    ans = ans % MOD;
  }

  cout << ans << endl;
  return 0;
}

ダメだった点

bit全探索ができなくても再起で深さ優先探索を実装すれば解けないこともなかった．アプローチは分かっていたので，早々にあきらめてしまったのはダメだったと思う．

良かった点

特になし

おわりに

bit全探索を使う問題は初めて解いたが，頻出パターンなので覚えておきたい．