HACK TO THE FUTURE 2018 予選
HACK TO THE FUTURE 2018 予選
やったこと
開始 ~ 2:00
山からピラミッドを引いて平らにしていく．あんま上手くいかない．
2:00 ~ 3:00
乱数生成のテストケースにおいては極端にガタガタした地形が発生することはなく，だいたいお椀を逆さにしたような形状になる．
テストケース生成と同様の方法でお椀形の山を作り，その差分がなるべく小さくなるような初期解を選択する．
0.5 秒くらいループを回すと diff 2000000 程度まで行く．
3:00 ~ 7:30
初期解選択後はランダムにピラミッドを崩しては建てるのを繰り返す．
1 つのピラミッド (x, y, h) を取り除く．その近傍 (だいたい距離 3 ~ 10) の座標 (nx, ny) をランダムに拾ってきて，
最も diff が小さくなるようなピラミッドの高さ nh を二分探索で求めて追加する．
近傍を時間変化させたりパラメータチューニングを頑張ったら diff が平均で 50000 近くになった．
順位 17 位になり，テンションがおかしくなる．
7:30 ~ 8:00
潜伏勢にガンガン抜かされて激焦るが，もう頭が働かないので祈りながらコードを投げ続ける．
最終提出時 26 位まで落ちて愕然
オンサイト頼むから通っててくれ……
得点最も高かった提出の糞汚いコード
#define _CRT_SECURE_NO_WARNINGS #include "bits/stdc++.h" #include <random> //#include "util.k" using namespace std; //呪文 #define DUMPOUT cout #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 typedef pair<pii, int> pi3; // x, y, h const int N = 100; unsigned long w; unsigned long xor128() { static unsigned long x = 123456789, y = 362436069, z = 521288629/*, _w = 88675123*/; unsigned long t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } vector<pi3> mk_random_testcase() { vector<pi3> res; for (int i = 0; i < 1000; i++) { int x = xor128() % N; int y = xor128() % N; int h = xor128() % N + 1; res.push_back(pi3(pii(x, y), h)); } return res; } void out_vvi(string filename, vector<vector<int>>& A) { ofstream ofs(filename); for (int i = 0; i < A.size(); i++) { ofs << A[i][0]; for (int j = 1; j < A[i].size(); j++) { ofs << " " << A[i][j]; } ofs << endl; } } void out_vpi3(string filename, vector<pi3>& points) { ofstream ofs(filename); ofs << points.size() << endl; for (int i = 0; i < points.size(); i++) { ofs << points[i].first.first << " " << points[i].first.second << " " << points[i].second << endl; } } void mk_pyramid(vector<vector<int>>& dst, const vector<pi3>& points) { for (int i = 0; i < points.size(); i++) { int x = points[i].first.first; int y = points[i].first.second; int h = points[i].second; for (int dy = 1 - h; dy <= h - 1; dy++) { int ny = y + dy; if (ny < 0 || N <= ny) continue; int abs_dy = abs(dy); for (int dx = abs_dy + 1 - h; dx <= h - 1 - abs_dy; dx++) { int nx = x + dx; if (nx < 0 || N <= nx) continue; dst[ny][nx] += h - abs(nx - x) - abs(ny - y); } } } } ll getDifference(const vector<vector<int>>& p) { ll res = 0; REP(i, N) REP(j, N) { res += abs(p[i][j]); } return res; } int getDifference(const vector<vector<int>>& p1, const vector<vector<int>>& p2) { int res = 0; REP(i, N) REP(j, N) { res += abs(p1[i][j] - p2[i][j]); } return res; } void pyramid_sub(vector<vector<int>>& A, int x, int y, int h) { for (int dy = 1 - h; dy <= h - 1; dy++) { int ny = y + dy; if (ny < 0 || N <= ny) continue; int abs_dy = abs(dy); for (int dx = abs_dy + 1 - h; dx <= h - 1 - abs_dy; dx++) { int nx = x + dx; if (nx < 0 || N <= nx) continue; A[ny][nx] -= h - abs(nx - x) - abs(ny - y); } } } void pyramid_add(vector<vector<int>>& A, int x, int y, int h) { for (int dy = 1 - h; dy <= h - 1; dy++) { int ny = y + dy; if (ny < 0 || N <= ny) continue; int abs_dy = abs(dy); for (int dx = abs_dy + 1 - h; dx <= h - 1 - abs_dy; dx++) { int nx = x + dx; if (nx < 0 || N <= nx) continue; A[ny][nx] += h - abs(nx - x) - abs(ny - y); } } } void pyramid_increment(vector<vector<int>>& A, int x, int y, int h) { for (int dy = 1 - h; dy <= h - 1; dy++) { int ny = y + dy; if (ny < 0 || N <= ny) continue; int abs_dy = abs(dy); for (int dx = abs_dy + 1 - h; dx <= h - 1 - abs_dy; dx++) { int nx = x + dx; if (nx < 0 || N <= nx) continue; A[ny][nx]++; } } } int argMinH(const vector<vector<int>>& target, vector<vector<int>>& src, int x, int y) { // argminh dif int from = 0, to = N; for (; to - from > 1;) { int mid = (from + to) / 2; pyramid_add(src, x, y, mid - 1); int difL = getDifference(target, src); pyramid_increment(src, x, y, mid); int difR = getDifference(target, src); pyramid_sub(src, x, y, mid); (difL - difR > 0 ? from : to) = mid; } return from; } int main() { //clock_t start, end; //start = clock(); cin.tie(0); ios::sync_with_stdio(false); srand((unsigned)time(NULL)); //w = 123457; w = rand(); vector<vector<int>> A(N, vector<int>(N, 0)); REP(i, N) REP(j, N) cin >> A[i][j]; //vector<pi3> testcase = mk_random_testcase(); //mk_pyramid(A, testcase); //out_vvi("input.txt", A); int betterscore = INT_MAX; vector<pi3> betterpoints; //int loopcnt = 0; // いい感じの初期分布を求める while ((double)clock() / CLOCKS_PER_SEC < 0.5) { //loopcnt++; vector<vector<int>> B(N, vector<int>(N, 0)); vector<pi3> points = mk_random_testcase(); mk_pyramid(B, points); int score = getDifference(A, B); if (score < betterscore) { betterscore = score; betterpoints = points; //dump(betterscore); } } //cerr << loopcnt << endl; //dump(loopcnt); // ランダムに 1 頂点を選び取り除く． // ランダムに何頂点か候補点を選び，いい感じの高さにして最も良かったのを採用 vector<vector<int>> B(N, vector<int>(N, 0)); mk_pyramid(B, betterpoints); //dump(getDifference(A, B)); double t; while ((t = (double)clock() / CLOCKS_PER_SEC) < 5.985) { int Q = betterpoints.size(); // 現在の得点 int score = getDifference(A, B); int nx, ny, nh; bool update = false; // 取り除く点を選ぶ int index = xor128() % Q; pi3& p = betterpoints[index]; int& x = p.first.first, &y = p.first.second, &h = p.second; // 取り除く pyramid_sub(B, x, y, h); int d = min(10.01, 6 / t + 3), w = d / 2; for (int i = 0; i < 3; i++) { int dx = xor128() % d - w; int dy = xor128() % d - w; int xx = x + dx, yy = y + dy; if (xx < 0 || N <= xx || yy < 0 || N <= yy) { i--; continue; } int hh = argMinH(A, B, xx, yy); if (hh == 0) continue; pyramid_add(B, xx, yy, hh); int tmpscore = getDifference(A, B); if (tmpscore < score) { update = true; score = tmpscore; nx = xx; ny = yy; nh = hh; } pyramid_sub(B, xx, yy, hh); } if (update) { pyramid_add(B, nx, ny, nh); x = nx; y = ny; h = nh; } else { pyramid_add(B, x, y, h); } //dump(getDifference(A, B)); } //dump(getDifference(A, B)); //cerr << getDifference(A, B) << endl; cout << betterpoints.size() << endl; for (int i = 0; i < betterpoints.size(); i++) { cout << betterpoints[i].first.first << " " << betterpoints[i].first.second << " " << betterpoints[i].second << endl; } //out_vpi3("output.txt", betterpoints); //end = clock(); //printf("%d msec.\n", end - start); return 0; }
