{ }codelper
高階関数P0329

左からたたむ、右からたたむ

整数 n 個が 1 列に並んだリスト a_1, a_2, …, a_n と、命令 q 個が与えられる。
命令 1 つは "向き 演算 初めの値" の形である。
演算は 2 つの整数 x, y から値を 1 つ作る関数で、5 種類ある。
add は x + y、sub は x - y、max は 2 つのうち大きい方、min は 2 つのうち小さい方、gap は x - y の絶対値である。
向きが L なら左たたみをする。
値 v を初めの値にして、a_1 から a_n まで順に v を 演算(v, a_i) に置き換える。
向きが R なら右たたみをする。
値 v を初めの値にして、a_n から a_1 まで逆順に v を 演算(a_i, v) に置き換える。
右たたみでは、リストの要素が演算の 1 番目の位置に、これまでの値が 2 番目の位置に入る。
命令ごとに、たたみ終わったときの v を求めよ。
リストと演算の関数と初めの値を受け取るたたみ関数を向きごとに 1 つずつ作り、演算の名前に合う関数を選んで渡して解いてみよう。
例のリストは 5 2 4 である。
"L sub 20" は ((20 - 5) - 2) - 4 = 9 であり、"R sub 20" は 5 - (2 - (4 - 20)) = -13 である。
"L gap 0" は v が 5, 3, 1 と変わって 1 であり、"R gap 0" は v が 4, 2, 3 と変わって 3 である。

入力
1 行目に n と q が空白で区切られて与えられる。
2 行目に a_1 から a_n までが空白 1 つで区切られて与えられる。
続く q 行に命令が 1 行に 1 つずつ、向き(L または R)、演算の名前(add, sub, max, min, gap のどれか)、初めの値が空白 1 つで区切られて与えられる。
1 ≤ n ≤ 1,000、1 ≤ q ≤ 200、-1,000,000,000 ≤ a_i ≤ 1,000,000,000、-1,000,000,000 ≤ 初めの値 ≤ 1,000,000,000
出力
命令ごとに、与えられた順に答えを 1 行に 1 つずつ出力する。
数はコンマなしで数字だけを書く
例 1 · stdin
3 5
5 2 4
L sub 20
R sub 20
L gap 0
R gap 0
L max -7
stdout
9
-13
1
3
5
main.py
入力(stdin)

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

$ 準備完了

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

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

関数を値として扱う方法は言語によって違います。
ここでは関数を「名前 → 関数」の表に入れ、たたみ関数に引数として渡します。
Python は関数の名前がそのまま値なので、{"add": operator.add, "max": max} のように組み込み関数もそのまま入れます。
JS・TS はアロー関数 (p, q) => p - q を使います。
Java は LongBinaryOperator にラムダや Long::sum・Math::max のようなメソッド参照を入れ、f.applyAsLong(p, q) で呼びます。
C# は Func<long, long, long> にラムダや Math.Max を入れます。
C は関数ポインタ long long (*f)(long long, long long) を使い、C++ はラムダを std::function に入れます。
Craykon にはラムダがないので名前のある関数を作り、ops["sub"] = 引く; のようにかっこなしで名前だけを書いて入れ、f(acc, x) で呼びます。
罠 1: 右たたみは進む向きだけでなく引数の位置も変わります。
右から進みながら f(v, a_i) と呼ぶと、例の R sub 20 が ((20 - 4) - 2) - 5 = 9 になります(答えは -13)。
JS の reduceRight も f(これまでの値, 要素) の順で呼ぶので、そのまま使うとこう間違えます。
逆に引数の位置だけ変えて左から進んでも間違いで、L と R を区別しなくても間違いです。
罠 2: JS で list.reduce(Math.max, init) のように組み込み関数をそのまま渡してはいけません。
reduce は関数に(これまでの値, 要素, 番号, 配列)の 4 つを渡し、Math.max は受け取ったものをすべて数に変えて比べるので NaN になります(例の L max -7)。
2 つだけ受け取るアロー関数で包みます。
罠 3: 初めの値を忘れてはいけません。
Python の functools.reduce(f, items) は初めの値を渡さないと最初の要素から始めるので、例の L sub 20 が 9 ではなく (5 - 2) - 4 = -1 になります。
罠 4: 10 億の数を 1,000 個足すと 1 兆で、32 ビットを超えます。
Java・C# は long、C・C++ は long long でたたみます。
C++ でこれまでの値を int に入れると、エラーなしでおかしな数になります。
Python の整数には限界がなく、JS・TS・Craykon の数は 2^53 まで正確です。

