yukicoder No.338 アンケート機能：主に端数処理などの実装面について

最近、私は主にyukicoderの問題を解いています。先ほど、No.338 アンケート機能 - yukicoderという問題を解きました。その際に、言語により数値を丸める（端数処理を行う）関数の挙動が異なることに注意する必要がありました。本記事では、それをはじめとする実装面に注意しつつ、この問題の解き方について述べます。

問題の趣旨

非負整数a, bはs ≧ 1を満たす（ただしs = a + bとする）。また、0以上100以下の整数A, Bはそれぞれ100a / s, 100b / sの小数点以下を四捨五入した値である。入力としてA, Bが与えられる。整数sの最小値を求めよ。

解法

全探索によれば解けます。すなわち、適当な範囲の中で(a, b)を動かし*1、100a / s, 100b / sを四捨五入した結果がA, Bに一致すればその(a, b)を答えの候補とし、そのうちでsを最小にするものを求めればよいのです。

しかし、ここで問題となるのが、四捨五入の処理です。すぐ思いつくのは、数値を丸める一般的な関数（あるいは手続き）*2を用いることです。この関数は多くの言語でroundと名付けられているようなので、ここではround関数と総称します*3。しかし、round関数の挙動は環境によって異なります。wikipedia:端数処理によると、round関数の動作としては四捨五入のほかに最近接偶数への丸めがよくあるといいます*4。例を挙げると、前者の場合にはround(2.5)が3に等しくなりますが、後者の場合には2に等しくなります。使用する言語のround関数の挙動が四捨五入であれば、浮動小数点数の誤差に注意しつつ*5これをそのまま使うことができます。これに対して、挙動が最近接偶数への丸めであれば、何らかの方法で丸めの挙動を指定するか、自ら四捨五入の関数をつくる必要があります。

解答例

私が書いた解答コードを載せておきます。なお、以下ではA, Bをそれぞれa0, b0と表記しています。

round関数の挙動が四捨五入である場合：C++11およびScalaを用いた解答例

まずは、標準のround関数が与えられた数を四捨五入する場合について述べます。ここではC++11とScalaで書いた解答コードを示します。

C++11 (g++)による解答コードは以下の通りです。std::round関数のふるまいは四捨五入なので*6、これをそのまま用いています。二つ組(a, b)を動かすのは、素直に二重のforループで表現しています。

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <limits>


int compute_min_sum(int a0, int b0, int max_cand = 500) {
    auto answer = std::numeric_limits<int>::max();
    for (auto a = 0; a < max_cand; a++)
    {
        for (auto b = 0; b < max_cand; b++)
        {
            if (a == 0 && b == 0) {
                continue;
            }
            auto s = a + b;
            auto cond_a = a0 == std::round(100 * (double)a / s);
            auto cond_b = b0 == std::round(100 * (double)b / s);
            if (cond_a && cond_b) {
                answer = std::min(answer, s);
            }
        }
    }
    return answer;
}


int main() {
    int a0, b0;
    std::cin >> a0 >> b0;
    std::cout << compute_min_sum(a0, b0) << std::endl;
    return EXIT_SUCCESS;
}

Scalaによる解答コードは次の通りです。少なくとも私が実験した限りでは、scala.math.roundの挙動は四捨五入なので、これをそのまま用いています。二重のforループの代わりに、デカルト積を用いた一重のforを使っています。また、ここではjava.util.Scannerを使って入力を読み込んでいますが、readLine().split(" ").map(_.toInt)としてもよさそうです。

object Main {

  def compute_min_sum(a0: Int, b0: Int, limit: Int = 500): Int = {
    var answer = Int.MaxValue
    for (a <- 0 until limit; b <- 0 until limit; if a != 0 || b != 0) {
      val s = a + b
      val aCondition = a0 == scala.math.round(100 * a.toDouble / s)
      val bCondition = b0 == scala.math.round(100 * b.toDouble / s)
      if (aCondition && bCondition) {
        answer = scala.math.min(answer, s)
      }
    }
    return answer
  }

