C++ の動作確認をしてみた（５３）

C++の練習を兼ねて, AtCoder Beginner Contest 117 の問題C（Streamline) ～問題D (XXOR) を解いてみた.

■感想.
1. 問題D は, 方針が掴めなかったので, 解説を確認して, おそらく, こんな感じと思った内容でコーディングしたものである.

本家のサイトABC 117 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
const int LIMIT = 1e5;

int main() {
    
    // 1. 入力情報取得.
    int N, M;
    cin >> N >> M;
    int X[M];
    FOR(i, 0, M) cin >> X[i], X[i] += LIMIT;
    
    // 2. 駒の移動回数をカウント.
    // 2-1. N >= M なら, 移動回数はゼロ回.
    LL ans = 0;
    if(N >= M){
        cout << ans << endl;
        return 0;
    }
    
    // 2-2. 区間の距離を保存.
    sort(X, X + M);
    int DIFF[M - 1];
    DIFF[0] = X[1] - X[0];
    FOR(i, 1, M) DIFF[i] = X[i + 1] - X[i];
    // FOR(i, 0, M) cout << X[i] << " ";
    // cout << endl;
    
    // 3. 区間の距離を降順sort.
    sort(DIFF, DIFF + M - 1);
    // FOR(i, 0, M - 1) cout << DIFF[i] << " ";
    
    // 4. 回数の最小値を計算.
    FOR(i, 0, M - N) ans += DIFF[i];
    
    // 5. 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

const int LIMIT = 1e5;

int main() {

// 1. 入力情報取得.

int N, M;

cin >> N >> M;

int X[M];

FOR(i, 0, M) cin >> X[i], X[i] += LIMIT;

// 2. 駒の移動回数をカウント.

// 2-1. N >= M なら, 移動回数はゼロ回.

LL ans = 0;

if(N >= M){

cout << ans << endl;

return 0;

}

// 2-2. 区間の距離を保存.

sort(X, X + M);

int DIFF[M - 1];

DIFF[0] = X[1] - X[0];

FOR(i, 1, M) DIFF[i] = X[i + 1] - X[i];

// FOR(i, 0, M) cout << X[i] << " ";

// cout << endl;

// 3. 区間の距離を降順sort.

sort(DIFF, DIFF + M - 1);

// FOR(i, 0, M - 1) cout << DIFF[i] << " ";

// 4. 回数の最小値を計算.

FOR(i, 0, M - N) ans += DIFF[i];

// 5. 後処理.

cout << ans << endl;

return 0;

}

■C++版プログラム(問題D／AC版).

// 解き直し.
// ABC 117 解説.
// https://img.atcoder.jp/abc117/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL DIGIT = 40;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

// n桁の0埋めの数字を作る.
// https://gin0606.hatenablog.com/entry/2013/12/24/134138
// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).
// @param d: 0埋め後の桁数.
string fillText(string s, LL d) {
    string ret = s;
    while(ret.size() < d) ret = "0" + ret;
    return ret;
}

// Use of dynamic bitset to convert decimal numbers.
// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers
// 10進数 → 2進数.
// @param n: 2進数へ変換したい10進数.
// @param d: 2進数表記する桁数.
// @return: 2進数.
string decimalToBinary(LL n, LL d) {
    if(n == 0) return fillText("0", d);
    string ret;
    LL ln = abs(n);
    while(ln) {
        ret = string((ln & 1) ? "1" : "0") + ret;
        ln /= 2;
    }
    ret = fillText(ret, d);
    if(n < 0) ret = "-" + ret;
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    // 以下, 解説通り.
    LL N, K;
    cin >> N >> K;
    string A[N];
    FOR(i, 0, N){
        LL a;
        cin >> a;
        // 40桁で設定.
        A[i] = decimalToBinary(a, DIGIT);
    }
    // ex.
    // 6 -> "0000000000000000000000000000000000000110"
    // FOR(i, 0, N) cout << A[i] << " ";
    // cout << endl;
    
    // 2. 2のべき乗を保存.
    LL pow2[DIGIT] = {};
    pow2[DIGIT - 1] = 1;
    FOR(i, 2, DIGIT + 1) pow2[DIGIT - i] = (2 * pow2[DIGIT - i + 1]);
    // ex.
    // pow2[0] = 549755813888, pow2[1] = 274877906944, ..., pow2[38] = 2, pow2[39] = 1
    // FOR(i, 0, DIGIT) cout << pow2[i] << " ";
    // cout << endl;
    
    // 3. A[0] ～ A[N - 1] の各桁について, 1の個数をカウント.
    LL bit1[DIGIT] = {};
    FOR(i, 0, DIGIT) FOR(j, 0, N) if(A[j][i] == '1') bit1[i]++;
    // FOR(i, 0, DIGIT) cout << bit1[i] << " ";
    // cout << endl;
    
    // 4. f の 最大値 を 計算.
    string bitK = decimalToBinary(K, DIGIT);
    string maxX  = "0000000000000000000000000000000000000000";
    LL ans = 0LL;
    FOR(i, 0, DIGIT){
        
        // i桁目で, maxX[i] を '0', '1' の場合で比較.
        // 4-1. maxX[i] = '0' の場合.
        string X0 = maxX;
        X0[i] = '0';
        LL inc0 = pow2[i] * bit1[i];
        
        // 4-2. maxX[i] = '1' の場合.
        string X1 = maxX;
        X1[i] = '1';
        LL inc1 = pow2[i] * (N - bit1[i]);
        
        // 4-3. 更新.
        if(X1 <= bitK && inc0 < inc1)  ans += inc1, maxX = X1;
        if(X1 <= bitK && inc0 >= inc1) ans += inc0, maxX = X0;
        if(X1 >  bitK)                 ans += inc0, maxX = X0;
        
    }
    
    // 5. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;

}

100

101

// 解き直し.

// ABC 117 解説.

// https://img.atcoder.jp/abc117/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL DIGIT = 40;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

// n桁の0埋めの数字を作る.

// https://gin0606.hatenablog.com/entry/2013/12/24/134138

// @param s: 0埋めしたい文字列(※d桁より多い場合は, 0埋め出来ないので何もしない).

// @param d: 0埋め後の桁数.

string fillText(string s, LL d) {

string ret = s;

while(ret.size() < d) ret = "0" + ret;

return ret;

}

// Use of dynamic bitset to convert decimal numbers.

// https://stackoverflow.com/questions/42759330/use-of-dynamic-bitset-to-convert-decimal-numbers

// 10進数 → 2進数.

// @param n: 2進数へ変換したい10進数.

// @param d: 2進数表記する桁数.

// @return: 2進数.

string decimalToBinary(LL n, LL d) {

if(n == 0) return fillText("0", d);

string ret;

LL ln = abs(n);

while(ln) {

ret = string((ln & 1) ? "1" : "0") + ret;

ln /= 2;

}

ret = fillText(ret, d);

if(n < 0) ret = "-" + ret;

return ret;

}

int main() {

// 1. 入力情報取得.

// 以下, 解説通り.

LL N, K;

cin >> N >> K;

string A[N];

FOR(i, 0, N){

LL a;

cin >> a;

// 40桁で設定.

A[i] = decimalToBinary(a, DIGIT);

}

// ex.

// 6 -> "0000000000000000000000000000000000000110"

// FOR(i, 0, N) cout << A[i] << " ";

// cout << endl;

// 2. 2のべき乗を保存.

LL pow2[DIGIT] = {};

pow2[DIGIT - 1] = 1;

FOR(i, 2, DIGIT + 1) pow2[DIGIT - i] = (2 * pow2[DIGIT - i + 1]);

// ex.

// pow2[0] = 549755813888, pow2[1] = 274877906944, ..., pow2[38] = 2, pow2[39] = 1

// FOR(i, 0, DIGIT) cout << pow2[i] << " ";

// cout << endl;

// 3. A[0] ～ A[N - 1] の各桁について, 1の個数をカウント.

LL bit1[DIGIT] = {};

FOR(i, 0, DIGIT) FOR(j, 0, N) if(A[j][i] == '1') bit1[i]++;

// FOR(i, 0, DIGIT) cout << bit1[i] << " ";

// cout << endl;

// 4. f の最大値を計算.

string bitK = decimalToBinary(K, DIGIT);

string maxX = "0000000000000000000000000000000000000000";

LL ans = 0LL;

FOR(i, 0, DIGIT){

// i桁目で, maxX[i] を '0', '1' の場合で比較.

// 4-1. maxX[i] = '0' の場合.

string X0 = maxX;

X0[i] = '0';

LL inc0 = pow2[i] * bit1[i];

// 4-2. maxX[i] = '1' の場合.

string X1 = maxX;

X1[i] = '1';

LL inc1 = pow2[i] * (N - bit1[i]);

// 4-3. 更新.

if(X1 <= bitK && inc0 < inc1) ans += inc1, maxX = X1;

if(X1 <= bitK && inc0 >= inc1) ans += inc0, maxX = X0;

if(X1 > bitK) ans += inc0, maxX = X0;

}

// 5. 出力～後処理.

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 117

C++の練習を兼ねて, AtCoder Beginner Contest 117 の 問題C（Streamline) ～ 問題D (XXOR) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 117 の問題C（Streamline) ～問題D (XXOR) を解いてみた.

コメントを残すコメントをキャンセル