0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

タクシー運賃は距離と時間の二軸で決まる――低速90秒80円と深夜1.25倍の補正

0
Posted at

タクシー運賃は距離と時間の二軸で決まる――低速90秒80円と深夜1.25倍の補正

タクシーの運賃は、走った距離だけでは決まらない。渋滞でほとんど進まなくても、時速10km以下で走った時間が90秒たまるごとに80円が加算される。深夜はさらに、料金を20%増しにするのではなく、走行距離そのものを1.25倍に補正して料金表に当てはめる。計算式そのものは足し算と割り算だけだが、実装で壊れるのは計算式ではなく、平均速度の判定、深夜の境界、浮動小数点の誤差、異常入力の扱いである。

この記事の仕様は、LINEの過去の新卒採用試験を題材にした公開ミッション(TechTrain)のものである。タクシー料金の練習問題を扱った過去の記事(タクシー料金をJavaで計算する――切り上げは「199を足して割る」、150m単位なら149になる理由、タクシー料金Ver.2をJavaで計算する――深夜20%割増と10%割引は「何に掛けるか」で料金が変わる)とは料金の数字が違う。Ver.1・Ver.2が500円・200m単位・20%割増の練習仕様だったのに対し、こちらは初乗り410円・237m単位・1.25倍補正の公開ミッション版の仕様である。数字を混ぜて読まないこと。

仕様の全体像:3つのメーター

タクシーには3つのメーターがある、とLINEの公式解説は整理している。距離メーター、低速走行時間メーター、運賃メーターである。公開ミッションの仕様を表にすると次の通りになる。

項目 仕様
初乗り 1.052km(1052m)まで410円
距離加算 超過分を237mごとに80円、端数は切り上げ
低速運賃 時速10km以下の走行時間、90秒ごとに80円、端数は切り捨て
深夜割増 22時〜翌5時、走行距離と低速走行時間を1.25倍に補正
入力 標準入力、1行に hh:mm:ss.fff と前回記録時からの走行距離(m)
出力 運賃(円)を標準出力、終了コード0
異常入力 標準出力に何も出さず、終了コード0以外で終了

距離の加算は切り上げ、低速時間の加算は切り捨てと、端数の向きが逆になっている。ここを逆に覚えると、境界のテストで料金が80円ずれる。

低速運賃は「区間の平均速度」で決まる

低速かどうかの判定は、レコード間の平均速度で行う。仕様書は「速度は、レコードの平均速度(走行距離を前回記録からの時間で割ったもの)にて算出する」「平均速度が10km以下の場合は、その時間はずっと10km以下で走行したものとして計算する」と明記している。

この定義には、見落としやすい帰結が2つある。

1つ目は、区間内の変動が見えないことである。90秒の区間で250m走った場合、平均速度はちょうど10km/hで、低速時間は90秒になる。実際には60秒止まって30秒で250m走ったとしても、仕様上は同じ90秒が低速時間になる。区間の中で何があったかは、記録からは分からない。仕様はその分からなさを、平均速度で割り切る設計にしている。

2つ目は、1秒の差で80円変わる境界があることである。同じ250mでも、89秒で走れば平均は約10.11km/hで低速時間は0秒になる。90秒なら80円、89秒なら0円である。速度の判定は 距離 ÷ 時間 ではなく、割り算を避けた整数の比較で書くのが安全である。速度が10km/h以下であることは、距離を0.1m単位の整数 dm、時間をミリ秒の整数 dtMs として、dm * 36 <= dtMs と等しい。250mを90秒で走る場合は 2500 * 36 = 90000 <= 90000 で等号が成立し、低速側になる。ちょうど10km/hは低速である。

// 低速判定:速度 <= 10 km/h を割り算なしの整数比較で書く
// 速度[km/h] = (dm / 10) / (dtMs / 1000) * 3.6 = dm * 360 / dtMs
// dm * 360 / dtMs <= 10  <=>  dm * 36 <= dtMs
private static boolean isLowSpeed(long distanceDm, long dtMs) {
    return distanceDm * 36 <= dtMs;
}

深夜割増は「20%増し」ではなく「1.25倍の補正」

深夜割増の仕組みは、料金に20%を掛けるものではない。仕様書は「深夜時間帯における走行距離が実際の距離の1.25倍になっているものとして補正して計算する」と書いている。料金表に当てはめる前に、距離そのものを伸ばす。

仕様書の具体例が、この設計の意味をよく表している。深夜23時から850.0m乗車した場合、補正後の走行距離は 850m * 1.25 = 1062.5m になり、料金表から490円になる。850mだけ見れば初乗りの1052mに収まって410円のはずが、補正で初乗りの境界を越える。

