3月, 2019 | 個人用メモ帳

2019年3月31日2019年3月31日

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

C++の練習を兼ねて, AtCoder Typical Contest 002 の問題A (A – 幅優先探索) を解いてみた.

■感想.
1. 幅優先探索に慣れるために, コーディングしたが, ACを取れるまで苦労した.
具体的には, 以下のような原因で, 探索イメージと実際の探索状況がズレてしまっていた.
※探索開始地点, 探索終了地点の index が 1ずつズレていた点, 探索距離の更新方法がおかしかった点.

2. 未使用の変数, コメント誤りなどがあったので, 前回の投稿から, 一部差し替えた.

本家のサイトA – 幅優先探索をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
// constexpr int MAX = 400;
constexpr int MAX = 2601;
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int R, C;
int sx, sy, gx, gy;
int board[MAX];
int memo[MAX];

// 幅優先探索.
// https://ja.wikipedia.org/wiki/幅優先探索
// 迷路を幅優先探索する.
// ※bfsの動作確認用.
// @param s: 探索開始地点の迷路上の座標.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        // 4. キューから取り出す.
        int v = q.front();
        q.pop();
        // 5. 取り出した要素を処理.
        // x: 列方向, y: 行方向 で考える.
        int nx, ny, n;
        int cx = v % C , cy = v / C;
        for(int i = 0; i < 4; ++i){
            nx = cx + dx[i];
            ny = cy + dy[i];
            n = nx + ny * C;
            // cout << "cx=" << cx << " nx=" << nx  << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;
            // 6. 訪問不可能なマス であれば, 処理をスキップ.
            if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;
            if(board[n] == '#')                                 continue;
            
            // 7. 訪問先のマスで, 訪問可能 かつ スタート地点でない かつ 未訪問 であれば, 訪問済み(※最短ルート)を設定.
            if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);
        }
    }
    return;
}

int main() {
    
    // 1. 入力情報取得.
    
    cin >> R >> C >> sy >> sx >> gy >> gx;
    sy--, sx--, gy--, gx--;
    for(int i = 0; i < R; ++i){
        string s;
        cin >> s;
        for(int j = 0; j < C; ++j){
            board[i * C + j] = s[j];
        }
    }
    
    // 2. 探索を開始し, 探索距離を更新.
    bfs(sy * C + sx);
    // for(int i = 0; i < R; ++i){
    //     for(int j = 0; j < C; ++j){
    //         cout << memo[i * C + j] << " ";
    //     }
    //     cout << endl;
    // }
    
    // 3. 出力.
    int ans = memo[gy * C + gx];
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

// constexpr int MAX = 400;

constexpr int MAX = 2601;

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int R, C;

int sx, sy, gx, gy;

int board[MAX];

int memo[MAX];

// 幅優先探索.

// https://ja.wikipedia.org/wiki/幅優先探索

// 迷路を幅優先探索する.

// ※bfsの動作確認用.

// @param s: 探索開始地点の迷路上の座標.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

// 3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4. キューから取り出す.

int v = q.front();

q.pop();

// 5. 取り出した要素を処理.

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % C , cy = v / C;

for(int i = 0; i < 4; ++i){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * C;

// cout << "cx=" << cx << " nx=" << nx << " cy=" << cy << " ny=" << ny << " n=" << n << " c=" << c << endl;

// 6. 訪問不可能なマスであれば, 処理をスキップ.

if(n < 0 || nx < 0 || nx >= C || ny < 0 || ny >= R) continue;

if(board[n] == '#') continue;

// 7. 訪問先のマスで, 訪問可能かつスタート地点でないかつ未訪問であれば, 訪問済み(※最短ルート)を設定.

if(board[n] == '.' && n != s && memo[n] == 0) memo[n] = memo[v] + 1, q.push(n);

}

return;

}

