停留所が 1 番から n 番まで順にあるバス路線がある。 バスは 1 番の停留所から n 番の停留所まで一回走る。 i 番の停留所から i+1 番の停留所までの道を i 番区間という（1 ≤ i ≤ n − 1）。 乗客は m 人いて、乗客ごとに二つの整数 a、b が与えられる。 この乗客は a 番の停留所で乗り、b 番の停留所で降りる（a < b）。 だからこの乗客は a 番区間から b − 1 番区間までバスにいる。 b 番の停留所で別の人が乗っても、降りた人は b 番区間にいない。 区間ごとにバスにいた人数を数えたときのいちばん多い人数を求めよ。 人数がそのいちばん多い人数である区間のうち、いちばん小さい番号といちばん大きい番号も求めよ。 そのような区間が一つだけなら二つの番号は同じである。 いちばん多い人数、いちばん小さい番号、いちばん大きい番号を空白一つずつ空けて一行に出力せよ。 一行目に n と m、続く m 行に乗客ごとに a と b が空白で区切って与えられる。
入力
2 ≤ n ≤ 9,999、1 ≤ m ≤ 10,000、1 ≤ a < b ≤ n（すべて整数）
出力
一行：いちばん多い人数、その人数の区間のいちばん小さい番号といちばん大きい番号
例 1 · stdin
5 4
1 3
2 5
3 4
4 5
stdout
2 2 4
例 2 · stdin
4 3
1 2
2 3
3 4
stdout
1 1 3
main.py
エラー一覧00F8 ↓ · ⇧F8 ↑
入力(stdin)
実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。
$ 準備完了
コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。
ほかの言語では？言語別の解答を見る · 8 言語の解答
乗客ごとに a 番から b − 1 番区間まで一つずつ足すと、最悪 10,000 人 × 9,998 区間、約 1 億回で、Python・Craykon には遅すぎます。 代わりに差分リストを使います。 乗客ごとに diff[a] += 1、diff[b] -= 1 だけを書き、1 番区間から前から足していけば（累積和）その値がその区間の人数です。 引く位置が落とし穴です。 b 番の停留所で降りるので b 番区間から引く必要があり、diff[b + 1] で引くと降りた人がもう一区間乗っていきます。 b は n まで来るので、リストは n + 1 マス必要です。 Java new int[n] は ArrayIndexOutOfBoundsException、C# は IndexOutOfRangeException で、C はエラーなしに配列の外に書きます。 JS・TS new Array(n + 1) は空のマスだけなので += 1 が NaN になります。 .fill(0) を付けます。 Python [0] * (n + 1)、C++ std::vector<int>(n + 1, 0)、Craykon 新リスト(n + 1, 0)、Java・C# の int[] は最初から 0 です。 最初の区間と最後の区間を一度に探すには、大きくなったとき（>）だけ最初の区間を変え、同じとき（==）は最後の区間だけを変えます。
Pythonmain.py · 20 行
import sysdata = sys.stdin.buffer.read().split()n, m = int(data[0]), int(data[1])# 차이 목록: a번 구간부터 한 명 늘고, b번 구간부터 한 명 준다(b번 정류장에서 내리니까)diff = [0] * (n + 1)for k in range(m): a, b = int(data[2 + 2 * k]), int(data[3 + 2 * k]) diff[a] += 1 diff[b] -= 1load = 0best, first, last = -1, 0, 0for i in range(1, n): # i번 구간: i번 → i+1번 정류장 load += diff[i] # 앞에서부터 더하면 그 구간에 있는 사람 수 if load > best: best, first, last = load, i, i elif load == best: last = iprint(best, first, last)
JavaScriptmain.js · 15 行
const nums = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = nums;// fill(0)이 없으면 빈 칸이라 += 1이 NaN이 된다const diff = new Array(n + 1).fill(0);for (let k = 0; k < m; k++) { diff[nums[2 + 2 * k]] += 1; diff[nums[3 + 2 * k]] -= 1;}let load = 0, best = -1, first = 0, last = 0;for (let i = 1; i < n; i++) { load += diff[i]; if (load > best) [best, first, last] = [load, i, i]; else if (load === best) last = i;}console.log(`${best} ${first} ${last}`);
TypeScriptmain.ts · 15 行
import { readFileSync } from "node:fs";const nums: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = nums;const diff: number[] = new Array<number>(n + 1).fill(0);for (let k = 0; k < m; k++) { diff[nums[2 + 2 * k]] += 1; diff[nums[3 + 2 * k]] -= 1;}let load = 0, best = -1, first = 0, last = 0;for (let i = 1; i < n; i++) { load += diff[i]; if (load > best) [best, first, last] = [load, i, i]; else if (load === best) last = i;}console.log(`${best} ${first} ${last}`);
JavaMain.java · 38 行
import java.io.DataInputStream;import java.io.IOException;public class Main { static DataInputStream in = new DataInputStream(System.in); static int readInt() throws IOException { int c = in.read(); while (c < '0') c = in.read(); int r = 0; while (c >= '0') { r = r * 10 + (c - '0'); c = in.read(); } return r; } public static void main(String[] args) throws IOException { int n = readInt(), m = readInt(); int[] diff = new int[n + 1]; // b는 n까지 오니 n + 1칸 for (int k = 0; k < m; k++) { int a = readInt(), b = readInt(); diff[a]++; diff[b]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } System.out.println(best + " " + first + " " + last); }}
C#Main.cs · 25 行
using System;using System.IO;class Program{ static void Main() { string[] t = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(t[0]), m = int.Parse(t[1]); var diff = new int[n + 1]; for (int k = 0; k < m; k++) { diff[int.Parse(t[2 + 2 * k])]++; diff[int.Parse(t[3 + 2 * k])]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) last = i; } Console.WriteLine($"{best} {first} {last}"); }}
C++main.cpp · 27 行
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> diff(n + 1, 0); for (int k = 0; k < m; k++) { int a, b; std::cin >> a >> b; diff[a]++; diff[b]--; } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } std::cout << best << " " << first << " " << last << "\n";}
Cmain.c · 25 行
#include <stdio.h>static int diff[10000];int main(void) { int n, m, a, b; scanf("%d %d", &n, &m); for (int k = 0; k < m; k++) { scanf("%d %d", &a, &b); diff[a]++; /* a번 구간부터 한 명 늘고 */ diff[b]--; /* b번 정류장에서 내리니 b번 구간부터 준다 */ } int load = 0, best = -1, first = 0, last = 0; for (int i = 1; i < n; i++) { load += diff[i]; if (load > best) { best = load; first = last = i; } else if (load == best) { last = i; } } printf("%d %d %d\n", best, first, last); return 0;}
Craykonmain.cray · 30 行
first = コンソール.数読み();n = first[0];m = first[1];// 차이 목록: a번 구간부터 한 명 늘고, b번 구간부터 한 명 준다diff = 新リスト(n + 1, 0);繰り返す (k = 0; k < m; k++){ p = コンソール.数読み(); diff[p[0]] += 1; diff[p[1]] -= 1;}load = 0;best = -1;from = 0;to = 0;繰り返す (i = 1; i < n; i++){ load += diff[i]; もし (load > best) { best = load; from = i; to = i; } でなければ もし (load == best) { to = i; }}コンソール.書く(best + " " + from + " " + to);