結果
| 問題 |
No.585 工夫のないパズル
|
| コンテスト | |
| ユーザー |
 manugino
|
| 提出日時 | 2017-11-03 14:53:15 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 18,496 bytes |
| コンパイル時間 | 999 ms |
| コンパイル使用メモリ | 105,120 KB |
| 実行使用メモリ | 849,256 KB |
| 最終ジャッジ日時 | 2024-11-22 15:25:15 |
| 合計ジャッジ時間 | 18,331 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 7 TLE * 4 MLE * 1 |
ソースコード
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCodeでのEOF入力はCtrl+D
// ¥はAlt+\
// ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////
//yukicorder
//No.585 工夫のないパズル
//
//IDA*探索に挑戦したいが、まずは愚直に、昔8パズルでやったのを思い出して
//1. なにも考えず幅優先探索BFS
//結果：当然のごとくTLE・・・
//
//そういえば8パズルでは双方向探索で劇的に速くなったけど・・・
//2. せっかくだから双方向BFSまた実装してみるか、復習がてら。どうせTLEになるだろうとは思いつつ
//結果：それでも変わらず同じ問題でTLE・・・無駄な労力返せ〜
//
//ということでようやく本題のIDA*探索へ。大いに蟻本と渦巻本を参考にしながら
//3. 知識あり(ヒューリスティクスを使った) ID-DFS (Iterative Deepening Depth-First Search) である、ID-A*を実装
//結果：なんとダメでした。TLE。2のときより1問しか多く解けなかった。
//もっとフツーに攻略法ライクに解くんだってさ。これまた徒労でした。ちーん。。。
//
//3-a. 構造体PUZZLEの状態をstring stateで表現していたが、これを試しにchar配列にしてみると高速化されたりしないか実験
//なんとこれだけで大幅にACが増えた！！string使ってたのバカバカバカバカバカバカ！！
//86手の問題が解けて、96手の問題がTLEだったから、あとほんの少し高速化できればいけそうなんだけどなー。
//
//実例：
//まず以下が3.の状態でstringを使っている場合、
//FHLE
//MOIC
//DNPB
//AKGJ
//20
//R 0 2
//R 2 1
//R 3 1
//C 1 1
//R 2 1
//C 0 1
//R 3 3
//C 0 1
//R 0 3
//R 1 2
//R 2 2
//C 2 1
//R 1 1
//C 1 1
//R 2 2
//C 2 3
//R 2 1
//R 0 1
//C 2 2
//R 0 3
//numOfSearch = 318372
//0.0960 sec
//Program ended with exit code: 0
//
//そして以下がstateをchar配列に変えた場合であるが、めちゃめちゃ速くなった!!! 0.0960sec ===> 0.0300sec
//こういう構造体を自作するケースでstring使っちゃうとめっちゃ遅くなるんやなって実感できてたいへん勉強になりました。
//FHLE
//MOIC
//DNPB
//AKGJ
//20
//R 0 2
//R 2 1
//R 3 1
//C 1 1
//R 2 1
//C 0 1
//R 3 3
//C 0 1
//R 0 3
//R 1 2
//R 2 2
//C 2 1
//R 1 1
//C 1 1
//R 2 2
//C 2 3
//R 2 1
//R 0 1
//C 2 2
//R 0 3
//numOfSearch = 318372
//0.0300 sec
//Program ended with exit code: 0
//
//
//
//
//まだ意地でもad−hocのやり方やらずに、なんとか教科書解法で解こうとしている・・・ので、
//4. 知識あり(ヒューリティクスを使った) BFS (Breadth-First Search) である、A*を試しに実装してみる <== イマココ
//
////////////////////////////////////////
//#define debug //*******************************************************************************************************************************************
#ifdef debug
#include <chrono>
#endif
#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>
//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert
using namespace std;
#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif
#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif
#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) printf("%d\n", (A))
#define prints(A) printf("%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl
#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
//const int INF = (1LL<<31)-1;
const int NONE = -1;
//const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
//const ull INF_ULL = (ull)1e19-1ULL;
#define MOD 1000000007 //大きい素数の代表といえばこの人、10億7さん
#define N_MAX 3010 //num of vertex or element
#define M_MAX 124760 //num of edge
#define DATA_MAX 1010
#define N 4
#define N2 16
string GOAL = "ABCDEFGHIJKLMNOP";
//24 patterns of possible move
#define K_MAX 24
char dir[K_MAX] = {'R','R','R','R','R','R','R','R','R','R','R','R','C','C','C','C','C','C','C','C','C','C','C','C'}; //direction
int pos[K_MAX] = { 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 , 0 , 0 , 0 , 1 , 1 , 1 , 2 , 2 , 2 , 3 , 3 , 3 }; //position
int dif[K_MAX] = { 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 , 1 , 2 , 3 }; //difference
int MDT[N2][N2]; //Manhattan Distance Table
#define MOVE_MAX 120 //探索の最大深さ制限 = 最長手数100手の問題らしいので、これくらいで制限
#define H 3 //過去H手までさかのぼって打ち消さないかチェックする。H=1とH=3では、H=3のほうが圧倒的に高速！より多くの無駄な探索を枝刈りできるからだと思う
//4以上にする意味はない
ll numOfSearch = 0;
struct PUZZLE {
char state[N2+1];
int path[MOVE_MAX]; //初期状態からここまでの手
int cost; //初期状態からここまでの手数、pathに保存されている手の数に等しい
int md; //GOALまでのManhattan DistanceをGOALまでの推定コストとして利用
bool operator < (const PUZZLE &p) const { //for map
rep(i,0,N2) {
if( this->state[i]==p.state[i] ) continue;
else return this->state[i] < p.state[i];
}
return false; //completely same
}
static bool compareCost(const PUZZLE &x, const PUZZLE &y) { //for priority_queueのために定義してみたけど、priority_queueへの渡し方がわからなかったので、結局この関数は使っていない
//f(x) = g(x) + h*(x) = cost + md が小さいものを優先的に取り出したいので、lessではなく、greaterを定義してあげる必要がある
//cf. priority_queue はデフォルトで比較関数lessを使い、値の「大きい」ものから取り出すというあべこべな仕様のSTLなので
if( x.cost + x.md == y.cost + y.md ) { //全体コストが等しいときは、現時点までの手数が少ない方を優先する
return x.cost > y.cost; //greater
//完全に等しいときはfalseが返り、yが優先されてしまうはず。デフォルトだとlessでtrueのものが下に落ちていくので。まあ等しいんだからどっちが優先されてもいいけど
}
else {
return x.cost + x.md > y.cost + y.md; //greater
}
}
bool isGoal() {
// return this->state==GOAL;
return this->md==0;
}
void display() {
dout << "----\n";
disp(this->state);
show(path,0,this->cost);
disp(this->cost);
disp(this->md);
rep(i,0,N) {
rep(j,0,N) {
dout << this->state[i*N+j];
}
dout << endl;
}
dout << endl;
}
void rotate(int k) { //pをk番目 (k=0...23) の動かし方で1手動かして返す
//同時に、cost、path、mdも更新する
this->path[this->cost++] = k;
int start, last, jump;
char tmp[N2];
if(dir[k]=='R') {
jump = 1;
start = N * pos[k];
last = start + (N-1)*jump; // = start + 3
}
else {
assert(dir[k]=='C');
jump = N;
start = pos[k];
last = start + (N-1)*jump; // = start + 12
}
//一旦tmpにdifだけずらしてコピーしておいて
for(int i=start; i<=last; i+=jump) {
int next = i + dif[k] * jump;
if(next > last) next = i - (N - dif[k])*jump;
tmp[next] = state[i];
md -= MDT[i][state[i]-'A'];
}
//元の配列を更新する
for(int i=start; i<=last; i+=jump) {
state[i] = tmp[i];
md += MDT[i][state[i]-'A'];
}
}
static int getMD(PUZZLE p) {
int sum = 0;
rep(i,0,N2) {
sum += MDT[i][p.state[i]-'A'];
}
return sum;
}
};
void init() {
//calc. MDT
rep(i,0,N2) {
rep(j,0,N2) {
//通常のマンハッタン距離
MDT[i][j] = abs(i/N - j/N) + abs(i%N - j%N);
//同じ行or列にあれば1手で移動できる
//行も列も異なれば2手必要
// MDT[i][j] = (i/N != j/N) + (i%N != j%N);
//+2, +3移動もありで考えてた時代に考案した、マンハッタン距離より優秀なヒューリスティクスかと思っていたが、
//+2, +3移動は考えないことにしたので、ボツ
//むしろH*(x)の値が小さくなってしまって、枝刈りが少なくなるから全然優秀ではなかったのかもしれない
//ちなみに今の状態で、マンハッタン距離からこっちに変えると、探索数が100倍くらい増えて、めっちゃ遅くなる
}
}
}
void display() {
#ifdef debug
dout << "----\n";
dout << "MDT[][] = \n";
dout << " "; showi(j, 0, N2);
rep(i,0,N2) {
disP(i) << ":";
rep(j,0,N2) {
disP(MDT[i][j]);
}
dout << endl;
}
#endif
}
pair<int, vi> solve_Astar(PUZZLE initialState) { //解けたときの手数と手順を返す、解けなかった場合はNONEと空配列を返す
//初期状態のMD
initialState.md = PUZZLE::getMD(initialState);
#ifdef debug
dout << "Initial State =\n";
initialState.display();
#endif
//「これまでのコスト＋ゴールまでの推定コスト」が小さいものから取り出すキュー
auto compareCost = [](const PUZZLE &x, const PUZZLE &y) {
if( x.cost + x.md == y.cost + y.md ) return x.cost > y.cost;
else return x.cost + x.md > y.cost + y.md;
};
priority_queue<PUZZLE, vector<PUZZLE>, decltype(compareCost)> Q(compareCost);
Q.push(initialState);
//すでに探索済みの状態を記録しておくマップ
map<PUZZLE, bool> V;
V[initialState] = true;
//BFS according to A*
PUZZLE x, y;
while(not Q.empty()) {
x = Q.top(); Q.pop();
numOfSearch++;
if(x.cost >= MOVE_MAX) {
//問題の制約により、ここにたどり着くことはありえないはず
dout << "手数が制限を超えました!!\n";
disp(x.cost);
disp(MOVE_MAX);
break;
}
#ifdef debug
dout << "====================================\n";
disp(numOfSearch);
x.display();
#endif
//judge if solved or not
if( x.isGoal() ) {
#ifdef debug
dout << "SOLVED!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!\n";
#endif
//optimize the solution, path and cost
//+2, +3するmoveをskipしていたので、+1 moveが連続する箇所を、対応する+2 move or +3 moveに変換する
int ans = 0;
vi sol;
sol.push_back(x.path[0]);
rep(i,1,x.cost) {
if( dir[sol[ans]] == dir[x.path[i]] and pos[sol[ans]] == pos[x.path[i]] ) {
sol[ans]++;
}
else {
sol.push_back(x.path[i]);
ans++;
}
}
ans++;
// rep(i,0,x.cost-1) {
// if( dir[x.path[i]] == dir[x.path[i+1]] and pos[x.path[i]] == pos[x.path[i+1]]) {
// x.path[i+1] += dif[x.path[i]];
// x.path[i] = NONE;
// ans--;
// }
// }
return make_pair(ans, sol);
}
//現在の状態から1手で実現できる状態を列挙する
//その際、x.pathを参照し、直近のH手を打ち消すような手はskipする
rep(k,0,K_MAX) {
if(k%(N-1)!=0) continue; //+2, +3だけ動かすmoveは、結局+1 moveの繰り返しなので、ignoreする
y = x; //xのcopyであるyをrotateさせていく
#ifdef debug
dout << "--------次の1手で実現できる状態の列挙\n";
disp(k);
disP(dir[k]);
disP(pos[k]);
disP(dif[k]);
dout << endl;
#endif
bool shouldIgnore = false;
int difContinuouslyByMoveHistory = 0; //kと同じdir[]、pos[]を、過去H手で「連続で」どれくらい動かしたか？
for(int i=y.cost-1; i>=y.cost-H; i--) {
if( i<0 ) break;
if( dir[k]!=dir[y.path[i]] or pos[k]!=pos[y.path[i]] ) break;
difContinuouslyByMoveHistory += dif[y.path[i]];
if( dif[k] + difContinuouslyByMoveHistory == N ) {
#ifdef debug
dout << "直近の数手を打ち消す手なので、ignore\n";
#endif
shouldIgnore = true;
break;
}
}
if(shouldIgnore) continue;
//kが無視すべきでない手であれば
y.rotate(k); //その手を実行し、
if(not V[y]) { //yがまだVに登録されていなければ = 未探索のノードであれば
Q.push(y);
V[y] = true;
#ifdef debug
y.display();
dout << "since the above y has not been searched yet, add into Q.\n";
#endif
}
} //end of k-loop
} //end of while(not Q.empty) loop
#ifdef debug
dout << "すべての手を試した or 手数がLIMITを超えたので、NONEと空配列を返す\n";
#endif
vi empty;
return make_pair(NONE, empty);
}
int main() {
//cin, coutの高速化 ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
cin.tie(0); //cinとcoutの同期を切る
ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
//read input data
// scand(N);
string s;
char ss[N2+1];
rep(i,0,N) {
din >> s;
rep(j,0,N) {
ss[i*N+j] = s[j];
}
}
ss[N2] = '\0';
//------------------------------------------------------------------------------------------
#ifdef debug
//start timer
auto startTime = chrono::system_clock::now();
#endif
//------------------------------------------------------------------------------------------
PUZZLE puzzle;
strcpy(puzzle.state, ss);
init();
display();
pair<int, vi> result = solve_Astar(puzzle);
#ifdef debug
dout << "=== OUTPUT ===\n";
#endif
if( result.first!=NONE ) {
dout << result.first << endl;
rep(i,0,result.first) {
if( result.second[i]==NONE ) continue;
dout << dir[result.second[i]] << " " << pos[result.second[i]] << " " << dif[result.second[i]] << endl;
}
}
else {
dout << "UNSOLVABLE!!!\n";
}
// disp(numOfSearch); //FOR DEBUG ONLY
//------------------------------------------------------------------------------------------
#ifdef debug
//stop timer
auto endTime = chrono::system_clock::now();
auto dur = endTime - startTime;
auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
#endif
//------------------------------------------------------------------------------------------
#ifdef INPUTFILE
inputfile.close();
#endif
#ifdef OUTPUTFILE
outputfile.close();
cout << "\"" << OutputFilePath << "\"" << endl;
#endif
return 0;
}