Submission #2140957
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS #include "bits/stdc++.h" #include <random> //#include <opencv2/core.hpp> // coreモジュールのヘッダーをインクルード //#include <opencv2/highgui.hpp> // highguiモジュールのヘッダーをインクルード //#include <opencv2/imgproc.hpp> //#define DEBUG //#define VISUALIZE #ifdef VISUALIZE #include "visualizer.h" #endif using namespace std; //呪文 #define DUMPOUT cerr #define dump(...) DUMPOUT<<" ";DUMPOUT<<#__VA_ARGS__<<" :["<<__LINE__<<":"<<__FUNCTION__<<"]"<<endl;DUMPOUT<<" ";dump_func(__VA_ARGS__) typedef unsigned uint; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<double, double> pdd; typedef pair<string, string> pss; template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const pair<_KTy, _Ty>& m) { ostr << "{" << m.first << ", " << m.second << "}"; return ostr; } template <typename _KTy, typename _Ty> ostream& operator << (ostream& ostr, const map<_KTy, _Ty>& m) { if (m.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *m.begin(); for (auto itr = ++m.begin(); itr != m.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const vector<_Ty>& v) { if (v.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const set<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << *(s.begin()); for (auto itr = ++s.begin(); itr != s.end(); itr++) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const stack<_Ty>& s) { if (s.empty()) { ostr << "{ }"; return ostr; } stack<_Ty> t(s); ostr << "{" << t.top(); t.pop(); while (!t.empty()) { ostr << ", " << t.top(); t.pop(); } ostr << "}"; return ostr; } template <typename _Ty> ostream& operator << (ostream& ostr, const list<_Ty>& l) { if (l.empty()) { ostr << "{ }"; return ostr; } ostr << "{" << l.front(); for (auto itr = ++l.begin(); itr != l.end(); ++itr) { ostr << ", " << *itr; } ostr << "}"; return ostr; } template <typename _KTy, typename _Ty> istream& operator >> (istream& istr, pair<_KTy, _Ty>& m) { istr >> m.first >> m.second; return istr; } template <typename _Ty> istream& operator >> (istream& istr, vector<_Ty>& v) { for (size_t i = 0; i < v.size(); i++) istr >> v[i]; return istr; } namespace aux { // print tuple template<typename Ty, unsigned N, unsigned L> struct tp { static void print(ostream& os, const Ty& v) { os << get<N>(v) << ", "; tp<Ty, N + 1, L>::print(os, v); } }; template<typename Ty, unsigned N> struct tp<Ty, N, N> { static void print(ostream& os, const Ty& value) { os << get<N>(value); } }; } template<typename... Tys> ostream& operator<<(ostream& os, const tuple<Tys...>& t) { os << "{"; aux::tp<tuple<Tys...>, 0, sizeof...(Tys)-1>::print(os, t); os << "}"; return os; } template<typename A, size_t N, typename T> inline void Fill(A(&array)[N], const T &val) { std::fill((T*)array, (T*)(array + N), val); } void dump_func() { DUMPOUT << endl; } template <class Head, class... Tail> void dump_func(Head&& head, Tail&&... tail) { DUMPOUT << head; if (sizeof...(Tail) == 0) { DUMPOUT << " "; } else { DUMPOUT << ", "; } dump_func(std::move(tail)...); } #define PI 3.14159265358979323846 #define EPS 1e-11 #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define all(x) (x).begin(), (x).end() #define SZ(x) ((int)(x).size()) #define fake false unsigned w; unsigned xor128() { static unsigned x = 123456789, y = 362436069, z = 521288629/*, w = 88675123*/; unsigned t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } #ifdef VISUALIZE visualizer vis; #endif class chokudai001 { int di[4] = { 0, -1, 0, 1 }; int dj[4] = { 1, 0, -1, 0 }; public: typedef vector<int> Path; typedef vector<Path> Paths; typedef pair<Paths, vector<bool>> State; typedef priority_queue<pair<int, State>, vector<pair<int, State>>, greater<pair<int, State>>> PQ; vector<int> A; int N; int total; int step; chokudai001() {} void init(int N); void init_random(int N, int M); int getVal(int i, int j); int getVal(pii p); void decrement(int p); Paths beam_search(int width); int calc_score(const Path& path); int calc_score(const State& paths); void output_moves(const Path& path); void output_moves(); void visualize(int waitTime); }; chokudai001::Paths chokudai001::beam_search(int width = 10) { int highest = -1; REP(i, N) REP(j, N) highest = max(highest, getVal(i, j)); vector<State> initial_state; REP(i, N) REP(j, N) if (getVal(i, j) == highest) { vector<bool> used(N * N, false); used[i * N + j] = true; initial_state.push_back(pair<Paths, vector<bool>>(Paths({ { i * N + j } }), used)); } PQ pq; for (int i = 0; i < initial_state.size(); i++) { pq.push(pair<int, State>(calc_score(initial_state[i]), initial_state[i])); } for (int k = 1; k < N * N; k++) { PQ pq_new; while (!pq.empty()) { State state = pq.top().second; pq.pop(); //dump(state); Paths& paths = state.first; vector<bool>& used = state.second; Path& path = paths.back(); int p = path.back(); int i = p / N, j = p % N; bool update = false; // 4-dir for (int d = 0; d < 4; d++) { int ni = i + di[d], nj = j + dj[d]; if (ni < 0 || N <= ni || nj < 0 || N <= nj) continue; if (used[ni * N + j]) continue; update = true; path.push_back(ni * N + nj); used[ni * N + nj] = true; pq_new.push(pair<int, State>(calc_score(state), state)); path.pop_back(); used[ni * N + nj] = false; } // new seed if (!update) { int highest_tmp = -1; REP(p, N * N) { if (used[p]) continue; highest_tmp = max(highest_tmp, A[p]); } vector<int> pCandidate; REP(p, N * N) { if (used[p]) continue; if (A[p] == highest_tmp) pCandidate.push_back(p); } int pSelected = pCandidate[xor128() % pCandidate.size()]; paths.push_back(Path({ pSelected })); used[pSelected] = true; pq_new.push(pair<int, State>(calc_score(state), state)); paths.pop_back(); used[pSelected] = false; } } while (pq_new.size() > width) pq_new.pop(); pq = pq_new; } return pq.top().second.first; } void chokudai001::output_moves() { Paths paths = beam_search(); for (int i = 0; i < paths.size(); i++) { output_moves(paths[i]); } } void chokudai001::output_moves(const Path& path) { for (int k = path.size() - 1; k >= 1; k--) { while (A[path[k - 1]] <= A[path[k]]) { decrement(path[k]); for (int l = k + 1; l < path.size(); l++) { int x = A[path[l - 1]]; int y = A[path[l]]; if (x != y || y == 0) break; decrement(path[l]); } step++; visualize(10); } } { int k = 0; while (A[path[k]] > 0) { decrement(path[k]); for (int l = k + 1; l < path.size(); l++) { int x = A[path[l - 1]]; int y = A[path[l]]; if (x != y || y == 0) break; decrement(path[l]); } step++; visualize(10); } } } int chokudai001::calc_score(const State& state) { int score = 0; const Paths& paths = state.first; for (int i = 0; i < paths.size(); i++) { score += calc_score(paths[i]); } return score; } int chokudai001::calc_score(const Path& path) { int score = 0; score += A[path[0]]; for (int i = 0; i < path.size() - 1; i++) { int x = A[path[i]]; int y = A[path[i + 1]]; if (x <= y) score += y - x + 1; } return score; } void chokudai001::init(int N) { A.resize(N * N, 0); REP(i, N) REP(j, N) { cin >> A[i * N + j]; total += A[i * N + j]; } this->N = N; this->step = 0; } void chokudai001::init_random(int N, int M) { A.resize(N * N, 0); REP(i, N) REP(j, N) { int a = xor128() % M + 1; A[i * N + j] = a; total += a; } this->N = N; this->step = 0; } int chokudai001::getVal(int i, int j) { return A[i * N + j]; } int chokudai001::getVal(pii p) { return A[p.first * N + p.second]; } void chokudai001::decrement(int p) { A[p]--; total--; #ifndef DEBUG int i = p / N, j = p % N; printf("%d %d\n", i + 1, j + 1); #endif } void chokudai001::visualize(int waitTime) { #ifdef VISUALIZE vis.draw(A, step, total, waitTime); #endif } int main() { #ifdef DEBUG clock_t start, end; start = clock(); #endif cin.tie(0); ios::sync_with_stdio(false); random_device rnd; mt19937 mt(rnd()); w = mt(); //w = 1234567; const int N = 30; const int M = 100; chokudai001 c001; #ifdef DEBUG c001.init_random(N, M); //c001.init(N); #else c001.init(); #endif #ifdef VISUALIZE vis = visualizer(N, c001.A); #endif c001.output_moves(); #ifdef VISUALIZE vis.draw(c001.A, c001.step, c001.total, 0); #endif #ifdef DEBUG end = clock(); printf("%d msec.\n", end - start); #endif return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - 高橋君の山崩しゲーム |
User | komori3 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 9302 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:306:12: error: no matching function for call to ‘chokudai001::init()’ c001.init(); ^ ./Main.cpp:233:6: note: candidate: void chokudai001::init(int) void chokudai001::init(int N) { ^ ./Main.cpp:233:6: note: candidate expects 1 argument, 0 provided