つまり深夜の初乗りの境界は、実質的に 1052 / 1.25 = 841.6m まで下がる。841.6mなら410円、841.7mなら490円である。昼なら410円で済む距離が、深夜は同じ距離でもう一段上の料金になる。割増を「最後に料金へ掛ける」と実装すると、この境界の動きを再現できない。補正は距離にかけるもので、料金にかけるものではない。

低速走行時間についても同じ補正がかかる。深夜の低速時間は実際の時間の1.25倍として通算する。昼の低速60秒と深夜の低速60秒は、通算すると 60 + 60 * 1.25 = 135 秒になり、90秒単位で切り捨てて80円になる。

// 深夜補正は距離と低速時間にかける。料金に掛けるのではない
// 補正後距離を 0.025m 単位の整数で持つ:昼の距離 dm は ×4、深夜の距離 dm は ×5
long correctedQdm = dayDistanceDm * 4 + nightDistanceDm * 5;
long distanceFare;
if (correctedQdm <= FIRST_DISTANCE_QDM) { // 1052m = 42080
    distanceFare = FIRST_FARE;             // 410円
} else {
    long units = (correctedQdm - FIRST_DISTANCE_QDM + UNIT_QDM - 1) / UNIT_QDM;
    distanceFare = FIRST_FARE + UNIT_FARE * units; // 237m ごとに 80 円、切り上げ
}
// 低速時間も同じく通算してから 90 秒単位で切り捨てる
long lowQms = dayLowMs * 4 + nightLowMs * 5;
long lowFare = UNIT_FARE * (lowQms / (LOW_SPEED_MS * 4));

時間帯をまたいでも初乗りは1回だけ

通常時間帯から深夜時間帯へ、あるいは深夜から通常へと走行がまたがる場合、仕様書は「通常時間帯の走行距離と深夜時間帯の補正後の走行距離とは通算して計算する。時間帯の切り替え時にそれまでの走行距離が清算されたり、初乗り料金が新たに発生したりすることはない」と書いている。低速走行時間も同様に通算する。

区間ごとに料金を計算して足し合わせる実装では、この通算を壊す。21時59分に100m走って22時をまたいで100m走った場合、区間ごとに清算すれば初乗りが2回発生する。正しくは昼の100mと深夜の補正後125mを通算した225mで、距離運賃は410円のままである。

深夜かどうかの判定は、区間の両端の記録時刻で行う。仕様書は「走行ログの前回記録時刻、今回記録時刻がともに深夜時間帯に含まれる場合は、その記録は深夜時間帯の走行」と定めている。片端だけが深夜に入っている区間は、深夜走行にならない。21時59分から22時00分の区間は昼の走行、22時00分から22時01分の区間は深夜の走行になる。22時00分00秒000ちょうどは深夜側で、区間は閉区間である。

時刻の扱いでもう1つ注意がある。乗車開始後に深夜24時をまたぐと、hh は 00 に戻らず 24、25 と表記される。25時30分は深夜である。時刻を hh:mm:ss.fff からミリ秒へ変換し、24時間で割った余りで深夜判定をすれば、hh が99まで伸びても同じ判定が使える。

// 時刻をミリ秒の整数に変換し、24 時間で割った余りで深夜判定をする
// hh は 00〜99 まで伸びる(24 時をまたぐと 24、25、…と表記される)
private static boolean isNight(long timeMs) {
    long tod = timeMs % (24L * 3600 * 1000);
    return tod >= 22L * 3600 * 1000 || tod < 5L * 3600 * 1000;
}

浮動小数点を使わない

この仕様で最も実務的な落とし穴は、浮動小数点である。走行距離は小数第1位(10cm)単位で記録される。double で足し上げると、1052.0mちょうどのはずの距離が、誤差で1052.0mをわずかに超えることがある。実測では、0.1を10520回加算すると 1052.0000000001387 になった。1052.0mちょうどの乗車が、誤って490円と計算される。0.1 + 0.2 が 0.30000000000000004 になるのと同じ現象である。

LINEの公式解説も、著者がこの問題でハマった点として「純粋に足し算したので距離がずれてしまった。浮動小数点の演算考慮不足」を挙げ、「距離を10かけて浮動小数処理を行わないようにする」という解き方を示している。距離は10倍して0.1m単位の整数(デシメートル)で持ち、時刻はミリ秒の整数で持つ。深夜の1.25倍補正も、×5/4 の整数演算で済ませる。0.025m単位の整数で補正後距離を持てば、割り算の端数も出ない。

