競技プログラミングにおける計算量削減の例【蟻とニブタンの物語】

はじめに

• 競技プログラミングには、教科書的な本があり、競技プログラミングに真面目に取り組んでる人なら、多分みんなも買って読んでるだろうけど、まだ片足を突っ込み始めた人だと知らない人も居るだろうから、とりあえず本の冒頭の問題を紹介する。
• N枚の数値が書かれたカードがあり、そのカードを4回引いたとき（同じカードを繰り返し引くことも可能）、合計数値がMとなり得るか？という問題。答えは、「Yes」「No」のどちらか。
• 全探索を使っても解けるけど、全探索の計算量は$O(n^4)$であり、nが1000くらいでも、AtCoderなどの競プロで制限となる計算量$10^8$を超えてしまう。よって、全探索以外の解き方も示す。
• コードはswiftで書くよ。
• 入力は、下記の形とする。下記の場合、2 2 3 3のカードを引いて10となるから、「Yes」

6 10 // N と M
2 7 3 14 4 4 // カードに書かれた数値

全探索の場合

• これは、簡単。for文を4重で行えば、4枚のカードの全探索ができる。

var (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)!} // valueの配列だからvsにした

var ans = "No"

OUT:for i in 0..<N {
    for j in 0..<N {
        for k in 0..<N {
            for l in 0..<N {
                if vs[i] + vs[j] + vs[k] + vs[l] == M {
                    ans = "Yes"
                    // print(vs[i],vs[j],vs[k],vs[l]) //答えの確認用
                    break OUT
                } 
            }
        }
    }
}

print(ans)

• 全探索は、簡単にコード化できるけど、計算量が多くなる場合は回避策が必要。
• 例えば、入力を下記のようにすると、paiza.ioではtimeout(2.00sec)となる。実際の答えはYesで、組み合わせは200 200 200 200になる。計算量は$1.6×10^9$となり、競プロ等で計算可能な上限の目安となる$10^8$を超えている。

200 800
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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 

二分探索（ニブタン）の紹介

• ここで、唐突ですが、ニブタンのご紹介です。
• 昇順となっている配列の中に、ある要素が含まれているかどうかを調べる方法の一つで、全探索（計算量O(N)）より早く(計算量O(logN))、検索できます。
• 例えば、１４個の昇順の配列があったとして、その中に値３６が含まれているかを調べる場合、下図のよう手順で探します。検索範囲の中間点の要素の値と検索値を比較して、要素の値の方が小さいときは、配列の右半分を新しい検索範囲として、同じことを繰り返す方法です。
  
• 計算量について言えば、Ｎ=1000のとき、全探索の計算量1000に対し、ニブタンの計算量はlogN=3となり、かなり減少する。(厳密に言えば、logの底を2として計算するべきなので、下記公式に基づき、10を底とした対数に3.322(=1/log2)を乗じた数値、9.965とN=1000を比べるべきだけどね。実感として、1000個の昇順配列からたった3回で検索が終わると思えないけど、9.965回なら終わりそうな気もするでしょ？)
  
• ニブタンのアルゴリズムを具体的に書くにはどうすれば良いか？を口で説明するより、コードで直接見た方が分かり易いと思う。もちろん、wikiでざっと読んでも良いけどね。

// 全探索
func zen(_ vs:[Int],_ num:Int)->Bool{
    for v in vs {
        if num == v{return true}
    }
    return false
}

//二分探索(ニブタン)
func nib(_ vs_org:[Int],_ num:Int)->Bool{

    var vs = vs_org
    vs.sort() //　昇順並び替え(計算量:NlogN)

    var l = 0 // 探索範囲の左端のindex
    var r = vs.count - 1 // 探索範囲の右端のindex
    
    while(true) {
    
        let i = ( l + r ) / 2 // 探索範囲の中間地点
    
        if vs[i] == num {
            return true // 発見 
        } else if vs[i] > num { // インデックスiの要素の値が検索値numより大きいとき
            r = i - 1 //　探索範囲の右端をインデックスiの左隣とする
        } else { 
            l = i + 1  //　探索範囲の左端をインデックスiの右隣とする
        }
        
        if ( l > r ) {return false} // 発見できないまま、捜索範囲の左右が逆転
    }

}


let vs = (0...(50000000)).map{$0}
let n = 43214321

print(n) // nを表示するだけ

print(zen(vs,n)) // 全探索

print(nib(vs,n)) //　ニブタン

• で、全探索とニブタンを実行するプログラムを書いてみたけど、実はこれ、ニブタンの方のみタイムアウトします。
• え？ニブタンの方が計算量が小さいはずじゃん！と思うだろうけど、実はニブタンは、検索対象の配列を予め昇順に並び替えておく、という条件があり、この並び替えの計算量が$NlogN$になってんだよね。log50000000は7.7だから、計算量が$3.5×10^8$になってタイムアウトになったっぽいね。全探索の方は、$5×10^7$だから、余裕があるのにね。
• だから、ニブタン(計算量logN)を考えるときは、並び替え(NlogN)も考慮する必要があり、また、ニブタンの関数を作るとき、関数内で並び替えを入れるのは、高速化の観点で非効率なので、引数として渡す時点で、並び替え済みである前提とすべき。

