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

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

■感想.
1. 問題Lは, LISを使う方針で実装してみたものの, ACに到達できず, 解説を参考に, 修正版にて, AC版に到達できた.
2. LIS(Longest increase subsequence) の応用版(広義単調増加列プラス追加条件) を, 確認することができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第九回アルゴリズム実技検定の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/past202112-open/editorial/3070
// -> hand_01.txt などで, WA版となったため, 解き直しとした.
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
int a[202020], b[202020];

int main(){
    
    // 1. 入力情報.
    int N, P;
    scanf("%d %d", &N, &P);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 数列 B.
    rep(i, N) b[i] =  a[N - 1 - i] - i;
    
    // 3. "広義"単調増加な数列の長さの最大値は？
    // 以下の問題を参照, 改変.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    rep(i, N){
        // 値が 0 以上 P - (N - 1)以下でない項は, 変更が必要(解説より).
        // 本問では, LIS の 計算過程で, 別途, 下記条件が, 必要なので注意.
        if(b[i] < 0 || b[i] > P - (N - 1)) continue;
        
        // それ以外.
        if(dp.size() == 0 || dp.back() <= b[i]){
            dp.pb(b[i]);
        }else{
            int at = upper_bound(all(dp), b[i]) - dp.begin();
            dp[at] = b[i];
        }
    }
    // rep(i, dp.size()) printf("%d\n", dp[i]);
    
    // 4. 出力.
    printf("%d\n", N - dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/past202112-open/editorial/3070

// -> hand_01.txt などで, WA版となったため, 解き直しとした.

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

#define all(x) x.begin(), x.end()

int a[202020], b[202020];

int main(){

// 1. 入力情報.

int N, P;

scanf("%d %d", &N, &P);

rep(i, N) scanf("%d", &a[i]);

// 2. 数列 B.

rep(i, N) b[i] = a[N - 1 - i] - i;

// 3. "広義"単調増加な数列の長さの最大値は？

// 以下の問題を参照, 改変.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

rep(i, N){

// 値が 0 以上 P - (N - 1)以下でない項は, 変更が必要(解説より).

// 本問では, LIS の計算過程で, 別途, 下記条件が, 必要なので注意.

if(b[i] < 0 || b[i] > P - (N - 1)) continue;

// それ以外.

if(dp.size() == 0 || dp.back() <= b[i]){

dp.pb(b[i]);

}else{

int at = upper_bound(all(dp), b[i]) - dp.begin();

dp[at] = b[i];

}

// rep(i, dp.size()) printf("%d\n", dp[i]);

// 4. 出力.

printf("%d\n", N - dp.size());

return 0;

}

[入力例]
5 10
7 5 10 3 2

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

[入力例]
5 10
9 8 7 7 5

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

[入力例]
11 1000000000
0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

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

[入力例]
3 2
2 1 0

[出力例]
0

[入力例]
15 33
25 16 14 13 12 19 7 22 6 32 5 15 2 21 1

[出力例]
8

[入力例]
31 41
5 9 26 5 35 8 9 7 9 32 38 4 6 26 4 33 8 32 7 9 5 0 2 8 8 41 9 7 16 9 3

[出力例]
26

[入力例]
200 2020
1854 2020 1753 2019 1674 944 2017 1290 1123 2015 1392 1559 1569 2013 1017 1214 1258 2001 2000 1689 1561 1999 1667 1372 1998 1086 1140 1888 1255 1359 1850 1522 1223 1833 1645 1831 982 1799 1409 1219 1759 1357 1730 1024 1217 1700 1351 1699 1487 949 1659 1435 1650 1030 1606 1457 736 1580 809 1110 1560 866 1297 1550 950 971 1400 1185 1310 617 1221 1300 1053 1222 1158 1212 848 1200 610 1111 1100 1020 999 674 987 1017 980 608 774 970 853 1077 966 809 935 955 834 850 943 815 603 767 942 584 513 446 941 417 737 858 910 694 456 901 888 800 869 836 783 454 449 442 490 330 393 616 681 619 364 530 341 680 424 381 522 559 309 325 613 620 512 249 444 228 305 505 384 500 237 489 247 423 468 273 455 396 337 485 430 258 400 150 264 103 333 312 172 300 127 297 285 142 256 166 221 222 221 192 270 189 98 167 32 71 135 54 67 66 122 13 41 111 61 58 77 70 25 12 5 0

[出力例]
130

[入力例]
500 5050
5050 5049 5048 5047 5046 5045 5044 5043 5042 5041 4287 4147 3021 4341 1671 2034 4202 1787 1077 1787 5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 2827 4990 4568 3815 4498 2679 1798 3529 1287 1122 4800 4799 4798 4797 4796 4795 4794 4793 4792 3992 3234 2468 1333 2364 4020 4376 4988 1832 3445 3052 4000 3999 3998 3997 3996 3995 3994 3993 3992 3991 1989 3990 1433 1400 1567 2967 4297 2893 3909 3770 3500 3499 3498 3497 3496 3495 3494 3493 3492 3491 2838 1761 1776 1125 2719 3355 1066 2470 3685 1125 3300 3299 3298 3297 3296 3295 3294 3293 3292 3291 3280 2207 3250 3232 2660 2604 2525 2021 3648 3000 2999 2998 2997 2996 2995 2994 2993 2992 2991 1983 1350 3797 1280 2643 2593 1177 1298 1411 2616 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 1918 1376 2689 3665 1218 3212 1481 3695 1034 2575 2300 2299 2298 2297 2296 2295 2294 2293 2292 2291 1650 1931 1012 1263 1756 1828 1327 1131 1373 1537 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1468 1212 1143 1178 1486 1493 1599 1470 1497 1057 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1926 1848 1043 1764 1028 1292 1451 1198 1844 1664 1700 1699 1698 1697 1696 1695 1694 1693 1692 1691 881 1328 547 646 1324 1118 1422 947 1374 1466 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 733 872 1111 1211 562 1022 653 726 806 1455 1300 1299 1298 1297 1296 1295 1294 1293 1292 1291 730 1498 695 1469 1177 1364 1065 1372 731 580 1200 1199 1198 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 808 1242 1036 1147 1174 797 1255 1222 1147 708 1225 1433 1384 500 1313 1200 1003 1002 1001 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 824 858 881 858 846 887 825 824 857 820 878 838 829 888 838 840 856 827 831 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 746 769 703 790 738 729 757 782 701 776 777 734 753 787 786 791 797 783 741 765 700 725 709 708 741 780 761 709 799 714 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 555 500 548 571 563 566 506 599 550 506 502 570 588 510 594 507 555 537 511 300 299 298 297 296 295 294 293 292 291 238 225 207 288 254 287 212 226 214 226 200 190 180 150 140 100 90 50 30 20 1

[出力例]
200

[入力例]

5 10

7 5 10 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 10

9 8 7 7 5

[出力例]

※AtCoderのテストケースより

[入力例]

11 1000000000

0 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000

[出力例]

※AtCoderのテストケースより

[入力例]

3 2

2 1 0

[出力例]

[入力例]

15 33

25 16 14 13 12 19 7 22 6 32 5 15 2 21 1

[出力例]

[入力例]

31 41

5 9 26 5 35 8 9 7 9 32 38 4 6 26 4 33 8 32 7 9 5 0 2 8 8 41 9 7 16 9 3

[出力例]

[入力例]

200 2020

1854 2020 1753 2019 1674 944 2017 1290 1123 2015 1392 1559 1569 2013 1017 1214 1258 2001 2000 1689 1561 1999 1667 1372 1998 1086 1140 1888 1255 1359 1850 1522 1223 1833 1645 1831 982 1799 1409 1219 1759 1357 1730 1024 1217 1700 1351 1699 1487 949 1659 1435 1650 1030 1606 1457 736 1580 809 1110 1560 866 1297 1550 950 971 1400 1185 1310 617 1221 1300 1053 1222 1158 1212 848 1200 610 1111 1100 1020 999 674 987 1017 980 608 774 970 853 1077 966 809 935 955 834 850 943 815 603 767 942 584 513 446 941 417 737 858 910 694 456 901 888 800 869 836 783 454 449 442 490 330 393 616 681 619 364 530 341 680 424 381 522 559 309 325 613 620 512 249 444 228 305 505 384 500 237 489 247 423 468 273 455 396 337 485 430 258 400 150 264 103 333 312 172 300 127 297 285 142 256 166 221 222 221 192 270 189 98 167 32 71 135 54 67 66 122 13 41 111 61 58 77 70 25 12 5 0

[出力例]

130

[入力例]

500 5050

5050 5049 5048 5047 5046 5045 5044 5043 5042 5041 4287 4147 3021 4341 1671 2034 4202 1787 1077 1787 5000 4999 4998 4997 4996 4995 4994 4993 4992 4991 2827 4990 4568 3815 4498 2679 1798 3529 1287 1122 4800 4799 4798 4797 4796 4795 4794 4793 4792 3992 3234 2468 1333 2364 4020 4376 4988 1832 3445 3052 4000 3999 3998 3997 3996 3995 3994 3993 3992 3991 1989 3990 1433 1400 1567 2967 4297 2893 3909 3770 3500 3499 3498 3497 3496 3495 3494 3493 3492 3491 2838 1761 1776 1125 2719 3355 1066 2470 3685 1125 3300 3299 3298 3297 3296 3295 3294 3293 3292 3291 3280 2207 3250 3232 2660 2604 2525 2021 3648 3000 2999 2998 2997 2996 2995 2994 2993 2992 2991 1983 1350 3797 1280 2643 2593 1177 1298 1411 2616 2500 2499 2498 2497 2496 2495 2494 2493 2492 2491 1918 1376 2689 3665 1218 3212 1481 3695 1034 2575 2300 2299 2298 2297 2296 2295 2294 2293 2292 2291 1650 1931 1012 1263 1756 1828 1327 1131 1373 1537 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1468 1212 1143 1178 1486 1493 1599 1470 1497 1057 1900 1899 1898 1897 1896 1895 1894 1893 1892 1891 1926 1848 1043 1764 1028 1292 1451 1198 1844 1664 1700 1699 1698 1697 1696 1695 1694 1693 1692 1691 881 1328 547 646 1324 1118 1422 947 1374 1466 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 733 872 1111 1211 562 1022 653 726 806 1455 1300 1299 1298 1297 1296 1295 1294 1293 1292 1291 730 1498 695 1469 1177 1364 1065 1372 731 580 1200 1199 1198 1197 1196 1195 1194 1193 1192 1191 1190 1189 1188 1187 1186 1185 1184 1183 1182 1181 1180 1179 808 1242 1036 1147 1174 797 1255 1222 1147 708 1225 1433 1384 500 1313 1200 1003 1002 1001 1000 999 998 997 996 995 994 993 992 991 990 989 988 987 986 985 984 983 982 981 980 979 978 977 976 975 974 973 972 971 824 858 881 858 846 887 825 824 857 820 878 838 829 888 838 840 856 827 831 800 799 798 797 796 795 794 793 792 791 790 789 788 787 786 785 784 783 782 781 780 779 778 777 776 775 774 773 772 771 746 769 703 790 738 729 757 782 701 776 777 734 753 787 786 791 797 783 741 765 700 725 709 708 741 780 761 709 799 714 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 555 500 548 571 563 566 506 599 550 506 502 570 588 510 594 507 555 537 511 300 299 298 297 296 295 294 293 292 291 238 225 207 288 254 287 212 226 214 226 200 190 180 150 140 100 90 50 30 20 1

[出力例]

200

■参照サイト
第九回アルゴリズム実技検定

C++の練習を兼ねて, 第九回 アルゴリズム実技検定 の 問題L (嘘つきな生徒たち) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, 第九回アルゴリズム実技検定の問題L (嘘つきな生徒たち) を解いてみた.

コメントを残すコメントをキャンセル