先に着く k 本のうち A 路線が i 本なら、B 路線は k-i 本です。 この i を二分探索で見つけます。 A の a[mid]（0 から数えて）が先の k 本に入るには、それより先に着く B の列車が k-mid-1 本以下でなければならず、これは b[k - mid - 1] + d >= a[mid] と同じです。 mid が大きくなるにつれて、この条件は真から偽に一度だけ変わります。 真なら lo = mid + 1、偽なら hi = mid と狭めていけば、14 回ほどで i が決まります。 k 番目の列車は、A の i 番目と B の k-i 番目のうち遅く着くほうです。 真ん中は Python (lo + hi) // 2、Java・C#・C・C++ (lo + hi) / 2、JavaScript・TypeScript Math.floor((lo + hi) / 2)、Craykon 数学.商(lo + hi, 2) で求めます。 Python bisect や C++ std::lower_bound は一つのリストから一つの値を探す道具なので、二つのリストを一緒に見るこの条件にはそのままでは使えず、繰り返しを自分で書きました。 罠その一：質問ごとに二つの時刻表を前から k 本目まで一つずつ数えると、最も大きい入力で約 1 億 6 千万回数えます。 d が質問ごとに違うので、一度まとめた順番を使い回すこともできません。 こう書いた Python の解答は時間内に終わりませんでした。 正直に言うと、同じやり方の C の解答はこのコンピュータで 0.4 秒以内に終わりました。 二分探索がどうしても必要なのは遅い言語でのことです。 罠その二：同じ時刻なら A が先です。 だから条件と最後の比較は >= でなければなりません。 二つを > と書くと B が先と数えられ、例 1 の二番目の質問 "2 5" は B 1 10 ではなく A 1 10 が、三番目の質問は A 2 20 ではなく B 2 20 が出ます。 罠その三：i の範囲は 0 から n までではなく、max(0, k - m) から min(k, n) までです。 範囲を 0 から n までにすると、k - mid - 1 が負になったり m 以上になったりします。 Python は負の番号を後ろから数えた位置として読むので、例 1 の最初の質問で静かに A 2 20 を出力し（答えは B 1 5）、五番目の質問 "7 5" では b[5] を読もうとして IndexError で止まります。 Java・C# はどちらの場合も例外で止まり、C・C++ は何が起こるか決まっていません。 罠その四：出力する時刻は時刻表の時刻ではなく、その日に実際に着く時刻です。 B 路線なら d を足さなければなりません。 足さないと、例 1 の二番目の質問が B 1 10 ではなく B 1 5 になります。 罠その五：時刻も d も 2 × 10^9 までなので、それぞれは 32 ビットの int に入りますが、足すと 4 × 10^9 まで大きくなってあふれます。 Java・C#・C・C++ は時刻と d を long/long long に入れなければなりません。 Java で int に入れると、例 2 の二番目の質問で 4000000000 が -294967296 に変わり、B 2 4000000000 ではなく A 1 2000000000 が出ます。 Python の整数には大きさの制限がなく、JavaScript・TypeScript・Craykon の数は 2^53 まで正確なので、そのままで合います。
Pythonmain.py · 33 行
import sysdef main(): data = sys.stdin.buffer.read().split() n, m, q = int(data[0]), int(data[1]), int(data[2]) a = [int(x) for x in data[3:3 + n]] b = [int(x) for x in data[3 + n:3 + n + m]] out = [] pos = 3 + n + m for _ in range(q): k, d = int(data[pos]), int(data[pos + 1]) pos += 2 # 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = max(0, k - m) hi = min(k, n) while lo < hi: mid = (lo + hi) // 2 # A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if b[k - mid - 1] + d >= a[mid]: lo = mid + 1 else: hi = mid i, j = lo, k - lo # k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if i == 0 or (j > 0 and b[j - 1] + d >= a[i - 1]): out.append("B %d %d" % (j, b[j - 1] + d)) else: out.append("A %d %d" % (i, a[i - 1])) print("\n".join(out))main()
JavaScriptmain.js · 27 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a = data.slice(3, 3 + n);const b = data.slice(3 + n, 3 + n + m);const out = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
TypeScriptmain.ts · 28 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const m = data[1];const q = data[2];const a: number[] = data.slice(3, 3 + n);const b: number[] = data.slice(3 + n, 3 + n + m);const out: string[] = [];for (let x = 0; x < q; x++) { const k = data[3 + n + m + 2 * x]; const d = data[4 + n + m + 2 * x]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. let lo = Math.max(0, k - m); let hi = Math.min(k, n); while (lo < hi) { const mid = Math.floor((lo + hi) / 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } const i = lo; const j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i === 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) out.push("B " + j + " " + (b[j - 1] + d)); else out.push("A " + i + " " + a[i - 1]);}console.log(out.join("\n"));
JavaMain.java · 42 行
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int q = Integer.parseInt(st.nextToken()); long[] a = new long[n]; long[] b = new long[m]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) a[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < m; i++) b[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int x = 0; x < q; x++) { st = new StringTokenizer(in.readLine()); int k = Integer.parseInt(st.nextToken()); long d = Long.parseLong(st.nextToken()); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.max(0, k - m); int hi = Math.min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) { out.append("B ").append(j).append(' ').append(b[j - 1] + d).append('\n'); } else { out.append("A ").append(i).append(' ').append(a[i - 1]).append('\n'); } } System.out.print(out); }}
C#Main.cs · 38 行
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), m = int.Parse(p[1]), q = int.Parse(p[2]); long[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int x = 0; x < q; x++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int k = int.Parse(p[0]); long d = long.Parse(p[1]); // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = Math.Max(0, k - m); int hi = Math.Min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) sb.Append("B ").Append(j).Append(' ').Append(b[j - 1] + d).Append('\n'); else sb.Append("A ").Append(i).Append(' ').Append(a[i - 1]).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 34 行
#include <algorithm>#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<long long> a(n), b(m); for (auto& v : a) cin >> v; for (auto& v : b) cin >> v; while (q--) { int k; long long d; cin >> k >> d; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. int lo = max(0, k - m); int hi = min(k, n); while (lo < hi) { int mid = (lo + hi) / 2; // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) cout << "B " << j << ' ' << b[j - 1] + d << '\n'; else cout << "A " << i << ' ' << a[i - 1] << '\n'; } return 0;}
Cmain.c · 30 行
#include <stdio.h>static long long a[9000], b[9000];int main(void) { int n, m, q; if (scanf("%d %d %d", &n, &m, &q) != 3) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &a[i]) != 1) return 0; for (int i = 0; i < m; i++) if (scanf("%lld", &b[i]) != 1) return 0; for (int x = 0; x < q; x++) { int k; long long d; if (scanf("%d %lld", &k, &d) != 2) return 0; /* 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. */ int lo = k - m > 0 ? k - m : 0; int hi = k < n ? k : n; while (lo < hi) { int mid = (lo + hi) / 2; /* A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 */ if (b[k - mid - 1] + d >= a[mid]) lo = mid + 1; else hi = mid; } int i = lo, j = k - lo; /* k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 */ if (i == 0 || (j > 0 && b[j - 1] + d >= a[i - 1])) printf("B %d %lld\n", j, b[j - 1] + d); else printf("A %d %lld\n", i, a[i - 1]); } return 0;}
Craykonmain.cray · 40 行
첫줄 = コンソール.数読み();n = 첫줄[0];m = 첫줄[1];q = 첫줄[2];a = コンソール.数読み();b = コンソール.数読み();繰り返す (x = 0; x < q; x++){ 줄 = コンソール.数読み(); k = 줄[0]; d = 줄[1]; // 앞의 k대 가운데 A 노선 열차의 수 i를 찾는다. B 노선은 k - i대이다. lo = 数学.大きい方(0, k - m); hi = 数学.小さい方(k, n); 間 (lo < hi) { mid = 数学.商(lo + hi, 2); // A의 mid번(0부터) 열차가 앞의 k대에 들려면 그보다 먼저 오는 B 열차가 k-mid-1대 이하여야 한다 もし (b[k - mid - 1] + d >= a[mid]) { lo = mid + 1; } でなければ { hi = mid; } } i = lo; j = k - lo; // k번째는 A의 마지막 것과 B의 마지막 것 가운데 늦은 쪽. 같은 시각이면 B가 뒤다 もし (i == 0 || j > 0 && b[j - 1] + d >= a[i - 1]) { コンソール.書く("B " + j + " " + (b[j - 1] + d)); } でなければ { コンソール.書く("A " + i + " " + a[i - 1]); }}