//二分探索(ニブタン)
func nib(_ vs:[Int],_ num:Int)->Bool{ // vsは昇順とする

    var l = 0 // 探索範囲の左端のindex
    var r = vs.count - 1 // 探索範囲の右端のindex
    
    while(true) {
    
        let i = ( l + r ) / 2 // 探索範囲の中間地点
    
        if vs[i] == num {
            return true // 発見 
        } else if vs[i] > num { // インデックスiの要素の値が検索値numより大きいとき
            r = i - 1 //　探索範囲の右端をインデックスiの左隣とする
        } else { 
            l = i + 1  //　探索範囲の左端をインデックスiの右隣とする
        }
        
        if ( l > r ) {return false} // 発見できないまま、捜索範囲の左右が逆転
    }

}

-　修正後の上記ニブタン関数と、全探索での実行時間をAtCoderのコードテストで比較すると、全探索が240msec、ニブタンが207msecだから、それほど差がないように見えるけど、print(n)だけでも205msecだったので、実際は、全探索35msec、ニブタン2msecってことだからかなり早くなってるね。つか、配列生成let vs = (0...(50000000)).map{$0}が一番時間かかってんじゃんね。

４枚カード問題をニブタンで高速化

• 到達目標を、カード総数1000枚とする。これを全探索で行うと、前述の通り時間切れになるけど、前述のニブタンを使って、なんとか計算量を$10^8$以内に抑える。
• まず、４枚カード問題を２枚カード問題にする。なんのこっちゃと思うだろうけど、カード総数1000枚から２枚抜き出したときの合計値を書いた新たなカード(カード総数1000000)の２枚の合計値がMになるかどうかを調べると言うこと。
• ただし、このカード総数1000000について、２枚の組み合わせを全探索すると、結局計算量は同じになってしまい、意味がない。
• では、どうするかというと、1000000枚のカード(配列名をvvsとする)から、１枚引いたときの値をvvs[i]としたとき、vvsの中に(M-vvs[i])となるカードがあるかどうかをニブタンで探す、ということにする。
• このとき、１000000枚の並び替えの計算量(NlogN)は$10^6×3.322×6 = 2.0×10^7$なので、$10^8$に収まっているため、並び替えは問題なく出来る。
• また、1000000回のニブタン(計算量$log1000000$)も、並び替えと同じ計算量であるため、問題なく実行できる。
• 計算量が問題ないことが確認できたので、安心してコードを書いていけるね。

