Neunomizuの日記

俺だけが俺だけじゃない

｢AtCoder Beginner Contest 147｣に出た

競技プログラミング
tags: 競技プログラミング

感想

  • C問題の実装が面倒だなと思ったのですが頑張って実装したので偉いと思いました
  • D問題でXORが出た瞬間に｢あ,これは数学かな｣と思いました
  • コンテストページ

A問題

  • ただ足し算をして条件分岐するだけです

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a1, a2, a3;
    cin >> a1 >> a2 >> a3;
    int sum = a1 + a2 + a3;
    if (sum >= 22) {
        puts("bust");
    }else {
        puts("win");
    }
    return 0;
}

B問題

  • 文字列の前と後ろを比較します

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a1, a2, a3;
    cin >> a1 >> a2 >> a3;
    int sum = a1 + a2 + a3;
    if (sum >= 22) {
        puts("bust");
    }else {
        puts("win");
    }
    return 0;
}

C問題

  • bit全探索を使うのかなと考えました
  • 誰が｢正直者｣で｢不親切な人｣かを仮定してそれが正しいか全て見ます
    • 仮定する人を表現する配列をhとして｢正直者｣の場合は値を1,｢不親切な人｣の場合は0としました
    • このとき｢正直者｣の数をcntとします
  • 人iの発言が正しいかどうか調べます(このときh[i]=1です)
    • 全て正しい場合は答え(ans)を更新し,1つでも間違っていた場合はflagをfalseにして答えは更新しません
    • h[i]=1のときに0<=j<A[j]としてx[i][j]とy[i][j]を使います
      • 仮定より,h[x[i][j]]は人x[i][j]が｢正直者｣かどうかという情報です
      • y[i][j]は人iがx[i][j]が｢正直者｣と言っているかどうかという情報です
      • 人iが正直者であればh[x[i][j]]とy[i][j]は一致するはずです
      • これが一致しないときは矛盾が生じているのでflagをfalseにします

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)n; ++i)
static const int dx[4] = { 0, 1, 0, -1 };
static const int dy[4] = { 1, 0, -1, 0 };
static const char dir[4] = { 'u', 'r', 'd', 'l' };
static const ll INF = 1 << 21;
static const ll MOD = 1e9 + 7;
static const int MAX_N = 100;
int N;
int A[MAX_N], x[MAX_N][MAX_N], y[MAX_N][MAX_N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    rep(i, N)
    {
        cin >> A[i];
        rep(j, A[i])
        {
            int tmpx, tmpy;
            cin >> tmpx >> tmpy;
            tmpx--;
            x[i][j] = tmpx, y[i][j] = tmpy;
        }
    }
    int ans = 0;
    for (int bit = 0; bit < (1 << N); bit++) {
        vector<int> h(N);
        for (int n = 0; n < N; n++) {
            if (bit & (1 << n)) {
                h[n] = 1;
            }
        }
        int cnt = 0;
        rep(i, N)
        {
            if (h[i])
                cnt++;
        }
        bool flag = true;
        rep(i, N)
        {
            if (h[i]) {
                rep(j, A[i])
                {
                    if (h[x[i][j]] != y[i][j]) {
                        flag = false;
                    }
                }
            }
        }
        if (flag)
            ans = max(ans, cnt);
    }
    cout << ans << endl;

    return 0;
}

D問題

  • XORは数学回のものが多いので復習しようと思いました(丸)

まとめ

  • 多少レートが上がった