C++の練習を兼ねて, AtCoder Beginner Contest 121 の 問題D (D – XOR World) を解いてみた.
■感想.
1. 問題D は, yukicoder の No.524 コインゲーム で解答した内容を, 一部改変して対応したものである.
2. なお, yukicoder の No.524 コインゲーム を解こうとしたときに, 解答方針が見えなかったので, 石取りゲームと排他的論理和に関する解説サイトがあったため, そのロジックを, プログラムとして再構築したものである.
本家のサイトABC 121 解説をご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
[入力例] 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 |
■参照サイト
AtCoder Beginner Contest 121
No.524 コインゲーム
ニム（複数山の石取りゲーム）の必勝法