// 距離は 0.1m 単位の整数(デシメートル)で読む。double は使わない
// "99.9" -> 999、"0.0" -> 0
private static long parseDistanceDm(String s) {
    int dot = s.indexOf('.');
    if (dot < 0 || s.length() - dot != 2) {
        throw new IllegalArgumentException("距離の形式が不正: " + s);
    }
    long dm = Long.parseLong(s.substring(0, dot)) * 10
            + Long.parseLong(s.substring(dot + 1));
    if (dm < 0 || dm > 999) {
        throw new IllegalArgumentException("距離が範囲外: " + s);
    }
    return dm;
}

異常入力は「仕様に従わないもの全部」

この仕様の異常入力の定義は、個別のケースを列挙しない。「仕様に従わない異常な入力に対しては、標準出力には何も出力せずに、終了コード0以外で終了する」という総括規定だけである。個別の異常ケースが列挙されていない以上、入力の制約をすべて洗い出してチェック一覧にするのが実装側の仕事になる。

仕様書から読み取れるチェックは、次の通りである。

チェック 根拠
行が hh:mm:ss.fff と距離の2カラムで、区切りは半角スペース1文字 入力形式の規定
時刻の桁数が規定通りで、hh は00〜99、mm・ss は00〜59 時刻形式の規定
空行がない(最終行の改行コードの後をのぞく) 空行は存在しないという規定
時刻が時間順に並んでいる 記録は時間軸に沿って並べられているという規定
1行目の距離が 0.0 である 1行目は必ず 0.0 という規定
2行以上のデータがある 必ず2行以上という規定
総走行距離が0.1以上である 総走行距離は0.1以上という規定
1レコードの距離が0.0〜99.9の範囲内である 数値の範囲の規定

正常系と異常系では出口が違う。正常なら運賃を標準出力に出して終了コード0、異常なら標準出力に何も出さず終了コード0以外である。異常を検出したら、部分的な運賃を出してはいけない。エラーメッセージは標準エラー出力に出してよい。公式解説は、採点時にのみ実行する隠れたテストケースがあり、タームによってはエラー処理に関するテストケースが膨大だと明記している。計算が合っていても、異常入力の扱いが甘いと点数が伸びない。

なお、公式解説ブログのエラー定義(「上の行から45秒を超えていたらエラー」など)や料金の数字(初乗り400円、45秒ごとの低速料金、深夜30%増し・ピーク50%増し)は、別ターム版の問題のものである。この記事の仕様(TechTrain公開ミッション版)とは数字が違うため、数字としては使っていない。使うのは、隠れたテストケースとエラー処理の重視、浮動小数点の回避、1パス処理という教訓の部分だけである。仕様書の時刻表記にも 23:59.59.999 というコロンが1つ欠けた表記がそのまま残っている。仕様書は読み飛ばさず、実装では正規表現で厳密に読む。

5万行を1パスで処理する

入力の最大行数は5万行である。行ごとに前回の記録だけを持って処理すれば、入力全体をメモリに載せる必要はない。距離と低速時間の累計だけを持ち、1行ずつ読んで1行ずつ処理する。公式解説も、単純に計算するとデータ量が多くてタイムアウトになる場合があると述べている。5万行なら1パスで十分に処理できるが、行ごとに全体を走査し直す書き方にすると、行数の二乗に近い計算量になる。

public static long calculate(BufferedReader in) throws IOException {
    String line = in.readLine();
    if (line == null || line.isEmpty()) {
        throw new IllegalArgumentException("入力が空である");
    }
    Record prev = parseRecord(line);
    if (prev.distanceDm() != 0) {
        throw new IllegalArgumentException("1行目の距離は 0.0 でなければならない");
    }
    long dayDm = 0, nightDm = 0, dayLowMs = 0, nightLowMs = 0, totalDm = 0;
    int rows = 1;
    while ((line = in.readLine()) != null) {
        if (line.isEmpty()) {
            throw new IllegalArgumentException("空行がある");
        }
        Record cur = parseRecord(line);
        if (cur.timeMs() < prev.timeMs()) {
            throw new IllegalArgumentException("時刻が時間順でない");
        }
        long dtMs = cur.timeMs() - prev.timeMs();
        totalDm += cur.distanceDm();
        boolean night = isNight(prev.timeMs()) && isNight(cur.timeMs());
        if (night) {
            nightDm += cur.distanceDm();
            if (isLowSpeed(cur.distanceDm(), dtMs)) {
                nightLowMs += dtMs;
            }
        } else {
            dayDm += cur.distanceDm();
            if (isLowSpeed(cur.distanceDm(), dtMs)) {
                dayLowMs += dtMs;
            }
        }
        prev = cur;
        rows++;
    }
    if (rows < 2 || totalDm == 0) {
        throw new IllegalArgumentException("2行以上で総走行距離 0.1 以上が必要である");
    }
    long correctedQdm = dayDm * 4 + nightDm * 5;
    long distanceFare = correctedQdm <= FIRST_DISTANCE_QDM
            ? FIRST_FARE
            : FIRST_FARE + UNIT_FARE
                * ((correctedQdm - FIRST_DISTANCE_QDM + UNIT_QDM - 1) / UNIT_QDM);
    long lowQms = dayLowMs * 4 + nightLowMs * 5;
    long lowFare = UNIT_FARE * (lowQms / (LOW_SPEED_MS * 4));
    return distanceFare + lowFare;
}

