結果

問題 No.5006 Hidden Maze
ユーザー hiikunZhiikunZ
提出日時 2022-06-12 16:06:13
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,636 ms / 2,000 ms
コード長 5,565 bytes
コンパイル時間 2,186 ms
実行使用メモリ 22,856 KB
スコア 1,252
平均クエリ数 988.48
最終ジャッジ日時 2022-06-12 16:11:53
合計ジャッジ時間 165,674 ms
ジャッジサーバーID
(参考情報)
judge16 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 100
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
constexpr ll MAX = 2000000000000000000;
constexpr ld PI = 3.14159265358979;
constexpr ll MOD = 0;//2024948111;
ld dotorad(ld K){return PI * K / 180.0;}
ld radtodo(ld K){return K * 180.0 / PI;}
mt19937 mt;
void randinit(){srand((unsigned)time(NULL));mt = mt19937(rand());}
ll sute,P;
ll cnt_h[21][20],cnt_w[20][21];//○
ll k = 0;
struct state{
bool visited[20][20];
ll I,J;
ld score;
string move;
ld kaku;
void init(){
for(ll i = 0;i < 20;i++) for(ll j = 0;j < 20;j++) visited[i][j] = 0;
I = 0;
J = 0;
visited[0][0] = 1;
score = 0;
move = "";
kaku = 1.0;
}
};
vector<state> next(state now){
vector<state> res;
{
//UP
state s = now;
if(cnt_h[s.I][s.J] <= 3){
if(cnt_h[s.I][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
for(ll f = 0;f < cnt_h[s.I][s.J];f++){
s.kaku *= 1.0 * P / 100.0;
}
s.I--;
s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
s.visited[s.I][s.J] = 1;
s.move += 'U';
res.emplace_back(s);
}
}
{
//DOWN
state s = now;
if(cnt_h[s.I + 1][s.J] <= 3){
if(cnt_h[s.I + 1][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
for(ll f = 0;f < cnt_h[s.I + 1][s.J];f++){
s.kaku *= 1.0 * P / 100.0;
}
s.I++;
s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
s.visited[s.I][s.J] = 1;
s.move += 'D';
res.emplace_back(s);
}
}
{
//LEFT
state s = now;
if(cnt_w[s.I][s.J] <= 3){
if(cnt_w[s.I][s.J] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
for(ll f = 0;f < cnt_w[s.I][s.J];f++){
s.kaku *= 1.0 * P / 100.0;
}
s.J--;
s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
s.visited[s.I][s.J] = 1;
s.move += 'L';
res.emplace_back(s);
}
}
{
//RIGHT
state s = now;
if(cnt_w[s.I][s.J + 1] <= 3){
if(cnt_w[s.I][s.J + 1] <= 0) s.kaku *= 1.0 * (100 - P) / 100.0;
for(ll f = 0;f < cnt_w[s.I][s.J + 1];f++){
s.kaku *= 1.0 * P / 100.0;
}
s.J++;
s.score += (1 - s.visited[s.I][s.J]) * 100000000 * s.kaku;
s.visited[s.I][s.J] = 1;
s.move += 'R';
res.emplace_back(s);
}
}
return res;
}
bool operator< (const state &s1, const state &s2){
return s1.score < s2.score;
};
int main(){
int ti = clock();
cin >> sute >> sute >> P;
for(ll i = 0;i < 21;i++){
for(ll j = 0;j < 20;j++){
cnt_h[i][j] = (i == 0 || i == 20) * 100;
cnt_w[j][i] = (i == 0 || i == 20) * 100;
}
}
while(1){
//cout<<k<<endl;
vector<priority_queue<state,vector<state>>> que(401);
state s;
s.init();
que[0].emplace(s);
state a = s,b = s;
k++;
while(1){
for(ll i = 0;i <= 400;i++){
if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break;
if(!que[i].empty()){
state s = que[i].top();
//\/ if(i%100==0)cout << i << "," << s.score << " " << s.kaku<<" "<<s.move.size()<< endl;
que[i].pop();
if(s.I == 19 && s.J == 19){
if(a.score < s.score){
a = s;
}
}
if(b.score < s.score){
b = s;
}
if(i != 400){
vector<state> S = next(s);
for(ll j = 0;j < (ll)S.size();j++) que[i + 1].emplace(S[j]);
while(que[i + 1].size() > 3) que[i + 1].pop();
}
}
}
if(1.0 * (clock() - ti) / CLOCKS_PER_SEC > 1.5 / 1000 * k) break;
}
if(k % 10 != 0 || a.move.size() == 0) a = b;
cout << a.move << endl;
ll res;
cin >> res;
if(res == -1) return 0;
ll I = 0,J = 0;
for(ll i = 0;i < res;i++){
if(a.move[i] == 'U'){
cnt_h[I][J] = -1;
I--;
}
if(a.move[i] == 'D'){
cnt_h[I + 1][J] = -1;
I++;
}
if(a.move[i] == 'L'){
cnt_w[I][J] = -1;
J--;
}
if(a.move[i] == 'R'){
cnt_w[I][J + 1] = -1;
J++;
}
}
if(res != (ll)a.move.size()){
ll i = res;
if(a.move[i] == 'U'){
if(cnt_h[I][J] != -1) cnt_h[I][J]++;
}
if(a.move[i] == 'D'){
if(cnt_h[I + 1][J] != -1) cnt_h[I + 1][J]++;
I++;
}
if(a.move[i] == 'L'){
if(cnt_w[I][J] != -1) cnt_w[I][J]++;
J--;
}
if(a.move[i] == 'R'){
if(cnt_w[I][J + 1] != -1) cnt_w[I][J + 1]++;
J++;
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0