C++の練習を兼ねて, 競プロ典型 90 問 の 問題087 (Chokudai’s Demand) を解いてみた.
■感想.
1. 問題087は, 方針が見えなかったので, (問題087 (Chokudai’s Demand) 解説) などを参考に実装したところ, AC版に到達出来た.
2. 二分探索, ワーシャル–フロイド法 の 復習が出来たので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.
詳細は, 本家のサイト(GitHub) 競プロ典型 90 問 の 問題087 を ご覧下さい.
■C++版プログラム(問題087／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 |
// 解き直し. // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/087-01.jpg // https://github.com/E869120/kyopro_educational_90/blob/main/editorial/087-02.jpg // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) const LL INF = 202020202020202020; LL o[44][44]; // 交通費(入力情報). int main(){ // 1. 入力情報. int N, K; LL P; scanf("%d %lld %d", &N, &P, &K); rep(i, N) rep(j, N) scanf("%lld", &o[i][j]); // 2. 判定関数. auto f = [&](LL X, char c) -> bool{ // 2-1. 初期化. LL a[N][N]; int cnt = 0; rep(i, N) rep(j, N) a[i][j] = (o[i][j] == -1) ? X : o[i][j]; // 2-2. Warshall–Floyd法(※各頂点間の最短距離を保存). rep(k, N) rep(i, N) rep(j, N) a[i][j] = min(a[i][j], a[i][k] + a[k][j]); // 2-3. Pヌーク以下の個数をカウント. rep(i, N) repx(j, i + 1, N) if(a[i][j] <= P) cnt++; // 2-4. 判定結果. return (c == 'L') ? (cnt <= K) : (cnt < K); }; // 3. 左端を, 二分探索で確認してみる. LL l = 0, h = INF, m, L = 0, R = 0; while(l + 1 < h){ m = (h + l) >> 1; if(f(m, 'L')) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } L = h; // 4. 右端を, 二分探索で確認してみる. l = 0, h = INF; while(l + 1 < h){ m = (h + l) >> 1; if(f(m, 'R')) h = m; else l = m; // printf("h=%lld l=%lld m=%lld\n", h, l, m); } R = h; // 5. 出力. // -> R のみ INF の 場合は, Infinity と見る. if(L != INF && R == INF) puts("Infinity"); else printf("%lld\n", R - L); 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 |
[入力例] 3 4 2 0 3 -1 3 0 5 -1 5 0 [出力例] 3 ※AtCoderテストケースより [入力例] 3 10 2 0 -1 10 -1 0 1 10 1 0 [出力例] Infinity ※AtCoderテストケースより [入力例] 13 777 77 0 425 886 764 736 -1 692 660 -1 316 424 490 423 425 0 -1 473 -1 311 -1 -1 903 941 386 521 486 886 -1 0 605 519 473 775 467 677 769 690 483 501 764 473 605 0 424 454 474 408 421 530 756 568 685 736 -1 519 424 0 -1 804 598 911 731 837 459 610 -1 311 473 454 -1 0 479 613 880 -1 393 875 334 692 -1 775 474 804 479 0 579 -1 -1 575 985 603 660 -1 467 408 598 613 579 0 456 378 887 -1 372 -1 903 677 421 911 880 -1 456 0 859 701 476 370 316 941 769 530 731 -1 -1 378 859 0 800 870 740 424 386 690 756 837 393 575 887 701 800 0 -1 304 490 521 483 568 459 875 985 -1 476 870 -1 0 716 423 486 501 685 610 334 603 372 370 740 304 716 0 [出力例] 42 ※AtCoderテストケースより [入力例] 4 5 4 0 5 -1 7 5 0 6 -1 -1 6 0 3 7 -1 3 0 [出力例] 3 [入力例] 10 666 43 0 540 1208 443 -1 1062 221 926 824 572 540 0 348 614 997 557 -1 738 637 8 1208 348 0 -1 1188 -1 1076 672 208 325 443 614 -1 0 226 443 -1 1049 -1 847 -1 997 1188 226 0 777 307 -1 816 802 1062 557 -1 443 777 0 718 130 676 341 221 -1 1076 -1 307 718 0 76 552 645 926 738 672 1049 -1 130 76 0 469 615 824 637 208 -1 816 676 552 469 0 780 572 8 325 847 802 341 645 615 780 0 [出力例] 112 |
■参照サイト
087 – Chokudai’s Demand
問題087 (Chokudai’s Demand) 解説(その１)
問題087 (Chokudai’s Demand) 解説(その２)
