スポンサーリンク

AtCoderをJavaScriptで挑むのは厳しいと思った

スポンサーリンク
AtCoderをJavaScriptで挑むのは厳しいと思った JavaScript
スポンサーリンク

スポンサーリンク

AtCoderをJavaScriptで挑むのは厳しい

これまでJavaSriptでAtCoderに挑戦し続けてきたが、流石に厳しいかもしれない…
というのも、言語の構造的に限界があると感じたからです。

↑ ※誤解を招く表現だと思うので、丁寧に解説します。

理由

JSをディスっている訳ではありません。
JSは、文法(ECMA2015〜)はモダンで汎用性も高く好きな言語の1つです。
それだけにAtCoderで利用する上で残念なポイントがいくつかあります。

その1つがNumber型の限界です。

2019/06/22のABC131のC問題ではこのNumber型の限界に引っかかり解けませんでした。
ABC131については下で解説します。

考察があっているにも関わらず、WAになる瞬間が一番辛いですね…

Number型のお話

Number.MAX_SAFE_INTEGER
Number.MAX_SAFE_INTEGER 定数は、JavaScript において正確に扱える最大整数値(253 - 1)を表します。

MDNの解説にもあるように、JSのNumber型で正確に数字を扱える最高値は9007199254740991と決まっています。理由はJSがIEEE754で決められた倍精度浮動小数点型数値を使用し、-(2^53 – 1)〜(2^53 – 1)の数を表現するからです。安全ではない範囲の数字を利用すると、正確な計算をしなくなります。
例えば次のコードはtrueと評価されます。

Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2
// true

Chromeではこの範囲を超えた値を利用できるようにbigIntという仕組みを提供しています。
BigIntはプリミティブ型になるそうです。

しかしながら、nodejs(5.12) AtCoderで使用されているバージョンでは利用できませんでした。

/imojudge/Main.js:2
var x = BigInt(10000000000000000000000000)
        ^

ReferenceError: BigInt is not defined
    at Object. (/imojudge/Main.js:2:9)
    at Module._compile (module.js:413:34)
    at Object.Module._extensions..js (module.js:422:10)
    at Module.load (module.js:357:32)
    at Function.Module._load (module.js:314:12)
    at Function.Module.runMain (module.js:447:10)
    at startup (node.js:148:18)
    at node.js:405:3

この問題をクリアするためには、大きな値を使えるようなモジュールをnpmから引っ張ってくるか自前で実装するしかないと思います。

最後に

同じようなスクリプト言語であるPHPやPythonでは、ほぼ同じロジックでクリアしている方が何人もいるにも関わらず、JSは壊滅的でした。

そもそもJSの母集団が〜

クリアするためには大きな整数を扱えるモジュールを圧縮して持ち込むしかないようでした。演算子が使えないような仕組みを用いてまでJSを使うのであれば、他の言語に乗り換えようかなと思います。

やっぱり数値計算に適していると言われるPythonであれば、整数型がlongで大きな値を扱えるので乗り換え先として良いんじゃないでしょうか。

と言いつつ、また次もJSで参加していると思います。

ABC131

整数 A,B,C,D が与えられます。A 以上 B 以下の整数のうち、C でも D でも割り切れないものの個数を求めてください。

1 <= A <= B <= 10^18

1 <= C, D <= 10^9

A B C Dは全て整数

入力例

314159265358979323 846264338327950288 419716939 937510582

出力例

532105071133627368

提出したコード

"use strict"
function main(arg) {
    arg = arg.trim().split("\n")[0].split(" ").map(Number)
    let A = arg[0]
    let B = arg[1]
    let C = arg[2]
    let D = arg[3]
    let M = lcm(C, D)
    let cStart = A
    let dStart = A
    let mStart = A
    let cEnd = B
    let dEnd = B
    let mEnd = B
    if (A % C !== 0) {
        cStart = A + (C - (A % C))
    }
    if (A % D !== 0) {
        dStart = A + (D - (A % D))
    }
    if (A % M !== 0) {
        mStart = A + (M - (A % M))
    }
    if (B % C !== 0) {
        cEnd = B - (B % C)
    }
    if (B % D !== 0) {
        dEnd = B - (B % D)
    }
    if (B % M !== 0) {
        mEnd = B - (B % M)
    }
    let cAns = (cEnd - cStart) / C + 1
    let dAns = (dEnd - dStart) / D + 1
    let mAns = (mEnd - mStart) / M + 1

    let tAns = cAns + dAns - mAns
    let ans = B - A - tAns + 1
    console.log(ans)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
 
function lcm(a,b) {
    var g = (n, m) => m ? g(m, n % m) : n
    return a * b / g(a, b)
}

Number型の最大値を越えると計算に誤差が生じてしまいました。
PHP7ではうまくいくんですけどね()

JavaScriptPyhton競技プログラミング雑談
スポンサーリンク
スポンサーリンク
スポンサーリンク
404 Motivation Not Found
タイトルとURLをコピーしました