{ }codelper
尺取り法P0260

二つの入口の入場記録をまとめる

コンサートホールに入口が A と B の二か所ある。
入口ごとに、入った観客の入場時刻(秒)が入った順に書かれている。
だから二つの記録はそれぞれ小さい時刻から順に並んでいる(同じ時刻が複数あることもある)。
二つの記録をまとめて、入場時刻の順に名簿を一つ作る。
時刻が同じなら A 入口の観客が B 入口の観客より前に来る。
同じ入口の観客どうしは元の記録の順番を守る。
名簿の先頭が 1 番である。
一行目に A 入口の観客たちの名簿番号を A の記録の順に、空白一つずつ空けて出力せよ。
二行目に B 入口の観客たちの名簿番号を B の記録の順に、同じように出力せよ。
入力の一行目に A の記録の数 n と B の記録の数 m、二行目に A の時刻 n 個、三行目に B の時刻 m 個が与えられる。

入力
1 ≤ n, m ≤ 10,000、0 ≤ 時刻 ≤ 1,000,000,000(整数)。
各行の時刻は小さくならない順に与えられる
出力
二行:A の観客たちの名簿番号、B の観客たちの名簿番号
例 1 · stdin
4 3
5 9 9 120
3 9 40
stdout
2 3 4 7
1 5 6
main.py
入力(stdin)

実行すると、これらの行が順に input()・標準入力に渡されます(実行中に入力を求めません)。

$ 準備完了

コードを入力して解くにはパソコンで開いてください。モバイルでは問題と解答を見られます。

ほかの言語では?言語別の解答を見る · 8 言語の解答

