競技プログラミングの鉄則

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, L, R;
    cin >> N >> L >> R;

    vll X(N);
    rep(i, N) cin >> X[i];

    auto op = [](ll a, ll b) -> ll {
        return min(a, b);
    };

    auto e = []() -> ll {
        return INF;
    };

    segtree<ll, op, e> seg(N);
    seg.set(0, 0);

    rep2(i, 1, N) {
        ll x = X[i];
        ll l = x - R;
        ll r = x - L;
        auto lit = lower_bound(all(X), l);
        auto rit = upper_bound(all(X), r);
        if (lit == rit) continue;
        ll mi = seg.prod(lit - X.begin(), rit - X.begin());
        seg.set(i, mi + 1);
    }

    cout << seg.get(N - 1) << endl;
}

B59. Number of Inversions

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_eb

B61. Influencer

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ec

B62. Print a Path

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ed

B63. 幅優先探索

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ee

B64. Shortest Path with Restoration

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ef

B65. Road to Promotion Hard

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_eg

B66. Typhoon

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_eh

B67. Max MST

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ei

B68. ALGO Express

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ej

B69. Black Company 2

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ek

C01. Tax Rate

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_di

C02. Two Balls

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fa

C03. Stock Queries

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fb

C04. Divisor Enumeration

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fc

C05. Lucky Numbers

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fd

C06. Regular Graph

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fe

C07. ALGO-MARKET

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ff

C08. ALGO4

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fg

C09. Taro’s Vacation

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fh

C10. A Long Grid

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fi

C11. Election

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fj

C12. Taro the Novel Writer

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fk

C13. Select 2

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fl

C14. Commute Route

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fm

C15. Many Meetings

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fn

C16. Flights

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fo

C17. Strange Data Structure?

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fp

C18. Pick Two（★6）

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fq

C19. Gasoline Optimization Problem

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fr

2026/2/17 segment tree の問題だとわかった状態で自力 AC

https://kenkoooo.com/atcoder/#/contest/show/76c42792-10db-491b-9486-ffc7f4f226e1?activeTab=Standings

$i-1$ から $i$ への移動で使ったガソリンはどの時点でガソリンスタンドで購入したガソリンかを考えると $i-K$ から $i-1$ までの区間にあるガソリンスタンドのうち、最も安いガソリンスタンドで購入したガソリンを使うのが最適であることがわかる。また一つのガソリンスタンドで補充できるガソリンは $K$ まで使えるので、同じ位置にガソリンスタンドがある場合は最安値のところを使えばよい。 segment tree を使って、区間 $[i-K, i-1]$ にあるガソリンスタンドのうち最安値のガソリンを使って $i-1$ から $i$ への移動をすることを繰り返せば、最終的に $L$ に到達するまでの最小コストを求めることができる。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, L, K;
    cin >> N >> L >> K;
    L++;

    auto op = [](ll a, ll b) -> ll {
        return min(a, b);
    };
    auto e = []() -> ll {
        return INF;
    };

    segtree<ll, op, e> seg(L);
    seg.set(0, 0);

    rep(i, N) {
        ll a, c;
        cin >> a >> c;
        ll t = seg.get(a);
        seg.set(a, min(t, c));
    }

    vll cost(L, INF);
    cost[0] = 0;
    rep2(i, 1, L) {
        ll l = max(0ll, i - K);
        cost[i] = seg.prod(l, i);
    }

    ll ans;
    if (*max_element(all(cost)) == INF)
        ans = -1;
    else
        ans = accumulate(all(cost), 0ll);
    cout << ans << endl;
}

C20. Mayor’s Challenge

https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_fs

競技プログラミングの鉄則

Table of Contents

A01. The First Problem

A02. Linear Search

A03. Two Cards

A04. Binary Representation 1

A05. Three Cards

A06. How Many Guests?

A07. Event Attendance

A08. Two Dimensional Sum

A09. Winter in ALGO Kingdom

A10. Resort Hotel

A11. Binary Search 1

A12. Printer

A13. Close Pairs

A14. Four Boxes

A15. Compression

A16. Dungeon 1（※初版第 1 刷の B22 も同じ問題です）

A17. Dungeon 2

A18. Subset Sum

A19. Knapsack 1

A20. LCS

A21. Block Game

A22. Sugoroku

A23. All Free

A24. LIS

A25. Number of Routes

A26. Prime Check

A27. Calculate GCD

A28. Blackboard

A29. Power

A30. Combination

A31. Divisors

A32. Game 1

A33. Game 2

A34. Game 3

A35. Game 4

A36. Travel

A37. Travel 2

A38. Black Company 1

A39. Interval Scheduling Problem

A40. Triangle

A41. Tile Coloring

A42. Soccer

A43. Travel 3

A44. Change and Reverse

A45. Card Elimination

A46. Heuristic 1

A49. Heuristic 2

A50. 山型足し算

A51. Stack

A52. Queue

A53. Priority Queue

A54. Map

A55. Set

A56. String Hash

A57. Doubling

A58. RMQ (Range Maximum Queries)

A59. RSQ (Range Sum Queries)

A60. Stock Price

A61. Adjacent Vertices

A62. Depth First Search

A63. Shortest Path 1

A64. Shortest Path 2

A65. Road to Promotion

A66. Connect Query

A67. MST (Minimum Spanning Tree)

A68. Maximum Flow

A69. Bipartite Matching

A70. Lanterns

A71. Homework

A72. Tile Painting

A73. Marathon Route

A74. Board Game

A75. Examination

A76. River Crossing

A77. Yokan Party（★4）

B01. A+B Problem

B02. Divisor Check

B03. Supermarket 1