結果

問題 No.753 最強王者決定戦
ユーザー tnakao0123tnakao0123
提出日時 2018-11-11 02:34:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 312 ms / 1,000 ms
コード長 2,557 bytes
コンパイル時間 666 ms
コンパイル使用メモリ 87,780 KB
実行使用メモリ 12,228 KB
最終ジャッジ日時 2023-08-18 05:03:32
合計ジャッジ時間 2,710 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 310 ms
12,180 KB
testcase_01 AC 312 ms
12,188 KB
testcase_02 AC 306 ms
12,228 KB
testcase_03 AC 309 ms
12,132 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 753.cc:  No.753 最強王者決定戦 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int BN = 4;
const int N = 1 << BN;
const int NBITS = 1 << N;

/* typedef */

typedef long long ll;
typedef vector<int> vi;

/* global variables */

int bnums[NBITS];
vi nbbs[BN + 1], hbs[BN + 1];
int wls[N][N];
ll dp[NBITS][N];

/* subroutines */

inline void bits2v(int bits, vi &v) {
  v.clear();
  for (int i = 0, bi = 1; bi <= bits; i++, bi <<= 1)
    if (bits & bi) v.push_back(i);
}

inline int v2hbits(vi &v, int hb) {
  int hbits = 0;
  for (int i = 0, bi = 1; i < v.size(); i++, bi <<= 1)
    if (hb & bi) hbits |= (1 << v[i]);
  return hbits;
}

/* main */

int main() {
  bnums[0] = 0;
  for (int bits = 1, msb = 1; bits < NBITS; bits++) {
    if ((msb << 1) <= bits) msb <<= 1;
    int bn = bnums[bits] = bnums[bits ^ msb] + 1;
    if (bnums[bn] == 1) {
      int k = 0;
      while (bn > 1) k++, bn >>= 1;
      nbbs[k].push_back(bits);
    }
  }
  //for (int i = 0; i <= BN; i++) printf("%d: %lu\n", i, nbbs[i].size());

  for (int bn = 1; bn <= BN; bn++) {
    int n = 1 << bn, hn = n >> 1;
    int nbits = 1 << n;
    for (int bits = 0; bits < nbits; bits++)
      if (bnums[bits] == hn) hbs[bn].push_back(bits);
  }
  //for (int i = 0; i <= BN; i++) printf("%d: %lu\n", i, hbs[i].size());

  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++) {
      scanf("%d", &wls[i][j]);
      if (i > j) wls[i][j] = -wls[j][i];
    }

  for (int i = 0; i < N; i++) dp[1 << i][i] = 1;

  for (int bn = 1; bn <= BN; bn++) {
    vi &nbb = nbbs[bn], hbb = hbs[bn];
    for (vi::iterator vit = nbb.begin(); vit != nbb.end(); vit++) {
      int &bits = *vit;
      vi bv;
      bits2v(bits, bv);

      for (vi::iterator hvit = hbb.begin(); hvit != hbb.end(); hvit++) {
	int hbits = v2hbits(bv, *hvit);
	int rbits = bits ^ hbits;
	for (int i = 0, bi = 1; i < N; i++, bi <<= 1)
	  if (hbits & bi)
	    for (int j = 0, bj = 1; j < N; j++, bj <<= 1)
	      if (rbits & bj) {
		if (wls[i][j] > 0)
		  dp[bits][i] += dp[hbits][i] * dp[rbits][j];
		else
		  dp[bits][j] += dp[hbits][i] * dp[rbits][j];
	      }
      }
    }
  }

  for (int i = 0; i < N; i++)
    printf("%lld\n", dp[NBITS - 1][i]);
  return 0;
}
0