結果
| 問題 | No.5006 Hidden Maze |
| コンテスト | |
| ユーザー |
👑  wanui
|
| 提出日時 | 2022-06-12 16:47:30 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,681 bytes |
| コンパイル時間 | 2,491 ms |
| 実行使用メモリ | 22,900 KB |
| スコア | 39,341 |
| 平均クエリ数 | 607.12 |
| 最終ジャッジ日時 | 2022-06-12 16:47:46 |
| 合計ジャッジ時間 | 15,154 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge12 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 71 WA * 29 |
ソースコード
#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18;
void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);}
void print(){print0("\n");}; template<typename H,typename... T>void print(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print(t...);}
void perr0(){}; template<typename H,typename... T> void perr0(H h,T... t){cerr<<h;perr0(t...);}
void perr(){perr0("\n");}; template<typename H,typename... T>void perr(H h,T... t){perr0(h);if(sizeof...(T)>0)perr0(" ");perr(t...);}
void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); }
// clang-format on
using pii = pair<int, int>;
using tii = tuple<int, int, int>;
struct point {
int i;
int j;
};
bool operator==(const point &lhs, const point &rhs) { return (lhs.i == rhs.i && lhs.j == rhs.j); }
bool operator!=(const point &lhs, const point &rhs) { return !(lhs == rhs); }
bool operator<(const point &lhs, const point &rhs) {
if (lhs.i != rhs.i) {
return lhs.i < rhs.i;
}
return lhs.j < rhs.j;
}
std::ostream &operator<<(std::ostream &os, point &pt) {
string s;
s.push_back('(');
s = s + to_string(pt.i);
s = s + ", ";
s = s + to_string(pt.j);
s.push_back(')');
return os << s;
}
mt19937 engine(0);
clock_t start_time;
double now() {
return 1000.0 * (clock() - start_time) / CLOCKS_PER_SEC;
}
void marathon_init() {
start_time = clock();
random_device seed_gen;
engine.seed(seed_gen());
}
int randint(int mn, int mx) {
int rng = mx - mn + 1;
return mn + (engine() % rng);
}
double uniform(double x, double y) {
const int RND = 1e8;
double mean = (x + y) / 2.0;
double dif = y - mean;
double p = double(engine() % RND) / RND;
return mean + dif * (1.0 - 2.0 * p);
}
bool anneal_accept(double new_score, double old_score, double cur_time, double begin_time, double end_time, double begin_temp, double end_temp) {
const int ANNEAL_RND = 1e8;
const double ANNEAL_EPS = 1e-6;
double temp = cur_time * (end_temp - begin_temp) / (end_time - begin_time) + (end_time * begin_temp - end_temp * begin_time) / (end_time - begin_time);
return (exp((new_score - old_score) / temp) > double(engine() % ANNEAL_RND) / ANNEAL_RND + ANNEAL_EPS);
}
const int N = 20;
const int OPS = 1000;
double P;
const int R = 0;
const int D = 1;
const int L = 2;
const int U = 3;
vector<point> mvs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int request(string ops) {
cout << ops << endl;
int res;
cin >> res;
return res;
}
string rand_combination(string s0, int start_ind) {
string s = s0;
int r = 0;
int d = 0;
for (int j = 0; j < start_ind; j++) {
if (s[j] == 'R') r++;
if (s[j] == 'D') d++;
}
for (int i = start_ind; i < int(s.size()); i++) {
if (r < N - 1 && d < N - 1) {
if (randint(0, 1)) {
s[i] = 'R';
r++;
} else {
s[i] = 'D';
d++;
}
} else if (r < N - 1) {
s[i] = 'R';
r++;
} else {
s[i] = 'D';
d++;
}
}
return s;
}
string randrd(int length) {
string s;
for (int o = 0; o < length; o++) {
if (randint(0, 1)) {
s.push_back('R');
} else {
s.push_back('D');
}
}
return s;
}
string makeop(int opid, vector<pair<int, string>> &history) {
// とりあえず R と D だけ。それで到達できないケースは諦める。
int N2 = 2 * N - 2;
// 全探索モード
do {
const int BRUTE_FORCE_START = 28;
pair<int, string> maxhist = {0, ""};
for (auto h : history) {
if (maxhist.first < h.first) {
maxhist = h;
}
}
if (maxhist.first < BRUTE_FORCE_START) {
break;
}
unordered_set<string> hist_ops;
for (auto h : history) {
hist_ops.insert(h.second);
}
int baseind = maxhist.first + 1;
int brute_force_num = N2 - baseind;
int r0 = 0;
int d0 = 0;
{
string s = maxhist.second;
for (int j = 0; j < baseind; j++) {
if (s[j] == 'R') r0++;
if (s[j] == 'D') d0++;
}
}
for (int i = 0; i < (1 << brute_force_num); i++) {
string s = maxhist.second;
int r = r0;
int d = d0;
for (int j = 0; j < brute_force_num; j++) {
char c;
if ((i >> j) & 1) {
c = 'R';
r++;
} else {
c = 'D';
c++;
}
s[j + baseind] = c;
}
if (r > N - 1 || d > N - 1) continue;
if (hist_ops.count(s)) continue;
return s;
}
} while (0);
// 完全な無作為
if (history.size() < 50 || opid % 10 == 0) {
string s;
s.resize(N2);
return rand_combination(s, 0);
}
// 適当にサンプリング+改変
{
pair<int, string> sample = history.back();
double total = 0;
for (auto h : history) {
total += (pow(1.0 * h.first, 2.0) + 0.5);
}
double rat = uniform(0.0, 1.0 * total);
double cum = 0;
for (auto h : history) {
cum += (pow(1.0 * h.first, 2.0) + 0.5);
if (rat < cum) {
sample = h;
break;
}
}
if (sample.second.size() <= 1) {
return randrd(N2);
}
// 後ろの方を適当に改変
string sample_str = sample.second;
int sample_moves = sample.first;
int sz = sample_str.size();
int changestart = sample_moves + randint(-2, 2);
if (changestart < 0) changestart = 0;
return rand_combination(sample_str, changestart);
}
return "R";
}
void solve() {
int opslimit = OPS;
opslimit = 1000;
int maxres = 0;
vector<pair<int, string>> history;
for (int opid = 0; opid < opslimit; opid++) {
string s = makeop(opid, history);
int res = request(s);
if (res < 0) {
return;
}
history.push_back({res, s});
maxres = max(maxres, res);
}
}
int main() {
marathon_init();
ioinit();
int _h, _w;
cin >> _h >> _w >> P;
P *= 0.01;
solve();
return 0;
}