C++の練習を兼ねて, AtCoder Beginner Contest 126 の 問題F (F – XOR Matching) を解いてみた.
■感想.
1. 紙に書いて試行錯誤していたら, 規則性を抽出出来たので, 何とか正答に辿り着けた.
2. 相変わらず苦手な DP の訓練となったと思う.
3. とりあえず, 解説見る前に解けたので, 及第点は, 取れたように思う.
本家のサイトABC 126解説をご覧下さい.
■C++版プログラム(問題F／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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; LL dp[262262]; // 2 の 18乗 = 262144 より大きければ良いはず. int main(){ // 1. 入力情報取得. int M; LL K; scanf("%d %lld", &M, &K); // 2. 数列作成(K >= 2 の M乗). int l = 1 << M; // 数列の長さ. // sample_02 で, WA となったので, if文 を 修正. // if(K >= l){ if(K >= l || (M == 1 && K == 1)){ printf("%d\n", -1); return 0; } // 3. 数列作成(K < 2 の M乗). int base = l - 1, counter = 0; // 3-1. K == 0 // ex. // M = 2, K = 0 // 0 0 -> 1 0 0 1 -> 2 1 0 0 1 2 -> 3 2 1 0 0 1 2 3 とすれば良さそう. if(K == 0){ dp[base] = K, dp[base + 1] = K; for(int i = 0; i < l; i++) if(i != K) counter++, dp[base - counter] = dp[base + 1 + counter] = i; } // 3-2. K > 0 // M = 2, K = 1 // 1 -> 0 1 0 -> 2 0 1 0 2 -> 3 2 0 1 0 2 3 -> 3 2 0 1 0 2 3 1 とすれば良さそう. // // M = 2, K = 2 // 2 -> 0 2 0 -> 1 0 2 0 1 -> 3 1 0 2 0 1 3 -> 3 1 0 2 0 1 3 2 とすれば良さそう. // // M = 2, K = 3 // 3 -> 0 3 0 -> 1 0 3 0 1 -> 2 1 0 3 0 1 2 -> 2 1 0 3 0 1 2 3 とすれば良さそう. if(K > 0){ dp[base] = K, dp[2 * base + 1] = K; for(int i = 0; i < l; i++) if(i != K) counter++, dp[base - counter] = dp[base + counter] = i; } // 4. 後処理. for(int i = 0; i < 2 * l; i++) printf("%lld ", dp[i]); 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 |
[入力例] 1 0 [出力例] 1 0 0 1 ※AtCoderテストケースより [入力例] 1 1 [出力例] -1 ※AtCoderテストケースより [入力例] 5 58 [出力例] -1 ※AtCoderテストケースより [入力例] 3 7 [出力例] 6 5 4 3 2 1 0 7 0 1 2 3 4 5 6 7 [入力例] 3 8 [出力例] -1 [入力例] 5 1 [出力例] 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 0 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 1 [入力例] 7 111 [出力例] 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 111 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 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 111 |
■参照サイト
AtCoder Beginner Contest 126