二つの記録はすでに整列しているので、それぞれに指(位置 i、j)を一本ずつ置き、早いほうを名簿に入れてその指だけを一つ進めれば n + m 回で終わります。
同じ時刻なら A が先なので、A を選ぶ条件は a[i] <= b[j] です。
< と書くと同じ時刻で B が先に入ります。
片方の記録が先に終わったら、残りをすべて後ろに付ける必要があります。
while (i < n && j < m) だけ回って止まると尻尾が抜けるので、条件を j == m || (i < n && a[i] <= b[j]) と書いて一つのループで最後まで処理します。
このとき i < n を先に聞けば、使い終わった記録の範囲外を読みません(&& は前が偽なら後ろを見ません。
順番を逆にして a[i] <= b[j] && i < n と書くと、Python・Java・C#・Craykon は範囲外エラーで止まります)。
集めて並べ替えてもよいですが、JS・TS の sort() は比較関数がないと文字列にして辞書順に並べるので、100 が 9 より前に来ます。
Java で List<Integer> の二つの値を == で比べると同じオブジェクトかを見るので、-128〜127 の外の同じ時刻が違うと判定されます。
int[] に入れるか、equals・intValue() を使います。
一行に数を空白でつないで書くとき、Python print(*pos)、JS・TS・C# join(" ")、Craykon コンソール.書く(リスト) は間にだけ空白を入れ、C・C++・Java は最初の数の前に空白が出ないよう自分で気をつけます。

Pythonmain.py · 18 行
n, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split())) pos_a, pos_b = [], []i = j = 0place = 1while i < n or j < m:    # A를 고르는 때: B가 다 끝났거나, A의 시각이 B보다 이르거나 같을 때(같으면 A가 먼저)    if j == m or (i < n and a[i] <= b[j]):        pos_a.append(place)        i += 1    else:        pos_b.append(place)        j += 1    place += 1print(*pos_a)print(*pos_b)
JavaScriptmain.js · 17 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a = lines[1].trim().split(/\s+/).map(Number);const b = lines[2].trim().split(/\s+/).map(Number);const posA = [], posB = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) {  // B가 끝났거나 A가 이르거나 같으면 A가 먼저  if (j === m || (i < n && a[i] <= b[j])) {    posA.push(place);    i++;  } else {    posB.push(place);    j++;  }}console.log(posA.join(" ") + "\n" + posB.join(" "));
TypeScriptmain.ts · 17 行
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, m] = lines[0].trim().split(/\s+/).map(Number);const a: number[] = lines[1].trim().split(/\s+/).map(Number);const b: number[] = lines[2].trim().split(/\s+/).map(Number);const posA: number[] = [], posB: number[] = [];let i = 0, j = 0;for (let place = 1; place <= n + m; place++) {  if (j === m || (i < n && a[i] <= b[j])) {    posA.push(place);    i++;  } else {    posB.push(place);    j++;  }}console.log(posA.join(" ") + "\n" + posB.join(" "));
JavaMain.java · 33 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer; public class Main {    static int[] readInts(BufferedReader br, int k) throws Exception {        StringTokenizer st = new StringTokenizer(br.readLine());        int[] r = new int[k];        for (int t = 0; t < k; t++) r[t] = Integer.parseInt(st.nextToken());        return r;    }     public static void main(String[] args) throws Exception {        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(br.readLine());        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());        int[] a = readInts(br, n), b = readInts(br, m);   // int[]라 ==가 값을 비교한다        StringBuilder outA = new StringBuilder(), outB = new StringBuilder();        int i = 0, j = 0;        for (int place = 1; place <= n + m; place++) {            if (j == m || (i < n && a[i] <= b[j])) {                if (outA.length() > 0) outA.append(' ');                outA.append(place);                i++;            } else {                if (outB.length() > 0) outB.append(' ');                outB.append(place);                j++;            }        }        System.out.print(outA + "\n" + outB + "\n");    }}
C#Main.cs · 31 行
using System;using System.Collections.Generic; class Program{    static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(first[0]), m = int.Parse(first[1]);        int[] a = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse);        int[] b = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), int.Parse);        var posA = new List<int>(n);        var posB = new List<int>(m);        int i = 0, j = 0;        for (int place = 1; place <= n + m; place++)        {            if (j == m || (i < n && a[i] <= b[j]))            {                posA.Add(place);                i++;            }            else            {                posB.Add(place);                j++;            }        }        Console.WriteLine(string.Join(" ", posA));        Console.WriteLine(string.Join(" ", posB));    }}
C++main.cpp · 30 行
#include <iostream>#include <vector> void printLine(const std::vector<int>& p) {    for (size_t t = 0; t < p.size(); t++) std::cout << (t ? " " : "") << p[t];    std::cout << "\n";} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    int n, m;    std::cin >> n >> m;    std::vector<int> a(n), b(m);    for (int& x : a) std::cin >> x;    for (int& x : b) std::cin >> x;    std::vector<int> posA, posB;    int i = 0, j = 0;    for (int place = 1; place <= n + m; place++) {        if (j == m || (i < n && a[i] <= b[j])) {            posA.push_back(place);            i++;        } else {            posB.push_back(place);            j++;        }    }    printLine(posA);    printLine(posB);}
Cmain.c · 28 行
#include <stdio.h> static int a[10000], b[10000];static int pos_a[10000], pos_b[10000]; static void print_line(const int *p, int k) {    for (int t = 0; t < k; t++) printf(t ? " %d" : "%d", p[t]);    printf("\n");} int main(void) {    int n, m;    scanf("%d %d", &n, &m);    for (int t = 0; t < n; t++) scanf("%d", &a[t]);    for (int t = 0; t < m; t++) scanf("%d", &b[t]);    int i = 0, j = 0;    for (int place = 1; place <= n + m; place++) {        /* B가 끝났거나 A가 이르거나 같으면 A가 먼저 */        if (j == m || (i < n && a[i] <= b[j])) {            pos_a[i++] = place;        } else {            pos_b[j++] = place;        }    }    print_line(pos_a, n);    print_line(pos_b, m);    return 0;}
Craykonmain.cray · 27 行
first = コンソール.数読み();n = first[0];m = first[1];a = コンソール.数読み();b = コンソール.数読み();posA = [];posB = [];i = 0;j = 0;繰り返す (place = 1; place <= n + m; place++){    // B가 끝났거나, A가 남아 있고 A의 시각이 이르거나 같으면 A가 먼저    // &&는 앞이 거짓이면 뒤를 보지 않으니 i < n을 먼저 묻는다    takeA = j == m || i < n && a[i] <= b[j];    もし (takeA)    {        posA.追加(place);        i++;    }    でなければ    {        posB.追加(place);        j++;    }}コンソール.書く(posA);コンソール.書く(posB);