新概念コンテスト2018で初めの論文を読んでの実装

北大・日立新概念コンピューティングコンテスト2018

現在、コンテスト中(2019年2月14日～2月27日)です。

問題はこっち
https://atcoder.jp/contests/hokudai-hitachi2018

論文"On Quadratization of Pseudo-Boolean Functions"を8割ぐらいを読んでの実装です。

ご自由にご利用ください。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>


const int MAX_L = 3000;


// 北大・日立新概念コンピューティングコンテスト2018
//
// ◇ 概要
//  論文"On Quadratization of Pseudo-Boolean Functions"を読んでの実装
// 
// ◇ 方針
// 次数が1か2であれば、そのまま入力の項を出力すればいい。
// よって、項数が3次以上を考えればいい。
// 入力f以上の値で、出力gをできるだけ小さくしたい。
// 上から優先で以下。
// 1. 係数cがマイナスの項は、c * w * ((d - 1) + sum(x))
// 2. 次数が3の時は、cxyz = c * ( w * (- (x + y + z) + 1) + x * y + y * z + z * x);
// 3. 次数が4,6の時は、 論文"On Quadratization of Pseudo-Boolean Functions"の(9)
//    （次数が2で割り切れるの時はこれが使えるが、結果の項数が増えるので高次の時はスコアーが下がるのでどこまで使うのかトレードオフがある）
// 4. 上記以外の場合、必要な時には先頭２つの項のどちらかが0になるようにと神に祈りながら先頭２つの掛け算の項をc

using namespace std;

// 結果を出力
void output(int S, int c_ret0, vector<int> & c_ret1, vector< vector<int> > & c_ret2) {
	// * 項数をcount
	int L = 0;

	// 定数項
	if (c_ret0 != 0) {
		L++;
	}

	// 次数1
	for (int c : c_ret1) {
		if (c != 0) {
			L++;
		}
	}

	// 次数2
	for (vector<int> & c2 : c_ret2) {
		for (int c : c2) {
			if (c != 0) {
				L++;
			}
		}
	}

	// * output
	// header
	cout << S << " " <<  L  << endl;
	
	// 定数項
	if (c_ret0 != 0) {
		cout << "0 " << c_ret0 <<  endl;
	}

	// 次数1
	for (int i = 0; i < c_ret1.size(); i++) {
		if (c_ret1[i] != 0) {
			cout << "1 " << c_ret1[i] << " " << i + 1 << endl; 
		}
	}
	// 次数2
	for (int i = 0; i < c_ret2.size(); i++) {
		for (int j = 0; j < c_ret2[i].size(); j++) {
			if (c_ret2[i][j] != 0) {
				cout << "2 " << c_ret2[i][j] << " " << i + 1 << " " << j + 1 << endl;
			}
		}
	}
}

// https://arxiv.org/pdf/1404.6538.pdf
// の(5)の実装
// 係数がマイナスの時、c * w * ((d - 1) + sum(x))
void calculateMinus(int c, vector<int>& v
	,int & S, int & c_ret0, vector<int> & c_ret1, vector< vector<int> > & c_ret2) {

	int d = v.size();
	int ws = S;
	S++;

	c_ret1[ws] = - c * (d - 1);

	for (int cur : v) {
		c_ret2[cur][ws] = c;
	}
}

// http://www.f.waseda.jp/hfs/MIRU2009.ppt
// の18ページ
// 三次の時、cxyz = c * ( w * (- (x + y + z) + 1) + x * y + y * z + z * x);
void calculate3degree(int c, vector<int>& v
	,int & S, int & c_ret0, vector<int> & c_ret1, vector< vector<int> > & c_ret2) {

	int ws = S;
	S++;

	sort(v.begin(), v.end());


	c_ret1[ws] = c;

	c_ret2[v[0]][ws] = -c;
	c_ret2[v[1]][ws] = -c;
	c_ret2[v[2]][ws] = -c;


	c_ret2[v[0]][v[1]] += c;
	c_ret2[v[1]][v[2]] += c;
	c_ret2[v[0]][v[2]] += c;
}


// https://arxiv.org/pdf/1404.6538.pdf
// 四次以上の偶数の時、論文"On Quadratization of Pseudo-Boolean Functions"の(9)の実装
void calculateEvenDegree(int c, vector<int>& v
	,int & S, int & c_ret0, vector<int> & c_ret1, vector< vector<int> > & c_ret2) {

	int d = v.size();
	int k = (d - 1) / 2;
	int ws = S;
	S += k;

	sort(v.begin(), v.end());
	
	for (int i = 0; i < d; i++) {
		for (int j = i + 1; j < d; j++) {
			c_ret2[v[i]][v[j]] += c;
		}
	}

	for (int i = 0; i < k; i++) {
		c_ret1[i + ws] = c * (4 * (i + 1) - 1);
	}

	for (int i = 0; i < d; i++) {
		for (int j = 0; j < k; j++) {
			c_ret2[v[i]][j + ws] = - c * 2;
		}
	}
}

// どれにも当てはまらない時、必要な時には先頭２つの項のどちらかが0になるようにと神に祈りながら先頭２つの掛け算の項をc
// (定数に加えるよりマシと思ったので)
void calcuateEtc(int c, vector<int>& v
	,int & S, int & c_ret0, vector<int> & c_ret1, vector< vector<int> > & c_ret2) {
	c_ret2[v[0]][v[1]] += c;

}

int main() {
	int N;
	int K;

	// * input
	cin >> N >> K;

	vector< vector<int> > v;
	vector<int> c;

	int c_d0 = 0;

	for (int i = 0; i < K; i++) {
		int d;
		int ct;

		cin >> d >> ct;
		c.push_back(ct);
		vector<int> v_row;

		for (int j = 0; j < d; j++) {
			int cur;
			cin >> cur;
			cur--;
			v_row.push_back(cur);
		}

		v.push_back(v_row);
	}

	// * out保存域の定義
	int S = N;

	// 定数項の結果
	int c_ret0 = 0; 

	// 1次項の係数の結果
	vector<int> c_ret1(MAX_L, 0);

	// 2次項の係数の結果（c_ret2[i][j]の時、必ず i < jとすること)
	vector< vector<int> > c_ret2(MAX_L, vector<int> (MAX_L, 0)); 


	// 計算
	for (int i = 0; i < K; i++) {
		int v_i_size = v[i].size();

		if (v_i_size == 0) {
			c_ret0 += c[i];
		} else if (v_i_size == 1) {
			c_ret1[v[i][0]] += c[i];
		} else if (v_i_size == 2) {
			c_ret2[v[i][0]][v[i][1]] += c[i];
		} else if (c[i] < 0) {
			calculateMinus(c[i] , v[i] ,S, c_ret0, c_ret1, c_ret2);
		} else if (v_i_size == 3) {
			calculate3degree(c[i] , v[i] ,S, c_ret0, c_ret1, c_ret2);
		} else if (v_i_size == 4 || v_i_size == 6) {
			calculateEvenDegree(c[i] , v[i] ,S, c_ret0, c_ret1, c_ret2);
		} else {
			calcuateEtc(c[i] , v[i] ,S, c_ret0, c_ret1, c_ret2);
			//c_ret0 += max(0, c[i]);
		}
	}

	// * output
	output(S, c_ret0, c_ret1, c_ret2);

	return 0;
}