C++の練習を兼ねて, AtCoder Regular Contest 098 の 問題D (D – Xor Sum 2) を解いてみた.
■感想.
1. 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. 尺取り法 の 訓練 が 出来たので良かったと思う.
3. 条件を満たす整数の組(l, r) が 見つかった毎に, (r – l + 1) を 加算する必要があることに気付けたのが, 良かったと思う.
本家のサイトAtcoderRegularContest解説をご覧下さい.
■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 |
// 解き直し. // AtcoderRegularContest解説 // https://img.atcoder.jp/arc098/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; LL A[200002], CUM[200002], XOR[200002]; int main(){ // 1. 入力情報取得. int N; scanf("%d", &N); for(int i = 1; i <= N; i++){ scanf("%lld", &A[i]); CUM[i] = CUM[i - 1] + A[i]; XOR[i] = XOR[i - 1] ^ A[i]; } // 2. 解説通り. // 条件を満たす 整数の組(l, r) の 個数 を計算(※尺取り法っぽいロジックを使えるとのこと). LL ans = 0; int l = 1, r = 1; int counter = 0; while(l <= N){ while(r <= N){ // 2-1. 整数の組(l, r) に 対応する和, 排他的論理和を取得. LL Add = CUM[r] - CUM[l - 1]; LL Xor = XOR[r] ^ XOR[l - 1]; // 変数名: xor だと, Compile error となった. // 2-2. 条件を満たすか確認. if(Add == Xor) ans += (r - l + 1); else break; // 2-3. r を increment. r++; // 2-4. debug用. counter++; if(counter > 200002) break; } // 2-5. l を increment. l++; } // 3. 出力 ～ 後処理. printf("%lld\n", ans); 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 |
[入力例] 4 2 5 4 6 [出力例] 5 ※AtCoderテストケースより [入力例] 9 0 0 0 0 0 0 0 0 0 [出力例] 45 ※AtCoderテストケースより [入力例] 19 885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1 [出力例] 37 ※AtCoderテストケースより [入力例] 300 271 208 520 930 131 375 957 254 643 153 354 646 801 37 233 597 490 859 519 780 924 504 718 996 843 98 723 948 515 994 409 23 936 868 113 916 257 997 279 453 396 955 441 705 974 231 735 279 150 747 183 669 234 787 304 800 558 327 379 505 715 394 333 86 894 188 637 2 584 726 527 128 836 713 648 361 906 338 250 343 62 148 662 901 166 440 963 534 505 88 307 127 98 261 623 914 794 905 45 182 442 711 205 964 40 779 125 531 273 58 96 396 333 845 551 198 231 858 332 515 17 21 607 837 706 953 715 613 796 725 212 857 926 85 395 812 954 684 924 801 351 711 315 618 209 384 648 492 260 500 305 150 60 848 834 269 603 760 915 732 652 368 313 86 150 8 37 282 237 942 242 866 362 597 859 315 474 192 998 897 882 969 480 638 336 202 960 52 101 16 862 883 523 701 826 119 682 488 344 73 937 306 403 692 982 654 265 684 664 490 640 88 476 650 943 997 190 87 275 437 47 452 791 900 97 1 230 900 571 288 202 833 679 106 493 741 733 452 980 455 497 846 57 488 645 413 826 291 766 680 555 758 596 36 622 623 271 902 233 414 889 815 246 169 197 945 436 342 68 896 742 322 720 345 439 656 377 714 995 291 381 944 522 426 285 980 454 241 521 449 854 595 710 103 554 634 76 760 451 526 [出力例] 323 |
■参照サイト
AtCoder Regular Contest 098