AtCoder Beginner Contest 025

Submission #1587724

Source codeソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

vector<vector<ll>> b(2, vector<ll>(3));
vector<vector<ll>> c(3, vector<ll>(2));
map<ll, P> dp;
vector<vector<ll>> decode(ll f) {
    vector<vector<ll>> res(3, vector<ll>(3));
    rep(y, 3) rep(x, 3) {
        res[y][x] = f % 3;
        f /= 3;
    }
    return res;
}
ll encode(const vector<vector<ll>>& m) {
    ll res = 0;
    rrep(y, 3) rrep(x, 3) {
        res = res * 3 + m[y][x];
    }
    return res;
}
P solve(ll f) {
    if (dp.count(f) > 0) return dp[f];
    P res(-linf, -linf);
    vector<vector<ll>> m = decode(f);
    vector<P> unused;
    rep(y, 3) rep(x, 3) if (m[y][x] == 0) unused.pb({x, y});
    if (unused.size() == 0) {
        res = {0, 0};
        rep(y, 2) rep(x, 3) {
            if (m[y][x] != m[y+1][x]) res.first += b[y][x];
            else res.second += b[y][x];
        }
        rep(y, 3) rep(x, 2) {
            if (m[y][x] != m[y][x+1]) res.first += c[y][x];
            else res.second += c[y][x];
        }
    }
    else {
        ll turn = unused.size() % 2 == 1;
        each(p, unused) {
            ll x, y; tie(x, y) = p;
            vector<vector<ll>> nm = m;
            nm[y][x] = turn+1;
            P r = solve(encode(nm));
            chmax(res, P(r.second, r.first));
        }
    }
    return dp[f] = res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> b >> c;
    cout << solve(0).first << endl;
    cout << solve(0).second << endl;
}

Submission

Task問題 C - 双子と○×ゲーム
User nameユーザ名 drafear
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2721 Byte
File nameファイル名
Exec time実行時間 10 ms
Memory usageメモリ使用量 640 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample-01.txt,sample-02.txt
All 100 / 100 sample-01.txt,sample-02.txt,test-01.txt,test-02.txt,test-03.txt,test-04.txt,test-05.txt,test-06.txt,test-07.txt,test-08.txt,test-09.txt,test-10.txt,test-11.txt,test-12.txt,test-13.txt,test-14.txt,test-15.txt,test-16.txt,test-17.txt,test-18.txt,test-19.txt,test-20.txt,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample-01.txt AC 10 ms 640 KB
sample-02.txt AC 10 ms 640 KB
test-01.txt AC 10 ms 640 KB
test-02.txt AC 10 ms 640 KB
test-03.txt AC 10 ms 640 KB
test-04.txt AC 10 ms 640 KB
test-05.txt AC 10 ms 640 KB
test-06.txt AC 10 ms 640 KB
test-07.txt AC 10 ms 640 KB
test-08.txt AC 10 ms 640 KB
test-09.txt AC 10 ms 640 KB
test-10.txt AC 9 ms 640 KB
test-11.txt AC 10 ms 640 KB
test-12.txt AC 9 ms 640 KB
test-13.txt AC 10 ms 640 KB
test-14.txt AC 9 ms 640 KB
test-15.txt AC 10 ms 640 KB
test-16.txt AC 10 ms 640 KB
test-17.txt AC 10 ms 640 KB
test-18.txt AC 10 ms 640 KB
test-19.txt AC 10 ms 640 KB
test-20.txt AC 10 ms 640 KB