検証環境

上の calculate で使う定数、レコードの読み取り、時刻のパース、main は次の通りである。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TaxiFare {
    private static final long FIRST_FARE = 410;           // 初乗り運賃(円)
    private static final long FIRST_DISTANCE_QDM = 1052L * 40; // 初乗り距離を 0.025m 単位で
    private static final long UNIT_QDM = 237L * 40;       // 加算単位 237m を 0.025m 単位で
    private static final long UNIT_FARE = 80;             // 加算単位あたりの運賃(円)
    private static final long LOW_SPEED_MS = 90_000;      // 低速運賃の単位時間 90 秒

    public static void main(String[] args) throws IOException {
        try {
            long fare = calculate(new BufferedReader(new InputStreamReader(System.in)));
            System.out.println(fare);
        } catch (IllegalArgumentException e) {
            // 異常入力では標準出力に何も出さず、終了コード 0 以外で終了する
            System.err.println(e.getMessage());
            System.exit(1);
        }
    }

    private record Record(long timeMs, long distanceDm) {
    }

    private static Record parseRecord(String line) {
        String[] parts = line.split(" ", -1);
        if (parts.length != 2) {
            throw new IllegalArgumentException("行の形式が不正: " + line);
        }
        return new Record(parseTimeMs(parts[0]), parseDistanceDm(parts[1]));
    }

    private static long parseTimeMs(String s) {
        if (!s.matches("\\d{2}:\\d{2}:\\d{2}\\.\\d{3}")) {
            throw new IllegalArgumentException("時刻の形式が不正: " + s);
        }
        int hh = Integer.parseInt(s.substring(0, 2));
        int mm = Integer.parseInt(s.substring(3, 5));
        int ss = Integer.parseInt(s.substring(6, 8));
        int fff = Integer.parseInt(s.substring(9, 12));
        if (hh > 99 || mm > 59 || ss > 59) {
            throw new IllegalArgumentException("時刻が範囲外: " + s);
        }
        return ((hh * 60L + mm) * 60 + ss) * 1000 + fff;
    }
    // parseDistanceDm、isLowSpeed、isNight、calculate は前出の通り
}

Javaコードは、この環境にJDKがなくJVMで実行していない。同じロジックをPython 3.12.3に写し、19件のチェックをすべて確認した。仕様書の具体例(深夜23時から850.0mで490円)と入力例(13:50:08.245からの4行で410円)、初乗りの境界(1052.0mで410円、1052.1mで490円)、低速運賃の境界(90秒で80円、89秒で0円、180秒で160円)、平均速度ちょうど10km/hが低速側になることと10.11km/hでは低速にならないこと、深夜の初乗り境界(841.6mで410円、841.7mで490円)、22時またぎの通算(490円)、25時台の深夜判定(850mで490円)、異常入力6件(1行だけ、1行目が0.0でない、総距離0.0、時刻の逆行、距離が99.9超、時刻の形式不正)の検出である。Javaコードは目視で構文を確認した。

浮動小数点の罠も実測で確認した。0.1 + 0.2 は 0.30000000000000004 になり、0.1を10520回加算すると 1052.0000000001387 になる。1052.0mちょうどの乗車が、doubleの足し上げでは1052.0mを超えてしまう。整数化は好みの問題ではなく、境界の正しさの問題である。

今後見るべきもの

  • TechTrainのミッション仕様の更新。初乗り距離や加算単位、低速のしきい値が変われば、境界のテストケースをすべて作り直す必要がある。
  • 実際のタクシー運賃の改定。初乗り距離や加算単位は地域と時期で変わる。仕様の数字を定数として分離しておくと、改定への追従が楽になる。
  • 深夜時間帯の定義の変更。22時〜翌5時という区間が変われば、深夜判定のメソッドだけを直せばよい設計にしておく。
  • 低速運賃のしきい値(時速10km)と単位時間(90秒)の変更。整数比較の式 dm * 36 <= dtMs は、しきい値と単位時間から導いた式なので、数字が変われば式も変わる。
  • 入力形式の変更。時刻の桁数や距離の単位が変わると、パースとバリデーションの両方に影響する。形式のチェックは1か所に集めておく。

参考資料

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?