駅が m + 1 個一列に並んでいて、i 番の区間（1 ≤ i ≤ m）の列車は i 番目の駅から i + 1 番目の駅までだけ走る。 終点の駅まで行くには、1 番の区間から m 番の区間まで、区間ごとに列車にちょうど一回ずつ順に乗らなければならない。 区間ごとに時刻表があり、列車一本は出発時刻と所要時間で書かれている。 列車は出発時刻に所要時間を足した時刻に次の駅に着く。 一つの区間の中で出発時刻はすべて異なるが、速い列車があるので、後に出た列車が先に着くこともある。 ある駅に時刻 x にいれば、その駅で出発時刻が x 以上の列車に乗れる（着いた時刻と同じ時刻に出る列車にも乗れる）。 q 個の質問に答えよ。 質問 "A t" は、最初の駅に時刻 t にいるとき、終点の駅に着ける最も早い時刻を尋ねる。 質問 "B d" は、終点の駅に時刻 d 以下に着くには、1 番の区間で乗る列車の出発時刻が最も遅くていつまでよいかを尋ねる。 質問ごとに答えを一行に一つずつ出力する。 質問 A で終点の駅まで行く方法がないとき、または質問 B で終点の駅に時刻 d 以下に着く方法がないときは -1 を出力する。
入力
一行目に m と q が空白で区切られて与えられる。 続いて 1 番の区間から順に、区間ごとに三行が与えられる：列車の数 c、出発時刻 c 個（小さい順、空白一つで区切る）、所要時間 c 個（出発時刻と同じ順）。 次の q 行に質問 "A t" または "B d" が一行に一つずつ与えられる。 1 ≤ m ≤ 10、1 ≤ c、すべての区間の c の合計 ≤ 10,000、1 ≤ q ≤ 5,000、0 ≤ 出発時刻 ≤ 2,000,000,000、1 ≤ 所要時間 ≤ 1,000,000,000、0 ≤ t, d ≤ 3,000,000,000
出力
q 行。 質問 A には終点の駅に着く最も早い時刻、質問 B には 1 番の区間の列車の最も遅い出発時刻、行けなければ -1。 数はコンマなしの数字だけで書く
例 1 · stdin
2 6
3
10 20 30
50 15 20
3
35 50 60
10 20 5
A 5
A 25
A 31
B 45
B 65
B 44
stdout
45
65
-1
20
30
-1
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
二分探索は「どの位置から条件が真に変わるか」を探すものなので、リストが一方向にだけ大きくなっていなければなりません。 出発時刻は並んでいますが、到着時刻は追い抜きのせいでばらばらです。 そこで後ろから最小値を累積して「j 番目かそれより後の列車に乗ったときの最も早い到着」を作っておくと、このリストは大きくなる一方なので二分探索ができ、質問 A の答えもここからそのまま読めます。 質問 A は「出発 ≥ 今の時刻である最初の位置」（lower bound）、質問 B は「累積した到着 ≤ 期限である最後の位置」（upper bound の一つ前）です。 道具は言語ごとに違います：Python の bisect_left・bisect_right、C++ の std::lower_bound・std::upper_bound がぴったりです。 Java の Arrays.binarySearch と C# の Array.BinarySearch は値がないと入る位置を負の数に変えて返し（Java は -(位置) - 1、C# は ~位置）、同じ値がいくつもあるとそのうちどれを返すか決まっていないので、累積した到着のように同じ値が並ぶリストには自分で書いたほうが安全です。 C の bsearch はちょうど同じ値しか探せず、なければ NULL なのでここでは使えません。 JS・TS と Craykon にはないので自分で書きます（Craykon は 数学.商(lo + hi, 2) で真ん中を求めます）。 落とし穴その一：乗れる最初の列車にそのまま乗ると間違いです。 後から出る急行が先に着くことがあります。 落とし穴その二：累積していない到着時刻に二分探索をすると、エラーなしにでたらめな位置が出ます。 落とし穴その三：境界です。 着いた時刻と同じ時刻に出る列車に乗れ（>=）、期限と同じ時刻に着いてもよい（<=）。 lower bound と upper bound を取り違えると、ちょうどこの場合だけ間違います。 落とし穴その四：出発時刻の 20 億は 32 ビットの int に入りますが、所要時間を足した 30 億はあふれます。 Java・C# はエラーなしに負の数になり、C・C++ では未定義動作なので、long・long long で受けます。 質問の t と d も 30 億までなので int では読むこともできません。 Python、JS・TS、Craykon はそのままで大丈夫です。
Pythonmain.py · 50 行
import sysfrom bisect import bisect_left, bisect_rightdef main(): data = sys.stdin.buffer.read().split() m, q = int(data[0]), int(data[1]) pos = 2 deps = [] # deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례) best = [] # best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for _ in range(m): c = int(data[pos]) pos += 1 dep = [int(x) for x in data[pos : pos + c]] pos += c arr = [dep[j] + int(data[pos + j]) for j in range(c)] pos += c # 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 for j in range(c - 2, -1, -1): if arr[j + 1] < arr[j]: arr[j] = arr[j + 1] deps.append(dep) best.append(arr) out = [] for _ in range(q): kind = data[pos] x = int(data[pos + 1]) pos += 2 if kind == b"A": # 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for i in range(m): j = bisect_left(deps[i], x) if j == len(deps[i]): x = -1 break x = best[i][j] else: # 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for i in range(m - 1, -1, -1): j = bisect_right(best[i], x) - 1 if j < 0: x = -1 break x = deps[i][j] out.append(x) print("\n".join(map(str, out)))main()
JavaScriptmain.js · 70 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [m, q] = lines[0].trim().split(/\s+/).map(Number);const deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)const best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각let row = 1;for (let i = 0; i < m; i++) { const c = Number(lines[row].trim()); const dep = lines[row + 1].trim().split(/\s+/).map(Number); const dur = lines[row + 2].trim().split(/\s+/).map(Number); row += 3; const arr = dep.map((t, j) => t + dur[j]); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (let j = c - 2; j >= 0; j--) arr[j] = Math.min(arr[j], arr[j + 1]); deps.push(dep); best.push(arr);}// a[j] >= x인 첫 자리(없으면 a.length)function lowerBound(a, x) { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 a.length)function upperBound(a, x) { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}const out = [];for (let k = 0; k < q; k++) { const [kind, value] = lines[row + k].trim().split(/\s+/); let x = Number(value); if (kind === "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (let i = 0; i < m; i++) { const j = lowerBound(deps[i], x); if (j === deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (let i = m - 1; i >= 0; i--) { const j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } out.push(x);}console.log(out.join("\n"));
TypeScriptmain.ts · 72 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [m, q] = lines[0].trim().split(/\s+/).map(Number);const deps: number[][] = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)const best: number[][] = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각let row = 1;for (let i = 0; i < m; i++) { const c = Number(lines[row].trim()); const dep: number[] = lines[row + 1].trim().split(/\s+/).map(Number); const dur: number[] = lines[row + 2].trim().split(/\s+/).map(Number); row += 3; const arr: number[] = dep.map((t, j) => t + dur[j]); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (let j = c - 2; j >= 0; j--) arr[j] = Math.min(arr[j], arr[j + 1]); deps.push(dep); best.push(arr);}// a[j] >= x인 첫 자리(없으면 a.length)function lowerBound(a: number[], x: number): number { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 a.length)function upperBound(a: number[], x: number): number { let lo = 0; let hi = a.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}const out: number[] = [];for (let k = 0; k < q; k++) { const [kind, value] = lines[row + k].trim().split(/\s+/); let x = Number(value); if (kind === "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (let i = 0; i < m; i++) { const j = lowerBound(deps[i], x); if (j === deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (let i = m - 1; i >= 0; i--) { const j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } out.push(x);}console.log(out.join("\n"));
JavaMain.java · 80 行
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { // a[j] >= x인 첫 자리(없으면 a.length) static int lowerBound(long[] a, long x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } // a[j] > x인 첫 자리(없으면 a.length) static int upperBound(long[] a, long x) { int lo = 0, hi = a.length; while (lo < hi) { int mid = (lo + hi) >>> 1; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); // 도착 시각은 30억까지 가므로 long이어야 한다 long[][] deps = new long[m][]; // 출발 시각(커지는 차례) long[][] best = new long[m][]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c = Integer.parseInt(br.readLine().trim()); deps[i] = new long[c]; best[i] = new long[c]; st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) deps[i][j] = Long.parseLong(st.nextToken()); st = new StringTokenizer(br.readLine()); for (int j = 0; j < c; j++) best[i][j] = deps[i][j] + Long.parseLong(st.nextToken()); // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = Math.min(best[i][j], best[i][j + 1]); } StringBuilder sb = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(br.readLine()); String kind = st.nextToken(); long x = Long.parseLong(st.nextToken()); if (kind.equals("A")) { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = lowerBound(deps[i], x); if (j == deps[i].length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = upperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } sb.append(x).append('\n'); } System.out.print(sb); }}
C#Main.cs · 94 行
using System;using System.Text;class Program{ // a[j] >= x인 첫 자리(없으면 a.Length) static int LowerBound(long[] a, long x) { int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo; } // a[j] > x인 첫 자리(없으면 a.Length) static int UpperBound(long[] a, long x) { int lo = 0, hi = a.Length; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int m = int.Parse(first[0]); int q = int.Parse(first[1]); // 도착 시각은 30억까지 가므로 long이어야 한다 long[][] deps = new long[m][]; // 출발 시각(커지는 차례) long[][] best = new long[m][]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c = int.Parse(Console.ReadLine()); string[] d = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string[] u = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); deps[i] = new long[c]; best[i] = new long[c]; for (int j = 0; j < c; j++) { deps[i][j] = long.Parse(d[j]); best[i][j] = deps[i][j] + long.Parse(u[j]); } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = Math.Min(best[i][j], best[i][j + 1]); } var sb = new StringBuilder(); for (int k = 0; k < q; k++) { string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long x = long.Parse(t[1]); if (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = LowerBound(deps[i], x); if (j == deps[i].Length) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = UpperBound(best[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } sb.Append(x).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 58 行
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m, q; cin >> m >> q; // 도착 시각은 30억까지 가므로 long long이어야 한다 vector<vector<long long>> deps(m); // 출발 시각(커지는 차례) vector<vector<long long>> best(m); // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c; cin >> c; deps[i].resize(c); best[i].resize(c); for (auto& t : deps[i]) cin >> t; for (int j = 0; j < c; j++) { long long dur; cin >> dur; best[i][j] = deps[i][j] + dur; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) best[i][j] = min(best[i][j], best[i][j + 1]); } for (int k = 0; k < q; k++) { char kind; long long x; cin >> kind >> x; if (kind == 'A') { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차 → lower_bound for (int i = 0; i < m; i++) { auto it = lower_bound(deps[i].begin(), deps[i].end(), x); if (it == deps[i].end()) { x = -1; break; } x = best[i][it - deps[i].begin()]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차 → upper_bound의 바로 앞 for (int i = m - 1; i >= 0; i--) { auto it = upper_bound(best[i].begin(), best[i].end(), x); if (it == best[i].begin()) { x = -1; break; } x = deps[i][it - best[i].begin() - 1]; } } cout << x << '\n'; } return 0;}
Cmain.c · 85 行
#include <stdio.h>#include <stdlib.h>// a[j] >= x인 첫 자리(없으면 n)static int lower_bound(const long long *a, int n, long long x) { int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] < x) lo = mid + 1; else hi = mid; } return lo;}// a[j] > x인 첫 자리(없으면 n)static int upper_bound(const long long *a, int n, long long x) { int lo = 0, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (a[mid] <= x) lo = mid + 1; else hi = mid; } return lo;}int main(void) { int m, q; if (scanf("%d %d", &m, &q) != 2) return 1; // 도착 시각은 30억까지 가므로 long long이어야 한다 int cnt[10]; long long *deps[10]; // 출발 시각(커지는 차례) long long *best[10]; // j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각 for (int i = 0; i < m; i++) { int c; scanf("%d", &c); cnt[i] = c; deps[i] = malloc(sizeof(long long) * c); best[i] = malloc(sizeof(long long) * c); for (int j = 0; j < c; j++) scanf("%lld", &deps[i][j]); for (int j = 0; j < c; j++) { long long dur; scanf("%lld", &dur); best[i][j] = deps[i][j] + dur; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 배열이 되어 이분 탐색을 할 수 있다 for (int j = c - 2; j >= 0; j--) { if (best[i][j + 1] < best[i][j]) best[i][j] = best[i][j + 1]; } } for (int k = 0; k < q; k++) { char kind; long long x; scanf(" %c %lld", &kind, &x); if (kind == 'A') { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 for (int i = 0; i < m; i++) { int j = lower_bound(deps[i], cnt[i], x); if (j == cnt[i]) { x = -1; break; } x = best[i][j]; } } else { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 for (int i = m - 1; i >= 0; i--) { int j = upper_bound(best[i], cnt[i], x) - 1; if (j < 0) { x = -1; break; } x = deps[i][j]; } } printf("%lld\n", x); } for (int i = 0; i < m; i++) { free(deps[i]); free(best[i]); } return 0;}
Craykonmain.cray · 98 行
첫줄 = コンソール.数読み();m = 첫줄[0];q = 첫줄[1];deps = []; // deps[i][j]: i번 구간 j번째 열차의 출발 시각(커지는 차례)best = []; // best[i][j]: j번째나 그 뒤 열차를 탔을 때 가장 이른 도착 시각繰り返す (i = 0; i < m; i++){ c = コンソール.数読み()[0]; dep = コンソール.数読み(); arr = コンソール.数読み(); 繰り返す (j = 0; j < c; j++) { arr[j] = dep[j] + arr[j]; } // 뒤에서부터 최솟값을 누적하면 커지기만 하는 목록이 되어 이분 탐색을 할 수 있다 繰り返す (j = c - 2; j >= 0; j--) { arr[j] = 数学.小さい方(arr[j], arr[j + 1]); } deps.追加(dep); best.追加(arr);}繰り返す (k = 0; k < q; k++){ t = コンソール.行読み().空白除去().分ける(); x = t[1].数に(); もし (t[0] == "A") { // 앞에서부터: 지금 시각 이후(같아도 됨)에 떠나는 첫 열차의 자리를 찾는다 繰り返す (i = 0; i < m; i++) { j = 첫자리이상(deps[i], x); もし (j == deps[i].個数) { x = -1; 抜ける; } x = best[i][j]; } } でなければ { // 뒤에서부터: 기한 안에(같아도 됨) 닿는 가장 늦은 열차의 자리를 찾는다 繰り返す (i = m - 1; i >= 0; i--) { j = 첫자리초과(best[i], x) - 1; もし (j < 0) { x = -1; 抜ける; } x = deps[i][j]; } } コンソール.書く(x);}// a[j] >= x인 첫 자리(없으면 a.개수)첫자리이상(a, x){ lo = 0; hi = a.個数; 間 (lo < hi) { mid = 数学.商(lo + hi, 2); もし (a[mid] < x) { lo = mid + 1; } でなければ { hi = mid; } } 返す lo;}// a[j] > x인 첫 자리(없으면 a.개수)첫자리초과(a, x){ lo = 0; hi = a.個数; 間 (lo < hi) { mid = 数学.商(lo + hi, 2); もし (a[mid] <= x) { lo = mid + 1; } でなければ { hi = mid; } } 返す lo;}