Namaran

Code daily. Without assist.

2026-11-04

run_all.c

#include <stddef.h>
#include <stdio.h>

typedef unsigned (*op)(unsigned);

void run_all(
    const op ops[], const int prog[], size_t len, const unsigned xs[], unsigned out[], size_t n) {
}

ops の関数はどれも、関数ごとに決まった unsigned の定数 a と b を使って、x を a * x + b に移します。a と b の値は分かりません。prog は ops の添字を len 個並べたもので、x に ops[prog[0]]、ops[prog[1]]、… の順に関数を当てていきます。xs の n 個の値それぞれにこれを行った結果を、同じ順に out へ書く run_all を書いてください。ops の関数を呼ぶ回数は合わせて len の定数倍までとし、n に比例して増やしてはいけません。len が 0 なら、out には xs と同じ値が入ります。例では、ops の各関数を、x を移す先の式で書きます。

入力例 1

ops = {3x+1, x+5}, prog = {0, 1, 0}, xs = {0, 2}

出力例 1

out = {19, 37}

入力例 2

ops = {3x+1, x+5}, prog = {}, xs = {4, 9}

出力例 2

out = {4, 9}

入力例 3

ops = {2x, x+3}, prog = {1, 0, 0}, xs = {1, 10}

出力例 3

out = {16, 52}
Reference
void run_all(
    const op ops[], const int prog[], size_t len, const unsigned xs[], unsigned out[], size_t n) {
    unsigned at0 = 0;
    unsigned at1 = 1;
    for (size_t i = 0; i < len; i++) {
        at0 = ops[prog[i]](at0);
        at1 = ops[prog[i]](at1);
    }
    unsigned slope = at1 - at0;
    for (size_t i = 0; i < n; i++) {
        out[i] = slope * xs[i] + at0;
    }
}

prog をそのまま xs の値ごとに実行すると、関数を n * len 回呼ぶことになります。関数ポインタからは関数の中身を読めないので、呼び出しを減らすには、prog 全体が何をする関数なのかを、少ない呼び出しで突き止める必要があります。

手がかりは、1次関数に1次関数を代入しても1次関数になることです。x を a1 * x + b1 に移したあとで a2 * x + b2 を当てると、結果は (a2 * a1) * x + (a2 * b1 + b2) です。prog の関数を何個つないでも同じなので、prog 全体も、ある A と B で x を A * x + B に移す関数になります。1次関数は2点で決まり、x が 0 のときの値が B、1 のときの値が A + B です。参考実装は prog を 0 と 1 から1回ずつ実行し、at0 と at1 の差を傾きにします。関数を呼ぶのは 2 * len 回で、あとは xs の値ごとに掛け算と足し算を1回ずつするだけです。入力例 1 の prog は 0 を 19 に、1 を 28 に移すので、全体は x を 9 * x + 19 に移す関数で、2 は 37 になります。

unsigned の計算が桁あふれしても、この見方は崩れません。unsigned の足し算と掛け算は、ビット数を N として 2 の N 乗で割った余りで行われ、余りをとってから計算しても、計算してから余りをとっても結果は同じです。そのため合成の式はそのまま成り立ち、at1 が at0 より小さくなった場合も、at1 - at0 は正しい傾きになります。int で同じことをすると、桁あふれは未定義動作です。len が 0 ならループは回らず、傾き 1、切片 0 となって、out には xs の値がそのまま入ります。

掲載したのは参考実装で、唯一の正解ではありません。prog の関数を1つずつ 0 と 1 で呼んで a と b を取り出し、それを合成していっても、呼び出しは同じ 2 * len 回です。