結果

問題 No.173 カードゲーム（Medium）
ユーザー yuppe19 😺yuppe19 😺
提出日時 2015-05-15 16:41:57
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,593 bytes
コンパイル時間 439 ms
コンパイル使用メモリ 30,012 KB
最終ジャッジ日時 2024-11-14 19:03:16
合計ジャッジ時間 908 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:15:1: error: ‘vector’ does not name a type
   15 | vector<unsigned int> mt;
      | ^~~~~~
main.cpp: In function ‘void init_genrand(unsigned int)’:
main.cpp:19:3: error: ‘mt’ was not declared in this scope; did you mean ‘mti’?
   19 |   mt.push_back(s & 0xffffffffU);
      |   ^~
      |   mti
main.cpp: At global scope:
main.cpp:26:6: error: variable or field ‘init_by_array’ declared void
   26 | void init_by_array(vector<unsigned int> init_key) {
      |      ^~~~~~~~~~~~~
main.cpp:26:20: error: ‘vector’ was not declared in this scope
   26 | void init_by_array(vector<unsigned int> init_key) {
      |                    ^~~~~~
main.cpp:4:1: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
    3 | #include <algorithm>
  +++ |+#include <vector>
    4 | using namespace std;
main.cpp:26:27: error: expected primary-expression before ‘unsigned’
   26 | void init_by_array(vector<unsigned int> init_key) {
      |                           ^~~~~~~~
main.cpp: In function ‘unsigned int genrand_int32()’:
main.cpp:54:12: error: ‘mt’ was not declared in this scope; did you mean ‘mti’?
   54 |       y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      |            ^~
      |            mti
main.cpp:58:12: error: ‘mt’ was not declared in this scope; did you mean ‘mti’?
   58 |       y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      |            ^~
      |            mti
main.cpp:61:10: error: ‘mt’ was not declared in this scope; did you mean ‘mti’?
   61 |     y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
      |          ^~
      |          mti
main.cpp:65:7: error: ‘mt’ was not declared in this scope; did you mean ‘mti’?
   65 |   y = mt[mti++];
      |       ^~
      |       mti
main.cpp: At global scope:
main.cpp:77:12: error: ‘vector’ was not declared in this scope
   77 | int choose(vector<int> &v, int prob, int n) {
      |

ソースコード

diff # 

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

class range {private: struct I{int x;int operator*(){return x;}bool operator!=(I& lhs){return x<lhs.x;}void operator++(){++x;}};I i,n;
public:range(int n):i({0}),n({n}){}range(int i,int n):i({i}),n({n}){}I& begin(){return i;}I& end(){return n;}};

const int N = 624;
const int M = 397;
const unsigned int MATRIX_A = 0x9908b0dfU;
const unsigned int UPPER_MASK = 0x80000000U;
const unsigned int LOWER_MASK = 0x7fffffffU;

vector<unsigned int> mt;
int mti = N + 1;

void init_genrand(unsigned int s) {
  mt.push_back(s & 0xffffffffU);
  for(mti=1; mti<N; mti++) {
    mt.push_back(1812433253U * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
    mt[mti] &= 0xffffffffU;
  }
}

void init_by_array(vector<unsigned int> init_key) {
  int key_length = init_key.size();
  init_genrand(19921223U);
  int i = 1, j = 0;
  int k = N > key_length ? N : key_length;
  for( ; k; k--) {
    mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1664525U)) + init_key[j] + j;
    mt[i] &= 0xffffffffU;
    i++; j++;
    if(i >= N) { mt[0] = mt[N-1]; i = 1; }
    if(j >= key_length) { j = 0; }
  }
  for(k=N-1; k; k--) {
    mt[i] = (mt[i] ^ ((mt[i-1] ^ (mt[i-1] >> 30)) * 1566083941U)) - i;
    mt[i] &= 0xffffffffU;
    i++;
    if(i >= N) { mt[0] = mt[N-1]; i = 1; }
  }
  mt[0] = 0x80000000U;
}

unsigned int genrand_int32(void) {
  unsigned int y;
  static unsigned int mag01[2] = {0x0U, MATRIX_A};
  if(mti >= N) {
    if(mti == N + 1) { init_genrand(5489U); }
    int kk;
    for(kk=0; kk<N-M; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
    }
    for(; kk<N-1; kk++) {
      y = (mt[kk] & UPPER_MASK) | (mt[kk+1] & LOWER_MASK);
      mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
    }
    y = (mt[N-1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
    mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];
    mti = 0;
  }
  y = mt[mti++];
  y ^= (y >> 11);
  y ^= (y << 7) & 0x9d2c5680U;
  y ^= (y << 15) & 0xefc60000U;
  y ^= (y >> 18);
  return y;
}

int genrand_int31(void) {
  return (int)(genrand_int32() >> 1);
}

int choose(vector<int> &v, int prob, int n) {
  int minp = 0;
  for(int i : range(1, n)) {
    if(v[i] < v[minp]) { minp = i; }
  }
  int p;
  if(genrand_int31() % 1000 < prob) {
    p = minp;
  } else {
    swap(v[minp], v[n-1]);
    p = genrand_int31() % (n-1);
  }
  swap(v[p], v[n-1]);
  return v[n-1];
}

int main(void) {
  clock_t start = clock();
  time_t seed = time(0);
  vector<unsigned int> init;
  init.push_back(0x123);
  init.push_back(0x234);
  init.push_back(0x345);
  init.push_back(0x456);
  init.push_back(seed);
  init_by_array(init);

  int n;
  float da, db;
  scanf("%d%f%f", &n, &da, &db);
  int pa = da * 1000, pb = db * 1000;
  vector<int> a, b;
  for(int i : range(n)) { int x; scanf("%d", &x); a.push_back(x); }
  for(int i : range(n)) { int x; scanf("%d", &x); b.push_back(x); }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  int game, win;
  int limit = 2.8 * CLOCKS_PER_SEC;
  for(game=0, win=0; clock()-start < limit; game++) {
    vector<int> cpa = a, cpb = b;
    int suma = 0, sumb = 0;
    for(int i : range(n-1)) {
      int ca = choose(cpa, pa, n-i);
      int cb = choose(cpb, pb, n-i);
      if(ca > cb) { suma += ca+cb; }
      else { sumb += ca+cb; }
    }
    int ca = cpa[0], cb = cpb[0];
    if(ca > cb) { suma += ca+cb; }
    else { sumb += ca+cb; }
    if(suma > sumb) { win++; }
  }
  printf("%f\n", float(win) / game);
  return 0;
}
// (ΦωΦ)＜試行回数が増えてるはず！
0