結果

問題 No.586 ダブルブッキング
ユーザー manuginomanugino
提出日時 2017-11-03 22:32:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 8,458 bytes
コンパイル時間 724 ms
コンパイル使用メモリ 85,244 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-02 05:06:03
合計ジャッジ時間 1,241 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [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 <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 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<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;
}
0