2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

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

Last updated at Posted at 2019-02-16

北大・日立新概念コンピューティングコンテスト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. 上記以外の場合、必要な時には先頭2つの項のどちらかが0になるようにと神に祈りながら先頭2つの掛け算の項を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;
        }
    }
}

// どれにも当てはまらない時、必要な時には先頭2つの項のどちらかが0になるようにと神に祈りながら先頭2つの掛け算の項を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;
}


2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?