終わる日 r を一つに決めると、始まる日を前にずらすほど日ざしの合計も雨の合計も増えるだけです（値が 0 以上だからです）。 だから雨の条件は始まる日がある日 lo 以降のときだけ成り立ち、日ざしの条件はある日 hi 以前のときだけ成り立ちます。 r で終わる良い期間は、始まる日が lo から hi までの hi - lo + 1 個で、その中で最も短いものは hi から始まります。 r が一日増えると、lo も hi も後ろにしか動きません。 だから三つのポインタ（r、lo、hi）がそれぞれ最初から最後まで一度だけ通り、質問一つが n に比例する時間で終わります。 合計も足し直さず、lo..r の雨の合計と hi..r の日ざしの合計を一日ずつ入れたり抜いたりしながら持っていきます。 八つの言語の解き方は形がほとんど同じです。 C・C++・Java・C#・JavaScript・TypeScript は rainSum -= rain[lo++] のように引きながらポインタを動かすのを一行で書けますが、Python と Craykon は ++ を式の中で使えないので二行に分けて書きます。 罠その一：始まる日ごとに終わる日を一つずつ延ばしてすべての期間を見ると、質問一つで約 4,000 万個、全部で約 60 億個の期間を見ることになります。 雨が一度も降らず、途中でやめることもできない入力があります。 こう書いた Python の解答は時間内に終わらず、同じやり方の C の解答もこのコンピュータで最も大きい入力に 12 秒かかりました。 罠その二：lo が hi より後ろにあるなら、r で終わる良い期間はありません。 lo <= hi を確かめずに hi - lo + 1 を足すと負の数が足されます。 例 1 の最初の質問は 4 ではなく 2 になり、二番目の質問は 0 0 0 ではなく -1 1 3 になります。 罠その三：hi を動かす繰り返しに hi < r がないと、S が 0 のとき hi が r を越えて、日が一つもない期間を数えます。 例 1 の三番目の質問 "0 1" で JavaScript は 5 1 1 ではなく 12 -1 3 を出力します。 JavaScript はリストの終わりを越えて読んでも undefined を返すだけなので静かに間違え、Python は IndexError で、Java・C# は例外で止まります。 C・C++ は何が起こるか決まっていません。 罠その四：最も短い期間が複数あれば、最も早く始まるものを選ばなければなりません。 r を前から増やしていくので、< で比べれば先に見つけたものが残ります。 <= で比べると、例 1 の三番目の質問で始まる日が 1 ではなく 6 になります。 罠その五：合計は 9 × 10^12 まで大きくなります。 Java・C#・C・C++ は合計と S、R を long/long long に入れなければなりません。 Java で合計を int に入れると、例 2 の最初の質問で 30 億が -1294967296 に変わり、1 3 1 ではなく 0 0 0 が出ます。 Python の整数には大きさの制限がなく、JavaScript・TypeScript・Craykon の数は 2^53 まで正確なので、そのままで合います。 良い期間の数は多くても約 4,050 万なので int に入ります。
Pythonmain.py · 44 行
import sysdef solve(n, sun, rain, need, limit): """햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날).""" count = 0 best_len = best_start = 0 lo = 0 # 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0 # 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) rain_sum = 0 # lo..r의 비 합 sun_sum = 0 # hi..r의 햇볕 합 for r in range(n): rain_sum += rain[r] while rain_sum > limit: rain_sum -= rain[lo] lo += 1 sun_sum += sun[r] while hi < r and sun_sum - sun[hi] >= need: sun_sum -= sun[hi] hi += 1 # 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if sun_sum >= need and lo <= hi: count += hi - lo + 1 if best_len == 0 or r - hi + 1 < best_len: best_len = r - hi + 1 best_start = hi + 1 return count, best_len, best_startdef main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) sun = [int(x) for x in data[2:2 + n]] rain = [int(x) for x in data[2 + n:2 + 2 * n]] out = [] pos = 2 + 2 * n for _ in range(q): need, limit = int(data[pos]), int(data[pos + 1]) pos += 2 out.append("%d %d %d" % solve(n, sun, rain, need, limit)) print("\n".join(out))main()
JavaScriptmain.js · 37 行
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun = data.slice(2, 2 + n);const rain = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need, limit) { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
TypeScriptmain.ts · 38 行
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const n = data[0];const q = data[1];const sun: number[] = data.slice(2, 2 + n);const rain: number[] = data.slice(2 + n, 2 + 2 * n);// 햇볕 합 ≥ need, 비 합 ≤ limit인 구간의 수와 가장 짧은 구간(길이, 시작 날)function solve(need: number, limit: number): [number, number, number] { let count = 0; let bestLen = 0; let bestStart = 0; let lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 let hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) let rainSum = 0; // lo..r의 비 합 let sunSum = 0; // hi..r의 햇볕 합 for (let r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen === 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } return [count, bestLen, bestStart];}const out: string[] = [];for (let i = 0; i < q; i++) { out.push(solve(data[2 + 2 * n + 2 * i], data[3 + 2 * n + 2 * i]).join(" "));}console.log(out.join("\n"));
JavaMain.java · 45 行
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 q = Integer.parseInt(st.nextToken()); long[] sun = new long[n]; long[] rain = new long[n]; st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) sun[i] = Long.parseLong(st.nextToken()); st = new StringTokenizer(in.readLine()); for (int i = 0; i < n; i++) rain[i] = Long.parseLong(st.nextToken()); StringBuilder out = new StringBuilder(); for (int k = 0; k < q; k++) { st = new StringTokenizer(in.readLine()); long need = Long.parseLong(st.nextToken()); long limit = Long.parseLong(st.nextToken()); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } out.append(count).append(' ').append(bestLen).append(' ').append(bestStart).append('\n'); } System.out.print(out); }}
C#Main.cs · 44 行
using System;using System.Text;class Program{ static void Main() { string[] p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(p[0]), q = int.Parse(p[1]); long[] sun = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); long[] rain = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse); var sb = new StringBuilder(); for (int k = 0; k < q; k++) { p = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); long need = long.Parse(p[0]), limit = long.Parse(p[1]); int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long rainSum = 0; // lo..r의 비 합 long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } sb.Append(count).Append(' ').Append(bestLen).Append(' ').Append(bestStart).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 39 行
#include <iostream>#include <vector>using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; vector<long long> sun(n), rain(n); for (auto& v : sun) cin >> v; for (auto& v : rain) cin >> v; while (q--) { long long need, limit; cin >> need >> limit; int count = 0, bestLen = 0, bestStart = 0; int lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 int hi = 0; // 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) long long rainSum = 0; // lo..r의 비 합 long long sunSum = 0; // hi..r의 햇볕 합 for (int r = 0; r < n; r++) { rainSum += rain[r]; while (rainSum > limit) rainSum -= rain[lo++]; sunSum += sun[r]; while (hi < r && sunSum - sun[hi] >= need) sunSum -= sun[hi++]; // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 if (sunSum >= need && lo <= hi) { count += hi - lo + 1; if (bestLen == 0 || r - hi + 1 < bestLen) { bestLen = r - hi + 1; bestStart = hi + 1; } } } cout << count << ' ' << bestLen << ' ' << bestStart << '\n'; } return 0;}
Cmain.c · 36 行
#include <stdio.h>static long long sun[9000], rain[9000];int main(void) { int n, q; if (scanf("%d %d", &n, &q) != 2) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &sun[i]) != 1) return 0; for (int i = 0; i < n; i++) if (scanf("%lld", &rain[i]) != 1) return 0; for (int k = 0; k < q; k++) { long long need, limit; if (scanf("%lld %lld", &need, &limit) != 2) return 0; int count = 0, best_len = 0, best_start = 0; int lo = 0; /* 비 합이 limit 이하가 되는 가장 이른 시작 날 */ int hi = 0; /* 햇볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) */ long long rain_sum = 0; /* lo..r의 비 합 */ long long sun_sum = 0; /* hi..r의 햇볕 합 */ for (int r = 0; r < n; r++) { rain_sum += rain[r]; while (rain_sum > limit) rain_sum -= rain[lo++]; sun_sum += sun[r]; while (hi < r && sun_sum - sun[hi] >= need) sun_sum -= sun[hi++]; /* 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 */ if (sun_sum >= need && lo <= hi) { count += hi - lo + 1; if (best_len == 0 || r - hi + 1 < best_len) { best_len = r - hi + 1; best_start = hi + 1; } } } printf("%d %d %d\n", count, best_len, best_start); } return 0;}
Craykonmain.cray · 45 行
첫줄 = コンソール.数読み();n = 첫줄[0];q = 첫줄[1];볕 = コンソール.数読み();비 = コンソール.数読み();繰り返す (k = 0; k < q; k++){ 줄 = コンソール.数読み(); need = 줄[0]; limit = 줄[1]; 센수 = 0; 짧은길이 = 0; 짧은시작 = 0; lo = 0; // 비 합이 limit 이하가 되는 가장 이른 시작 날 hi = 0; // 볕 합이 need 이상인 가장 늦은 시작 날(되는 날이 있을 때) 비합 = 0; // lo..r의 비 합 볕합 = 0; // hi..r의 볕 합 繰り返す (r = 0; r < n; r++) { 비합 = 비합 + 비[r]; 間 (비합 > limit) { 비합 = 비합 - 비[lo]; lo = lo + 1; } 볕합 = 볕합 + 볕[r]; 間 (hi < r && 볕합 - 볕[hi] >= need) { 볕합 = 볕합 - 볕[hi]; hi = hi + 1; } // 시작 날이 lo 이상 hi 이하이면 두 조건이 모두 맞는다 もし (볕합 >= need && lo <= hi) { 센수 = 센수 + hi - lo + 1; もし (짧은길이 == 0 || r - hi + 1 < 짧은길이) { 짧은길이 = r - hi + 1; 짧은시작 = hi + 1; } } } コンソール.書く(센수 + " " + 짧은길이 + " " + 짧은시작);}