//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// // [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*を試しに実装してみる <== イマココ //結果:全然TLE。サンプル問題3題くらいしかACならず。やっぱり優先順位比較とかする分めちゃめちゃ遅くなるんだなあ・・・。 //ただ、先の例で見ると以下の通り、実行速度はめちゃめちゃ遅いけど、探索回数自体はめちゃめちゃ減っているという。トレードオフやなあ。 //当然のごとく、最短手数は得られなくなっている。じゃあもうA*探索ってメリットなくない?って思っちゃう。 //FHLE //MOIC //DNPB //AKGJ //18 //R 0 1 //C 0 1 //R 3 1 //C 1 1 //C 3 1 //R 2 1 //C 3 1 //C 0 2 //R 1 2 //C 2 1 //R 0 2 //C 0 1 //R 1 1 //R 2 3 //C 0 1 //C 1 1 //R 2 1 //C 1 3 //numOfSearch = 43269 //2.2190 sec //Program ended with exit code: 0 //////////////////////////////////////// //#define debug //******************************************************************************************************************************************* #ifdef debug #include #endif #include #include // next_permutation #include #include #include #include #include #include //memcpy #include #include #include #include #include //accumulate #include //#include //hash func. #include //ifstream, ofstream #include //insert_iterator::inserter #include //#define NDEBUG //If NDEBUG is defined before #include , assert will be ignored. You had better define NDEBUG when u submit the code. #include //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 ii; typedef pair iii; typedef vector 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 110 //num of vertex or element #define M_MAX 124760 //num of edge #define DATA_MAX 1010 int R[N_MAX]; bool room[1000]; void init() { } void display() { #ifdef debug dout << "----\n"; #endif } 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); int N, myHotelCharge, altCharge; din >> myHotelCharge >> altCharge >> N; rep(i,0,N) { din >> R[i]; } //------------------------------------------------------------------------------------------ #ifdef debug //start timer auto startTime = chrono::system_clock::now(); #endif //------------------------------------------------------------------------------------------ int ans = 0; rep(i,0,N) { if(room[R[i]]) { ans += myHotelCharge + altCharge; } else room[R[i]] = true; } dout << ans << endl; //------------------------------------------------------------------------------------------ #ifdef debug //stop timer auto endTime = chrono::system_clock::now(); auto dur = endTime - startTime; auto msec = chrono::duration_cast(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; }