Pythonmain.py · 33 行
import sysfrom operator import add, sub def gap(p, q):    return abs(p - q) # 이름 → 함수. 함수도 값이라서 사전에 넣을 수 있다 (max, min은 내장 함수 그대로)OPS = {"add": add, "sub": sub, "max": max, "min": min, "gap": gap} def fold_left(items, f, init):    acc = init    for x in items:        acc = f(acc, x)          # 지금까지의 값이 왼쪽    return acc def fold_right(items, f, init):    acc = init    for x in reversed(items):        acc = f(x, acc)          # 지금까지의 값이 오른쪽    return acc def main():    lines = sys.stdin.read().split("\n")    n, q = map(int, lines[0].split())    items = [int(v) for v in lines[1].split()]    out = []    for line in lines[2:2 + q]:        side, name, init = line.split()        fold = fold_left if side == "L" else fold_right        out.append(fold(items, OPS[name], int(init)))    print("\n".join(map(str, out))) main()
JavaScriptmain.js · 32 行
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items = lines[1].trim().split(/\s+/).map(Number); // 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS = {  add: (p, q) => p + q,  sub: (p, q) => p - q,  max: (p, q) => Math.max(p, q),  min: (p, q) => Math.min(p, q),  gap: (p, q) => Math.abs(p - q),}; function foldLeft(list, f, init) {  let acc = init;  for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽  return acc;} function foldRight(list, f, init) {  let acc = init;  for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽  return acc;} const out = [];for (let k = 0; k < q; k++) {  const [side, name, init] = lines[2 + k].trim().split(/\s+/);  const fold = side === "L" ? foldLeft : foldRight;  out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
TypeScriptmain.ts · 37 行
import { readFileSync } from "node:fs"; type Op = (p: number, q: number) => number;type Fold = (list: number[], f: Op, init: number) => number; const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, q] = lines[0].trim().split(/\s+/).map(Number);const items: number[] = lines[1].trim().split(/\s+/).map(Number); // 이름 → 함수. 인수를 꼭 두 개만 받도록 화살표 함수로 감싼다const OPS: Record<string, Op> = {  add: (p, q) => p + q,  sub: (p, q) => p - q,  max: (p, q) => Math.max(p, q),  min: (p, q) => Math.min(p, q),  gap: (p, q) => Math.abs(p - q),}; const foldLeft: Fold = (list, f, init) => {  let acc = init;  for (const x of list) acc = f(acc, x); // 지금까지의 값이 왼쪽  return acc;}; const foldRight: Fold = (list, f, init) => {  let acc = init;  for (let i = list.length - 1; i >= 0; i--) acc = f(list[i], acc); // 지금까지의 값이 오른쪽  return acc;}; const out: number[] = [];for (let k = 0; k < q; k++) {  const [side, name, init] = lines[2 + k].trim().split(/\s+/);  const fold: Fold = side === "L" ? foldLeft : foldRight;  out.push(fold(items, OPS[name], Number(init)));}console.log(out.join("\n"));
JavaMain.java · 48 行
import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.HashMap;import java.util.Map;import java.util.StringTokenizer;import java.util.function.LongBinaryOperator; public class Main {    static long foldLeft(long[] items, LongBinaryOperator f, long init) {        long acc = init;        for (long x : items) acc = f.applyAsLong(acc, x);      // 지금까지의 값이 왼쪽        return acc;    }     static long foldRight(long[] items, LongBinaryOperator f, long init) {        long acc = init;        for (int i = items.length - 1; i >= 0; i--) acc = f.applyAsLong(items[i], acc);   // 지금까지의 값이 오른쪽        return acc;    }     public static void main(String[] args) throws Exception {        // 이름 → 함수. 이미 있는 메서드는 Long::sum처럼, 없는 것은 람다로 적는다        Map<String, LongBinaryOperator> ops = new HashMap<>();        ops.put("add", Long::sum);        ops.put("sub", (p, q) -> p - q);        ops.put("max", Math::max);        ops.put("min", Math::min);        ops.put("gap", (p, q) -> Math.abs(p - q));         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(br.readLine());        int n = Integer.parseInt(st.nextToken());        int q = Integer.parseInt(st.nextToken());        long[] items = new long[n];        st = new StringTokenizer(br.readLine());        for (int i = 0; i < n; i++) items[i] = Long.parseLong(st.nextToken());         StringBuilder out = new StringBuilder();        for (int k = 0; k < q; k++) {            st = new StringTokenizer(br.readLine());            String side = st.nextToken();            LongBinaryOperator f = ops.get(st.nextToken());            long init = Long.parseLong(st.nextToken());            out.append(side.equals("L") ? foldLeft(items, f, init) : foldRight(items, f, init)).append('\n');        }        System.out.print(out);    }}
C#Main.cs · 47 行
using System;using System.Collections.Generic;using System.Text; class Program{    static long FoldLeft(long[] items, Func<long, long, long> f, long init)    {        long acc = init;        foreach (long x in items) acc = f(acc, x);      // 지금까지의 값이 왼쪽        return acc;    }     static long FoldRight(long[] items, Func<long, long, long> f, long init)    {        long acc = init;        for (int i = items.Length - 1; i >= 0; i--) acc = f(items[i], acc);   // 지금까지의 값이 오른쪽        return acc;    }     static void Main()    {        // 이름 → 함수. Math.Max는 형이 여러 가지라 Func<long, long, long>에 넣으면 long용이 골라진다        var ops = new Dictionary<string, Func<long, long, long>>        {            ["add"] = (p, q) => p + q,            ["sub"] = (p, q) => p - q,            ["max"] = Math.Max,            ["min"] = Math.Min,            ["gap"] = (p, q) => Math.Abs(p - q),        };         string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        int q2 = int.Parse(first[1]);        long[] items = Array.ConvertAll(Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries), long.Parse);         var sb = new StringBuilder();        for (int k = 0; k < q2; k++)        {            string[] parts = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            Func<long, long, long> f = ops[parts[1]];            long init = long.Parse(parts[2]);            sb.Append(parts[0] == "L" ? FoldLeft(items, f, init) : FoldRight(items, f, init)).Append('\n');        }        Console.Write(sb);    }}
C++main.cpp · 47 行
#include <algorithm>#include <cstdlib>#include <functional>#include <iostream>#include <map>#include <string>#include <vector> using Op = std::function<long long(long long, long long)>; long long foldLeft(const std::vector<long long> &items, const Op &f, long long init) {    long long acc = init;    for (long long x : items) acc = f(acc, x);                        // 지금까지의 값이 왼쪽    return acc;} long long foldRight(const std::vector<long long> &items, const Op &f, long long init) {    long long acc = init;    for (auto it = items.rbegin(); it != items.rend(); ++it) acc = f(*it, acc);   // 지금까지의 값이 오른쪽    return acc;} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);     // 이름 → 함수. 람다를 std::function에 담는다    const std::map<std::string, Op> ops = {        {"add", [](long long p, long long q) { return p + q; }},        {"sub", [](long long p, long long q) { return p - q; }},        {"max", [](long long p, long long q) { return std::max(p, q); }},        {"min", [](long long p, long long q) { return std::min(p, q); }},        {"gap", [](long long p, long long q) { return std::llabs(p - q); }},    };     int n, q;    std::cin >> n >> q;    std::vector<long long> items(n);    for (auto &x : items) std::cin >> x;    for (int k = 0; k < q; k++) {        std::string side, name;        long long init;        std::cin >> side >> name >> init;        const Op &f = ops.at(name);        std::cout << (side == "L" ? foldLeft(items, f, init) : foldRight(items, f, init)) << '\n';    }}
Cmain.c · 46 行
#include <stdio.h>#include <string.h> /* 함수를 가리키는 포인터의 형: long long 둘을 받아 long long을 돌려주는 함수 */typedef long long (*Op)(long long, long long); long long op_add(long long p, long long q) { return p + q; }long long op_sub(long long p, long long q) { return p - q; }long long op_max(long long p, long long q) { return p > q ? p : q; }long long op_min(long long p, long long q) { return p < q ? p : q; }long long op_gap(long long p, long long q) { return p > q ? p - q : q - p; } /* 이름 → 함수 표 */struct { const char *name; Op f; } OPS[] = {    {"add", op_add}, {"sub", op_sub}, {"max", op_max}, {"min", op_min}, {"gap", op_gap},}; long long fold_left(const long long *items, int n, Op f, long long init) {    long long acc = init;    for (int i = 0; i < n; i++) acc = f(acc, items[i]);        /* 지금까지의 값이 왼쪽 */    return acc;} long long fold_right(const long long *items, int n, Op f, long long init) {    long long acc = init;    for (int i = n - 1; i >= 0; i--) acc = f(items[i], acc);   /* 지금까지의 값이 오른쪽 */    return acc;} long long items[1000]; int main(void) {    int n, q;    scanf("%d %d", &n, &q);    for (int i = 0; i < n; i++) scanf("%lld", &items[i]);    for (int k = 0; k < q; k++) {        char side[4], name[8];        long long init;        scanf("%3s %7s %lld", side, name, &init);        Op f = NULL;        for (int j = 0; j < 5; j++)            if (strcmp(OPS[j].name, name) == 0) f = OPS[j].f;        printf("%lld\n", side[0] == 'L' ? fold_left(items, n, f, init) : fold_right(items, n, f, init));    }    return 0;}
Craykonmain.cray · 70 行
더하기(p, q){    返す p + q;} 덜기(p, q){    返す p - q;} 큰쪽(p, q){    返す 数学.大きい方(p, q);} 작은쪽(p, q){    返す 数学.小さい方(p, q);} 차이(p, q){    返す 数学.絶対値(p - q);} // 이름 → 함수. 함수 이름을 괄호 없이 쓰면 함수 자체가 값이 된다ops = 辞書();ops["add"] = 더하기;ops["sub"] = 덜기;ops["max"] = 큰쪽;ops["min"] = 작은쪽;ops["gap"] = 차이; 왼쪽접기(items, f, init){    acc = init;    それぞれ (x の中 items)    {        acc = f(acc, x); // 지금까지의 값이 왼쪽    }    返す acc;} 오른쪽접기(items, f, init){    acc = init;    繰り返す (i = items.個数 - 1; i >= 0; i--)    {        acc = f(items[i], acc); // 지금까지의 값이 오른쪽    }    返す acc;} 첫줄 = コンソール.数読み();q = 첫줄[1];items = コンソール.数読み();繰り返す (k = 0; k < q; k++){    parts = コンソール.行読み().分ける(" ");    f = ops[parts[1]];    init = parts[2].数に();    もし (parts[0] == "L")    {        コンソール.書く(왼쪽접기(items, f, init));    }    でなければ    {        コンソール.書く(오른쪽접기(items, f, init));    }}