int main() {

// 1. 入力情報取得.

cin >> R >> C >> sy >> sx >> gy >> gx;

sy--, sx--, gy--, gx--;

for(int i = 0; i < R; ++i){

string s;

cin >> s;

for(int j = 0; j < C; ++j){

board[i * C + j] = s[j];

}

// 2. 探索を開始し, 探索距離を更新.

bfs(sy * C + sx);

// for(int i = 0; i < R; ++i){

// for(int j = 0; j < C; ++j){

// cout << memo[i * C + j] << " ";

// }

// cout << endl;

// }

// 3. 出力.

int ans = memo[gy * C + gx];

cout << ans << endl;

return 0;

}

[入力例]
7 8
2 2
4 5
########
#......#
#.######
#..#...#
#..##..#
##.....#
########

[出力例(debug版)]
0 0 0 0 0 0 0 0 
0 0 1 2 3 4 5 0 
0 1 0 0 0 0 0 0 
0 2 3 0 11 10 11 0 
0 3 4 0 0 9 10 0 
0 0 5 6 7 8 9 0 
0 0 0 0 0 0 0 0 
11
※AtCoderテストケースより

[入力例]
5 8
2 2
2 4
########
#.#....#
#.###..#
#......#
########

[出力例(debug版)]
0 0 0 0 0 0 0 0 
0 0 0 10 9 8 9 0 
0 1 0 0 0 7 8 0 
0 2 3 4 5 6 7 0 
0 0 0 0 0 0 0 0 
10
※AtCoderテストケースより

[入力例]
16 12
1 1
15 11
..##########
#.##......##
#.##.#.##.##
#....#....##
##.#########
##..########
###.########
###......###
###.####..##
###.##.....#
###.####.#.#
###.##.#.#.#
###.####.#.#
###.###..###
###.#..#...#
###......###

[出力例(debug版)]
0 1 0 0 0 0 0 0 0 0 0 0 
0 2 0 0 9 10 11 12 13 14 0 0 
0 3 0 0 8 0 12 0 0 15 0 0 
0 4 5 6 7 0 13 14 15 16 0 0 
0 0 6 0 0 0 0 0 0 0 0 0 
0 0 7 8 0 0 0 0 0 0 0 0 
0 0 0 9 0 0 0 0 0 0 0 0 
0 0 0 10 11 12 13 14 15 0 0 0 
0 0 0 11 0 0 0 0 16 17 0 0 
0 0 0 12 0 0 19 18 17 18 19 0 
0 0 0 13 0 0 0 0 18 0 20 0 
0 0 0 14 0 0 0 0 19 0 21 0 
0 0 0 15 0 0 0 0 20 0 22 0 
0 0 0 16 0 0 0 22 21 0 0 0 
0 0 0 17 0 21 22 0 22 23 24 0 
0 0 0 18 19 20 21 22 23 0 0 0 
24

[入力例]

7 8

2 2

4 5

########

#......#

#.######

#..#...#

#..##..#

##.....#

########

[出力例(debug版)]

0 0 0 0 0 0 0 0

0 0 1 2 3 4 5 0

0 1 0 0 0 0 0 0

0 2 3 0 11 10 11 0

0 3 4 0 0 9 10 0

0 0 5 6 7 8 9 0

0 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

5 8

2 2

2 4

########

#.#....#

#.###..#

#......#

########

[出力例(debug版)]

0 0 0 0 0 0 0 0

0 0 0 10 9 8 9 0

0 1 0 0 0 7 8 0

0 2 3 4 5 6 7 0

0 0 0 0 0 0 0 0

※AtCoderテストケースより

[入力例]

16 12

1 1

15 11

..##########

#.##......##

#.##.#.##.##

#....#....##

##.#########

##..########

###.########

###......###

###.####..##

###.##.....#

###.####.#.#

###.##.#.#.#

###.####.#.#

###.###..###

###.#..#...#

###......###

[出力例(debug版)]

0 1 0 0 0 0 0 0 0 0 0 0

0 2 0 0 9 10 11 12 13 14 0 0

0 3 0 0 8 0 12 0 0 15 0 0

0 4 5 6 7 0 13 14 15 16 0 0

0 0 6 0 0 0 0 0 0 0 0 0

0 0 7 8 0 0 0 0 0 0 0 0

0 0 0 9 0 0 0 0 0 0 0 0

0 0 0 10 11 12 13 14 15 0 0 0

0 0 0 11 0 0 0 0 16 17 0 0

0 0 0 12 0 0 19 18 17 18 19 0

0 0 0 13 0 0 0 0 18 0 20 0

0 0 0 14 0 0 0 0 19 0 21 0

0 0 0 15 0 0 0 0 20 0 22 0

0 0 0 16 0 0 0 22 21 0 0 0

0 0 0 17 0 21 22 0 22 23 24 0

0 0 0 18 19 20 21 22 23 0 0 0

■参照サイト
AtCoder Typical Contest 002

2019年3月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 090 の問題D (D – Remainder Reminder) を解いてみた.

■感想.
1. 解説の方針と異なっているように見えるが, 計算量を落とすようには書けたと思うので, 及第点取れたと思う.

本家のサイトABC 090/ARC 091 解説をご覧下さい.

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

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

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    
    // 2. (a, b) の 候補 を カウント.
    // ex.
    // b = K + 1: (N + 1) / (K + 1)個
    // b = K + 2: (N + 2) / (K + 2)個, (N + 1) / (K + 2)個
    // b = K + 3: (N + 3) / (K + 3)個, (N + 2) / (K + 3)個, (N + 1) / (K + 3)個
    // ...
    // b = K + i: (N + i) / (K + i)個, (N + i - 1) / (K + i)個, ...,  (N + 1) / (K + i)個
    // ...
    // b = K + (N - K): (2 * N - K) / N個, (2 * N - K - 1) / N個, ...,  (N + 1) / N個 => 計(N - K)通り
    LL ans = 0;
    FOR(b, K + 1, N){
        // 2-1. 上限, 下限 を 計算.
        // ex.
        // b = K + i なら, 
        // 上限: (N + i) / (K + i)個
        // 下限: (N + 1) / (K + i)個
        LL u = (N - K + b) / b, l = (N + 1) / b;
        // cout << "b=" << b << " u=" << u  << " l=" << l << endl;
        
        // 2-2. 各区間について集計.
        // (N - K + b) ～ u * b:       u * ((N - K + b) - u * b + 1)                 =>           ...個(★①)
        // u * b - 1 ～ (u - 1) * b:       (u - 1) * ((u * b - 1) - (u - 1) * b + 1) =>   (u - 1) * b個
        // ...
        // (l + 2) * b - 1 ～ (l + 1) * b: (l + 1) * (((l + 2) * b - 1) - (l + 1) * b + 1) => (l * b)個
        // (l + 1) * b - 1 ～ (N + 1):     l * (((l + 1) * b - 1) - (N + 1) + 1) 個  =>           ...個(★②)
        
        // 下限 ～ 上限 の 場合.
        FOR(v, l, u){
            LL diff = min(N - K + b, (v + 1) * b - 1); // 上限に近い場合に注意(★①).
            diff -= max(N + 1, v * b); // 下限に近い場合に注意(★②).
            ans += v * (diff + 1);
            // cout << "b=" << b << " l=" << l << " u=" << u << " v=" << v << " diff=" << diff << " ans=" << ans << endl;
        }
    }
    
    // 3. 出力 ～ 後処理.
    // K = 0 の 場合は, a = 0 の ケース を 除外する必要がある.
    if(K == 0) ans -= N;
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

// 2. (a, b) の候補をカウント.

// ex.

// b = K + 1: (N + 1) / (K + 1)個

// b = K + 2: (N + 2) / (K + 2)個, (N + 1) / (K + 2)個

// b = K + 3: (N + 3) / (K + 3)個, (N + 2) / (K + 3)個, (N + 1) / (K + 3)個

// ...

// b = K + i: (N + i) / (K + i)個, (N + i - 1) / (K + i)個, ..., (N + 1) / (K + i)個

// ...

// b = K + (N - K): (2 * N - K) / N個, (2 * N - K - 1) / N個, ..., (N + 1) / N個 => 計(N - K)通り

LL ans = 0;

FOR(b, K + 1, N){

// 2-1. 上限, 下限を計算.

// ex.

// b = K + i なら,

// 上限: (N + i) / (K + i)個

// 下限: (N + 1) / (K + i)個

LL u = (N - K + b) / b, l = (N + 1) / b;

// cout << "b=" << b << " u=" << u << " l=" << l << endl;

// 2-2. 各区間について集計.

// (N - K + b) ～ u * b: u * ((N - K + b) - u * b + 1) => ...個(★①)

// u * b - 1 ～ (u - 1) * b: (u - 1) * ((u * b - 1) - (u - 1) * b + 1) => (u - 1) * b個

// ...

// (l + 2) * b - 1 ～ (l + 1) * b: (l + 1) * (((l + 2) * b - 1) - (l + 1) * b + 1) => (l * b)個

// (l + 1) * b - 1 ～ (N + 1): l * (((l + 1) * b - 1) - (N + 1) + 1) 個 => ...個(★②)

// 下限～上限の場合.

FOR(v, l, u){

LL diff = min(N - K + b, (v + 1) * b - 1); // 上限に近い場合に注意(★①).

diff -= max(N + 1, v * b); // 下限に近い場合に注意(★②).

ans += v * (diff + 1);

// cout << "b=" << b << " l=" << l << " u=" << u << " v=" << v << " diff=" << diff << " ans=" << ans << endl;

}

// 3. 出力～後処理.

// K = 0 の場合は, a = 0 のケースを除外する必要がある.

if(K == 0) ans -= N;

cout << ans << endl;

return 0;

}

[入力例]
5 2

[出力例]
7
※AtCoderテストケースより

[入力例]
10 0

[出力例]
100
※AtCoderテストケースより


[入力例]
31415 9265

[出力例]
287927211
※AtCoderテストケースより

[入力例]
100000 12345

[出力例]
5746887726

[入力例]
123456 54321

[出力例]
2444729736

[入力例]
654321 123456

[出力例]
190231592490

[入力例]

5 2

[出力例]

※AtCoderテストケースより

[入力例]

10 0

[出力例]

100

※AtCoderテストケースより

[入力例]

31415 9265

[出力例]

287927211

※AtCoderテストケースより

[入力例]

100000 12345

[出力例]

5746887726

[入力例]

123456 54321

[出力例]

2444729736

[入力例]

654321 123456

[出力例]

190231592490

■参照サイト
AtCoder Beginner Contest 090

2019年3月20日2019年3月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 104 の問題D (D – We Love ABC) を解いてみた.

■感想.
1. 問題D は, DPを使うと思って解答しようとしたが, 方針がまとまらず, 解説を見て, 解き直したものである.
※なお, 問題C は, 難しすぎたので, 正解者のソースを勉強する方針に切り替え, 自力での解答は放棄している.

本家のサイトABC 104 Editorialをご覧下さい.

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

// 解き直し.
// ABC 104 Editorial
// https://img.atcoder.jp/abc104/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 動的計画法(DP)の適用(解説通り).
    LL l = S.size();
    LL dp[l + 1][4] = {};
    dp[l][3] = 1;
    dp[l][2] = 0, dp[l][1] = 0, dp[l][0] = 0;
    for(int i = l - 1; i >= 0; i--){
        char c = S[i];
        for(int j = 3; j >= 0; j--){
            if(j == 3){
                if(c == '?') dp[i][j] = 3 * dp[i + 1][j], dp[i][j] %= MOD;
                else         dp[i][j] = 1 * dp[i + 1][j], dp[i][j] %= MOD;
            }
            if(j < 3){
                if(c == '?'){
                    dp[i][j] = 3 * dp[i + 1][j];
                    dp[i][j] %= MOD;
                    dp[i][j] += 1 * dp[i + 1][j + 1];
                    dp[i][j] %= MOD;
                }else{
                    string ABC = "ABC";
                    dp[i][j] = 1 * dp[i + 1][j];
                    dp[i][j] %= MOD;
                    if(c == ABC.substr(j, 1)[0]) dp[i][j] += 1 * dp[i + 1][j + 1], dp[i][j] %= MOD;
                }
            }
        }
    }

    // 3. 出力 ～ 後処理.
    cout << dp[0][0] << endl;
    return 0;
    
}