  def main(args: Array[String]) {
    val scanner = new java.util.Scanner(System.in)
    val a0 = scanner.nextInt
    val b0 = scanner.nextInt
    println(compute_min_sum(a0, b0))
  }
}

round関数の挙動が最近接偶数への丸めである場合：Python 3およびScheme (Gauche)を用いた解答例

続いて、標準のround関数が与えられた数を最近接偶数へ丸める場合について述べます。ここではPython 3とScheme (Gauche)で書いた解答コードを示します。

Python 3による解答コードは以下の通りです。Python 3の組み込み関数roundは最近接偶数への丸めを行います*7。そこで、以下のコードではdecimalを用いています。コンテキストの丸めモードをROUND_HALF_UP（正の数に対しては要するに四捨五入）に定め、そのコンテキストでquantizeメソッドを用いて丸めを行っています。コンテキストの変更はwithの中に限定されます。また、Scalaの例と同様に、itertools.product（デカルト積）を用いてforを簡略化しています。なお、以下のコードではグローバル変数を用いて探索の範囲を定めていますが、どちらかといえばデフォルト引数を使うべきだったのかもしれません。

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import decimal
import itertools


MAX_CAND = 500


def solve(a0, b0):
    answer = None
    with decimal.localcontext() as context:
        context.rounding = decimal.ROUND_HALF_UP
        answer = decimal.Decimal("Inf")
        gen = (context.create_decimal(i) for i in range(MAX_CAND))
        for a, b in itertools.product(gen, repeat=2):
            if a == b == 0:
                continue
            cond_a = context.quantize(100 * a / (a + b), 0) == a0
            cond_b = context.quantize(100 * b / (a + b), 0) == b0
            if cond_a and cond_b:
                answer = min(answer, int(a + b))
    return answer


def main():
    a0, b0 = map(int, input().split())
    print(solve(a0, b0))


if __name__ == '__main__':
    main()

処理系Gaucheで動かすことを前提としたSchemeによる解答コードを次に示します。手続きround->exactの挙動は最近接偶数への丸めです。そこで、以下のコードでは四捨五入を行う手続きを定義し、これを用いています。全探索は内包表記を用いて実現しています。なお、以下のコードがSchemeらしいコードなのかどうかはよくわかっていません。

(use srfi-42)
(define (round-up-on-5 x) (truncate->exact (+ x (/ 1 2))))
(define (comp-min-a+b a0 b0 . max-a-b-opt)
    (let ((max-a-b (get-optional max-a-b-opt 500)))
        (min-ec
            (: a max-a-b)
            (: b max-a-b)
            (:let s (+ a b))
            (not (= s 0))
            (and
                (= a0 (round-up-on-5 (/ (* 100 a) s)))
                (= b0 (round-up-on-5 (/ (* 100 b) s))))
            s)))
(let* ((a0 (read)) (b0 (read)))
    (print (comp-min-a+b a0 b0)))

感想

かつてとあるAizu Online Judgeの問題でつまずいたことにより、言語によりround関数の挙動が異なることは知っていましたが、この問題で改めてそれを認識しました。日ごろよく親しんでいるような標準関数やモジュールであっても、たまにはドキュメントを読んで、挙動の詳細を確認する必要があると感じました。

*1:作問者の方の解説によると、s ≦ 200の場合を調べれば十分であるといいます。以下のコードでは、やや無駄ですがa, bをそれぞれ0以上500未満の範囲で動かしています。

*2:Pythonの組み込み関数roundや、C++の関数std::roundなどを指します。

*3:なお、Go言語のように、標準ライブラリにround関数がない言語もあります。これについてはコンテスト当時の配信で触れられていた記憶があります。

*4:実験データの処理などの点で、私としては後者のほうが好きです。

*5:作問者の方が解説で書かれているように、割り算した結果の四捨五入を整数で処理することで誤差の影響を抑えるという方法がありますが、ここでは触れません。

*6:参考：round - cpprefjp C++日本語リファレンス

*7:参考：2. 組み込み関数 — Python 3.5.1 ドキュメント