var (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let vs = readLine()!.split(separator:" ").map{Int($0)!} // valueの配列だからvsにした

var ans = "No"

// 新カード作成 O(N^2)
var vvs:[Int] = []
for i in 0..<N {
    for j in 0..<N {
        vvs.append(vs[i]+vs[j])
    }
}

// 新カードを昇順に並び替え O(N^2xlog(N^2))
vvs.sorted() 

// ニブタン
for i in 0..<(N*N) {
    if nib(vvs,M-vvs[i]) {
        ans = "Yes"
        break
    }
}

print(ans)


//二分探索(ニブタン)
func nib(_ vs:[Int],_ num:Int)->Bool{ // vsは昇順とする

    var l = 0 // 探索範囲の左端のindex
    var r = vs.count - 1 // 探索範囲の右端のindex
    
    while(true) {
    
        let i = ( l + r ) / 2 // 探索範囲の中間地点
    
        if vs[i] == num {
            return true // 発見 
        } else if vs[i] > num { // インデックスiの要素の値が検索値numより大きいとき
            r = i - 1 //　探索範囲の右端をインデックスiの左隣とする
        } else { 
            l = i + 1  //　探索範囲の左端をインデックスiの右隣とする
        }
        
        if ( l > r ) {return false} // 発見できないまま、捜索範囲の左右が逆転
    }
}

• 入力値は下記の通り。カードの値の配列は、(1...1000).shuffled().map{print($0,terminator:" ")}で作成したから、最大値は1000なので、答えはNoとなる。実行時間はAtCoderのコードテストで114msec。

1000 4001
58 655 649 704 561 559 147 155 886 626 12 210 720 243 795 611 507 664 463 751 67 359 224 59 350 992 786 271 995 766 188 278 107 670 828 836 122 113 323 253 555 268 711 417 732 478 398 290 174 135 653 907 274 428 453 449 445 1 848 812 702 690 726 587 532 899 636 149 953 753 214 348 816 446 834 472 289 406 600 538 125 689 139 316 184 897 820 361 158 431 990 614 491 755 584 349 181 335 86 660 451 712 700 547 443 825 698 721 10 277 981 14 661 433 466 22 427 957 517 525 671 222 131 634 473 799 418 146 772 365 627 60 959 962 740 442 470 176 286 496 853 171 965 573 159 685 368 160 117 518 715 967 793 325 882 437 991 618 603 976 495 552 424 297 439 719 777 730 327 166 921 172 124 709 457 377 841 512 568 554 972 678 251 937 607 482 693 635 985 877 145 434 945 231 329 840 905 32 114 301 40 910 239 855 308 357 523 680 713 734 392 593 804 487 126 162 448 341 993 273 557 296 798 722 373 191 347 379 494 240 485 622 412 245 876 724 105 326 25 658 919 728 737 930 832 488 196 6 69 369 230 994 501 218 677 263 602 17 574 599 754 773 152 279 955 819 928 911 823 45 136 504 345 986 484 262 72 871 503 515 628 662 21 163 787 411 300 120 200 872 88 63 581 346 351 339 569 499 211 983 309 226 175 642 878 101 817 464 583 511 785 203 64 386 864 179 13 566 839 516 572 441 830 241 974 420 932 111 98 952 806 358 813 276 388 576 790 904 133 303 979 560 209 294 915 900 534 238 608 895 54 520 367 544 1000 666 20 261 944 556 170 66 269 922 256 42 187 887 109 475 697 219 74 118 801 311 189 686 542 815 130 270 938 7 397 947 34 298 964 875 123 917 927 396 330 248 374 403 948 387 780 571 673 372 315 543 62 550 710 829 647 746 984 51 116 37 861 646 213 223 169 53 382 617 892 236 78 334 597 142 935 399 121 381 865 291 371 128 401 220 717 199 85 893 148 579 580 735 235 134 643 884 39 918 57 259 440 353 956 221 837 808 321 383 458 70 30 733 500 207 217 255 344 609 2 285 862 138 890 846 942 180 250 805 940 49 885 254 901 44 469 249 455 914 234 860 110 973 103 883 950 393 76 195 165 505 763 194 43 112 563 595 267 803 744 41 447 665 669 833 764 409 185 15 304 137 546 925 140 94 154 476 4 247 585 564 565 776 331 87 529 588 966 936 183 699 768 375 596 558 535 390 306 869 35 648 193 205 968 977 920 789 989 9 75 233 619 16 521 400 405 975 562 468 227 459 668 612 541 299 435 272 970 460 157 706 835 682 429 394 508 629 356 916 933 366 767 996 19 536 47 354 531 82 999 264 432 190 807 452 961 3 524 305 650 509 703 586 108 29 654 606 741 896 527 422 258 708 958 889 275 246 827 99 31 355 997 257 630 778 638 208 742 456 879 320 888 229 24 850 545 48 605 934 674 84 696 692 931 8 729 675 842 796 100 360 314 659 672 71 783 352 489 791 707 854 694 423 610 77 926 283 150 881 430 857 687 868 96 90 265 92 818 870 797 462 333 794 177 782 73 769 438 738 465 404 645 676 771 380 471 640 167 765 858 526 939 287 615 426 281 395 946 215 378 144 800 307 811 454 242 631 601 714 319 859 363 61 598 701 591 80 604 644 679 856 528 56 497 391 186 873 364 705 969 756 762 502 843 93 106 444 760 206 280 212 553 415 912 903 342 688 681 492 736 826 838 748 625 652 102 750 577 866 173 33 28 651 691 481 847 129 831 570 336 874 317 548 549 784 821 998 416 540 338 55 225 340 376 849 902 695 788 318 324 97 18 204 747 909 83 894 50 295 52 389 639 539 5 284 322 727 202 656 781 980 590 483 620 127 151 332 667 293 802 410 852 908 624 657 201 749 198 758 623 343 775 421 978 402 104 310 292 929 684 26 479 683 23 419 474 589 408 752 880 513 663 252 582 11 954 328 312 779 156 759 68 486 774 824 743 153 770 414 506 141 216 192 982 949 718 436 924 36 745 119 182 91 461 533 814 38 132 115 27 731 891 370 578 641 519 923 567 46 522 498 232 510 809 716 95 613 792 863 810 845 906 244 79 282 178 723 407 81 960 851 761 941 89 168 450 490 739 575 616 467 337 988 943 161 384 621 514 867 197 477 143 362 530 425 844 65 385 313 164 266 963 594 633 632 725 260 822 237 551 987 913 637 413 757 537 898 592 493 288 228 971 480 302 951

• 入力値の4001(実行時間114msec)を3456に変えると、当然答えはYesになるけど、実行時間は74msecとなり、半分くらいになった。まあ、Yesの場合はニブタンチェックループを途中で抜けることが出来るから、答えがNoの時より短くなるのは想定通り。

最後に

• なお、ニブタンは、配列内の要素検索の高速化手法としてはメジャーすぎるくらいだけど、まず、最初に昇順化した配列が必要であり、昇順化の計算量が、全探索での計算量を超えてしまうという特徴があるため、おそらくどの言語でも、配列と検索値だけでニブタンしてくれる関数は存在しないと思われる。
• 今回、蟻本を初めて読んで、最初のページの問題を解いてみたけど、やっぱり蟻本は教科書的に全ての問題を解くべきなんだろうね。
• 今は、APG4bでのc++の勉強を先にやってるけど、早く蟻本にも取りかからないとね。