// 解き直し.

// ABC 104 Editorial

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. 動的計画法(DP)の適用(解説通り).

LL l = S.size();

LL dp[l + 1][4] = {};

dp[l][3] = 1;

dp[l][2] = 0, dp[l][1] = 0, dp[l][0] = 0;

for(int i = l - 1; i >= 0; i--){

char c = S[i];

for(int j = 3; j >= 0; j--){

if(j == 3){

if(c == '?') dp[i][j] = 3 * dp[i + 1][j], dp[i][j] %= MOD;

else dp[i][j] = 1 * dp[i + 1][j], dp[i][j] %= MOD;

}

if(j < 3){

if(c == '?'){

dp[i][j] = 3 * dp[i + 1][j];

dp[i][j] %= MOD;

dp[i][j] += 1 * dp[i + 1][j + 1];

dp[i][j] %= MOD;

}else{

string ABC = "ABC";

dp[i][j] = 1 * dp[i + 1][j];

dp[i][j] %= MOD;

if(c == ABC.substr(j, 1)[0]) dp[i][j] += 1 * dp[i + 1][j + 1], dp[i][j] %= MOD;

}

// 3. 出力～後処理.

cout << dp[0][0] << endl;

return 0;

}

■参照サイト
AtCoder Beginner Contest 104

2019年3月15日2019年3月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 121 の問題D (D – XOR World) を解いてみた.

■感想.
1. 問題D は, yukicoder の No.524 コインゲームで解答した内容を, 一部改変して対応したものである.
2. なお, yukicoder の No.524 コインゲームを解こうとしたときに, 解答方針が見えなかったので, 石取りゲームと排他的論理和に関する解説サイトがあったため, そのロジックを, プログラムとして再構築したものである.

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

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

// yukicoder(No.524 コインゲーム)
// https://yukicoder.me/submissions/321850
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 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;
}

// 1 ～ N までの排他的論理和の合計を計算.
// @param N: 上限(整数).
// @param pow2: 2 の 冪乗.
// @param D: 桁数.
// @param nXor: 排他的論理和の合計.
// @return: 排他的論理和の合計の更新結果.
void xorSum(LL N, LL pow2[], LL D, LL nXor[]) {
    
    // 0. 1 ～ N までの 排他的論理和 を計算し, その各桁の mod 2 を確認する方針とする.
    // ex. 15 までの排他的論理和の合計.
    // 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
    // -> 8888
    // 
    // ex. 他のケースについての排他的論理和の合計.
    // 19 = 16 + 0 + 0 + 2 + 1
    //    = 18888 + 00000 + 00000 + 20011 + 10011
    //    = 4, 8, 8, 10, 10
    // 27 = 16 + 8 + 0 + 2 + 1
    //    = 18888 + 81444 + 00000 + 22011 + 11011
    //    = 12, 12, 12, 14, 14
    // 29 = 16 + 8 + 1 + 0 + 1
    //    = 18888 + 81444 + 44122 + 00000 + 11101
    //    = 14, 14, 14, 14, 15

    // 1. N の 2進数表現取得.
    LL ret = 0;
    string nStr = decimalToBinary(N, D);

    // 2. N までの 排他的論理和 の 合計 に向けた準備.
    // ex. 29 ならば, nXorStock に, 以下の値を保存.
    // 1 8 8 8 8 
    // 8 1 4 4 4 
    // 4 4 1 2 2 
    // 0 0 0 0 0 
    // 1 1 1 0 1 
    LL nXorStock[D][D];
    for(LL i = 0; i < D; i++){
        int ci = nStr[i] - '0';
        for(LL j = 0; j < D; j++){
            int cj = nStr[j] - '0';
            // cj を 乗ずる必要あり(ex. N = 29 の 1 1 1 0 1 を 作成するパターンなど).
            if(j <  i) nXorStock[i][j] = (pow2[D - 1 - i]) * ci * cj;
            if(j == i) nXorStock[i][j] = 1 * ci;
            if(j >  i) nXorStock[i][j] = (pow2[D - 1 - i] / 2) * ci;
        }
    }
    
    // 3. N までの 排他的論理和 の 合計 を, 各桁ごとに(※mod 2で)取得.
    for(LL i = 0; i < D; i++) nXor[i] = 0;
    for(LL j = 0; j < D; j++) for(LL i = 0; i < D; i++) nXor[j] += nXorStock[i][j], nXor[j] %= 2;

}

int main() {
    
    // 1. 入力情報取得.
    LL A, B;
    cin >> A >> B;
    
    // 2. 2 の べき乗を保存.
    // 2 の 40乗 = 1099511627776 (> 1e12) なので, 40bitで考えてみる.
    const int LIMIT = 40;
    LL pow2[LIMIT];
    pow2[0] = 1;
    for(LL i = 1; i < LIMIT; i++) pow2[i] = 2 * pow2[i - 1];
    
    // 3. A - 1, B の 排他的論理和の合計.
    LL xorA[LIMIT], xorB[LIMIT];
    
    // [入力例]
    // 0 0
    // [出力例]
    // 549755813888
    // -> なぜか, 上記のような, おかしな結果が表示された.
    // -> 上記から, A = 0 は, A-- は行わないようにする必要があるらしい(testcase_19, testcase_20 の WA と推定).
    // A--;
    if(A > 0) A--;
    xorSum(A, pow2, LIMIT, xorA);
    xorSum(B, pow2, LIMIT, xorB);
    // for(int i = 0; i < LIMIT; i++) cout << "xorA[" << i << "]=" << xorA[i] << " xorB[" << i << "]=" << xorB[i] << endl;
    
    // 4. 後処理.
    LL ans = 0;
    for(int i = 0; i < LIMIT; i++) if(xorA[i] != xorB[i]) ans += pow2[LIMIT - 1 - i];
    cout << ans << endl;
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

// yukicoder(No.524 コインゲーム)

// https://yukicoder.me/submissions/321850

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

// 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;

}

// 1 ～ N までの排他的論理和の合計を計算.

// @param N: 上限(整数).

// @param pow2: 2 の冪乗.

// @param D: 桁数.

// @param nXor: 排他的論理和の合計.

// @return: 排他的論理和の合計の更新結果.

void xorSum(LL N, LL pow2[], LL D, LL nXor[]) {

// 0. 1 ～ N までの排他的論理和を計算し, その各桁の mod 2 を確認する方針とする.

// ex. 15 までの排他的論理和の合計.

// 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

// -> 8888

// ex. 他のケースについての排他的論理和の合計.

// 19 = 16 + 0 + 0 + 2 + 1

// = 18888 + 00000 + 00000 + 20011 + 10011

// = 4, 8, 8, 10, 10

// 27 = 16 + 8 + 0 + 2 + 1

// = 18888 + 81444 + 00000 + 22011 + 11011

// = 12, 12, 12, 14, 14

// 29 = 16 + 8 + 1 + 0 + 1

// = 18888 + 81444 + 44122 + 00000 + 11101

// = 14, 14, 14, 14, 15

// 1. N の 2進数表現取得.

LL ret = 0;

string nStr = decimalToBinary(N, D);

// 2. N までの排他的論理和の合計に向けた準備.

// ex. 29 ならば, nXorStock に, 以下の値を保存.

// 1 8 8 8 8

// 8 1 4 4 4

// 4 4 1 2 2

// 0 0 0 0 0

// 1 1 1 0 1

LL nXorStock[D][D];

for(LL i = 0; i < D; i++){

int ci = nStr[i] - '0';

for(LL j = 0; j < D; j++){

int cj = nStr[j] - '0';

// cj を乗ずる必要あり(ex. N = 29 の 1 1 1 0 1 を作成するパターンなど).

if(j < i) nXorStock[i][j] = (pow2[D - 1 - i]) * ci * cj;

if(j == i) nXorStock[i][j] = 1 * ci;

if(j > i) nXorStock[i][j] = (pow2[D - 1 - i] / 2) * ci;

}

// 3. N までの排他的論理和の合計を, 各桁ごとに(※mod 2で)取得.

for(LL i = 0; i < D; i++) nXor[i] = 0;

for(LL j = 0; j < D; j++) for(LL i = 0; i < D; i++) nXor[j] += nXorStock[i][j], nXor[j] %= 2;

}

int main() {

// 1. 入力情報取得.

LL A, B;

cin >> A >> B;

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

// 2 の 40乗 = 1099511627776 (> 1e12) なので, 40bitで考えてみる.

const int LIMIT = 40;

LL pow2[LIMIT];

pow2[0] = 1;

for(LL i = 1; i < LIMIT; i++) pow2[i] = 2 * pow2[i - 1];

// 3. A - 1, B の排他的論理和の合計.

LL xorA[LIMIT], xorB[LIMIT];

// [入力例]

// 0 0

// [出力例]

// 549755813888

// -> なぜか, 上記のような, おかしな結果が表示された.

// -> 上記から, A = 0 は, A-- は行わないようにする必要があるらしい(testcase_19, testcase_20 の WA と推定).

// A--;

if(A > 0) A--;

xorSum(A, pow2, LIMIT, xorA);

xorSum(B, pow2, LIMIT, xorB);

// for(int i = 0; i < LIMIT; i++) cout << "xorA[" << i << "]=" << xorA[i] << " xorB[" << i << "]=" << xorB[i] << endl;

// 4. 後処理.

LL ans = 0;

for(int i = 0; i < LIMIT; i++) if(xorA[i] != xorB[i]) ans += pow2[LIMIT - 1 - i];

cout << ans << endl;

return 0;

}

[入力例]
2 4

[出力例]
5
※AtCoderテストケースより


[入力例]
123 456

[出力例]
435
※AtCoderテストケースより


[入力例]
123456789012 123456789012

[出力例]
123456789012
※AtCoderテストケースより


[入力例]
111111111111 222222222222

[出力例(debug版)]
xorA[0]=0 xorB[0]=0
xorA[1]=0 xorB[1]=0
xorA[2]=0 xorB[2]=1
xorA[3]=1 xorB[3]=1
xorA[4]=1 xorB[4]=0
xorA[5]=0 xorB[5]=0
xorA[6]=0 xorB[6]=1
xorA[7]=1 xorB[7]=1
xorA[8]=1 xorB[8]=1
xorA[9]=1 xorB[9]=0
xorA[10]=0 xorB[10]=1
xorA[11]=1 xorB[11]=1
xorA[12]=1 xorB[12]=1
xorA[13]=1 xorB[13]=1
xorA[14]=1 xorB[14]=0
xorA[15]=0 xorB[15]=1
xorA[16]=1 xorB[16]=0
xorA[17]=0 xorB[17]=1
xorA[18]=1 xorB[18]=1
xorA[19]=1 xorB[19]=1
xorA[20]=1 xorB[20]=1
xorA[21]=1 xorB[21]=0
xorA[22]=0 xorB[22]=1
xorA[23]=1 xorB[23]=0
xorA[24]=0 xorB[24]=0
xorA[25]=0 xorB[25]=0
xorA[26]=0 xorB[26]=0
xorA[27]=0 xorB[27]=0
xorA[28]=0 xorB[28]=0
xorA[29]=0 xorB[29]=0
xorA[30]=0 xorB[30]=1
xorA[31]=1 xorB[31]=1
xorA[32]=1 xorB[32]=1
xorA[33]=1 xorB[33]=0
xorA[34]=0 xorB[34]=0
xorA[35]=0 xorB[35]=0
xorA[36]=0 xorB[36]=1
xorA[37]=1 xorB[37]=1
xorA[38]=1 xorB[38]=1
xorA[39]=1 xorB[39]=1
182062613064


[入力例]
12345654321 1000000000000

[出力例(debug版)]
xorA[0]=0 xorB[0]=1
xorA[1]=0 xorB[1]=1
xorA[2]=0 xorB[2]=1
xorA[3]=0 xorB[3]=0
xorA[4]=0 xorB[4]=1
xorA[5]=0 xorB[5]=0
xorA[6]=1 xorB[6]=0
xorA[7]=0 xorB[7]=0
xorA[8]=1 xorB[8]=1
xorA[9]=1 xorB[9]=1
xorA[10]=0 xorB[10]=0
xorA[11]=1 xorB[11]=1
xorA[12]=1 xorB[12]=0
xorA[13]=1 xorB[13]=1
xorA[14]=1 xorB[14]=0
xorA[15]=1 xorB[15]=0
xorA[16]=1 xorB[16]=1
xorA[17]=1 xorB[17]=0
xorA[18]=0 xorB[18]=1
xorA[19]=1 xorB[19]=0
xorA[20]=1 xorB[20]=0
xorA[21]=0 xorB[21]=1
xorA[22]=1 xorB[22]=0
xorA[23]=1 xorB[23]=1
xorA[24]=1 xorB[24]=0
xorA[25]=0 xorB[25]=0
xorA[26]=1 xorB[26]=0
xorA[27]=1 xorB[27]=1
xorA[28]=1 xorB[28]=0
xorA[29]=1 xorB[29]=0
xorA[30]=0 xorB[30]=0
xorA[31]=0 xorB[31]=0
xorA[32]=0 xorB[32]=0
xorA[33]=0 xorB[33]=0
xorA[34]=1 xorB[34]=0
xorA[35]=1 xorB[35]=0
xorA[36]=0 xorB[36]=0
xorA[37]=0 xorB[37]=0
xorA[38]=0 xorB[38]=0
xorA[39]=0 xorB[39]=0
1005215198256

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

2 4

[出力例]

※AtCoderテストケースより

[入力例]

123 456

[出力例]

435

※AtCoderテストケースより

[入力例]

123456789012 123456789012

[出力例]

123456789012

※AtCoderテストケースより

[入力例]

111111111111 222222222222

[出力例(debug版)]

xorA[0]=0 xorB[0]=0

xorA[1]=0 xorB[1]=0

xorA[2]=0 xorB[2]=1

xorA[3]=1 xorB[3]=1

xorA[4]=1 xorB[4]=0

xorA[5]=0 xorB[5]=0

xorA[6]=0 xorB[6]=1

xorA[7]=1 xorB[7]=1

xorA[8]=1 xorB[8]=1

xorA[9]=1 xorB[9]=0

xorA[10]=0 xorB[10]=1

xorA[11]=1 xorB[11]=1

xorA[12]=1 xorB[12]=1

xorA[13]=1 xorB[13]=1

xorA[14]=1 xorB[14]=0

xorA[15]=0 xorB[15]=1

xorA[16]=1 xorB[16]=0

xorA[17]=0 xorB[17]=1

xorA[18]=1 xorB[18]=1

xorA[19]=1 xorB[19]=1

xorA[20]=1 xorB[20]=1

xorA[21]=1 xorB[21]=0

xorA[22]=0 xorB[22]=1

xorA[23]=1 xorB[23]=0

xorA[24]=0 xorB[24]=0

xorA[25]=0 xorB[25]=0

xorA[26]=0 xorB[26]=0

xorA[27]=0 xorB[27]=0

xorA[28]=0 xorB[28]=0

xorA[29]=0 xorB[29]=0

xorA[30]=0 xorB[30]=1

xorA[31]=1 xorB[31]=1

xorA[32]=1 xorB[32]=1

xorA[33]=1 xorB[33]=0

xorA[34]=0 xorB[34]=0

xorA[35]=0 xorB[35]=0

xorA[36]=0 xorB[36]=1

xorA[37]=1 xorB[37]=1

xorA[38]=1 xorB[38]=1

xorA[39]=1 xorB[39]=1

182062613064

[入力例]

12345654321 1000000000000

[出力例(debug版)]

xorA[0]=0 xorB[0]=1

xorA[1]=0 xorB[1]=1

xorA[2]=0 xorB[2]=1

xorA[3]=0 xorB[3]=0

xorA[4]=0 xorB[4]=1

xorA[5]=0 xorB[5]=0

xorA[6]=1 xorB[6]=0

xorA[7]=0 xorB[7]=0

xorA[8]=1 xorB[8]=1

xorA[9]=1 xorB[9]=1

xorA[10]=0 xorB[10]=0

xorA[11]=1 xorB[11]=1

xorA[12]=1 xorB[12]=0

xorA[13]=1 xorB[13]=1

xorA[14]=1 xorB[14]=0

xorA[15]=1 xorB[15]=0

xorA[16]=1 xorB[16]=1

xorA[17]=1 xorB[17]=0

xorA[18]=0 xorB[18]=1

xorA[19]=1 xorB[19]=0

xorA[20]=1 xorB[20]=0

xorA[21]=0 xorB[21]=1

xorA[22]=1 xorB[22]=0

xorA[23]=1 xorB[23]=1

xorA[24]=1 xorB[24]=0

xorA[25]=0 xorB[25]=0

xorA[26]=1 xorB[26]=0

xorA[27]=1 xorB[27]=1

xorA[28]=1 xorB[28]=0

xorA[29]=1 xorB[29]=0

xorA[30]=0 xorB[30]=0

xorA[31]=0 xorB[31]=0

xorA[32]=0 xorB[32]=0

xorA[33]=0 xorB[33]=0

xorA[34]=1 xorB[34]=0

xorA[35]=1 xorB[35]=0

xorA[36]=0 xorB[36]=0

xorA[37]=0 xorB[37]=0

xorA[38]=0 xorB[38]=0

xorA[39]=0 xorB[39]=0

1005215198256

■参照サイト
AtCoder Beginner Contest 121
No.524 コインゲーム
 ニム（複数山の石取りゲーム）の必勝法

C++の練習を兼ねて, AtCoder Typical Contest 002 の 問題A (A – 幅優先探索) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 090 の 問題D (D – Remainder Reminder) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 104 の 問題D (D – We Love ABC) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 121 の 問題D (D – XOR World) を解いてみた.

C++の練習を兼ねて, AtCoder Typical Contest 002 の問題A (A – 幅優先探索) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 090 の問題D (D – Remainder Reminder) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 104 の問題D (D – We Love ABC) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 121 の問題D (D – XOR World) を解いてみた.