PHPで競プロの平方根の問題に取り組んでみた

皆さまこんにちは、ウチイダユウゴです！

三月中に終息できるかな～と淡く期待していた感染症への対策ですが、まだまだ先行きが見えませんね。

気が滅入ってきますが、こんな時こそ楽しいことを考えるようにしていきたいものです。
ウチイダはC言語の継続的な学習を兼ねて、競技プログラミングをやったりしています。

今回はPHPで競技プログラミングに参加したというお話です。

PHPでatcoderの問題にチャレンジ！
結論から言いましょう…
実行環境
立ちはだかるSqrt Inequality
まとめ：競技プログラミングは、それに適した言語で！PHPは少なくともAtcoderには向かないぽい…

PHPでatcoderの問題にチャレンジ！

年始くらいからPiscine対策も兼ねて、アルゴリズムの勉強のためにatcoderに参加し始めました。

2月までは、Piscine対策だったのでC言語で挑戦していたのですが、
普段使っている言語で挑戦してみようかな～と思いつきました。

ちょうどパナソニックプログラミングコンテスト2020 が開催されるタイミングだったので、
このコンテストはjsとPHPでトライしてみたのです。

結論から言いましょう…

なんだか妙なポイントでつまづきました。
ほかの言語だったらこんな面倒なことは発生しないと思います。

PHPで競プロやるのはイバラの道っぽいので、素直に適した言語を使いましょう！ 😭

実行環境

掲載しているコードは、下記環境で動作させたものになります。
なお、Vagrantを利用した仮想環境です。

CentOS Linux release 7.7.1908 (Core)
PHP 7.3.13 (cli) (built: Dec 17 2019 10:29:15) ( NTS )

立ちはだかるSqrt Inequality

A問題とB問題は、苦労しつつもそこまでドハマリしないで解けました。

続くC問題「Sqrt Inequarlity」。

標準入力から3つの整数a, b, cが与えられるので、

√a + √b < √c

が成り立つかどうかを検証する問題です。

小数部分の誤差で不正解になるだろうなと思いつつ、素直に書いてこんな感じに。

<?php
  /* 標準入力に値を与えるのが面倒なので、コマンドライン引数から受け取る */
  //list($a, $b, $c) = sscanf(fgets(STDIN), "%d %d %d");
  $a = intval($argv[1]); $b = intval($argv[2]); $c = intval($argv[3]);
  if(sqrt($a) + sqrt($b) < sqrt($c))
    print("Yes\n");
  else
    print("No\n");

  return ;
?>

sqrt()で得た平方根を使って計算をしていくという、ごくスタンダードなやり方です。

以下で実行します。

[vagrant@localhost ~]$ php ./SqrtInequality.php 4 9 25
No
[vagrant@localhost ~]$ php ./SqrtInequality.php 4 9 26
Yes

このあたりは意図通り動作していますね。ただしこれで提出するとWAをくらいます。

解説のPDFにもあるケースで試してみると…

[vagrant@localhost ~]$ php ./SqrtInequality.php 249999999 250000000 999999998
No

Noが出力されますが、正しくは

√249999999 + √250000000 < √999999998

になるので、Yesが出力されなければなりません。

何が起こっているのか、途中の値をprintで出力してみます！

<?php

  /* 標準入力に値を与えるのが面倒なので、コマンドライン引数から受け取る */
  //list($a, $b, $c) = sscanf(fgets(STDIN), "%d %d %d");
  $a = intval($argv[1]); $b = intval($argv[2]); $c = intval($argv[3]);

  print("sqrt($a):". "\n");
  print(sqrt($a). "\n");

  print("sqrt($b):". "\n");
  print(sqrt($b). "\n");

  print("sqrt($a) + sqrt($b):". "\n");
  print(sqrt($a) + sqrt($b). "\n");

  print("sqrt($c):". "\n");
  print(sqrt($c). "\n");

  print("\n");

  if(sqrt($a) + sqrt($b) < sqrt($c))
    print("Yes\n");
  else
    print("No\n");

  return ;
?>

出力結果はこちら。

[vagrant@localhost ~]$ php ./SqrtInequality.php 249999999 250000000 999999998
sqrt(249999999):
15811.388269219
sqrt(250000000):
15811.388300842
sqrt(249999999) + sqrt(250000000):
31622.776570061
sqrt(999999998):
31622.776570061

No

ああ、思った通りですね～(ﾟДﾟ;)
誤差のせいで結果が等しくなってしまいました。

何らかの方法で、小数の精度を上げる必要があります。

precision ディレクティブでsqrt()の結果の精度を高める

PHPは変数の方がないので、longなどで取り扱う小数の桁数を調整できません。

どうしたらいいのかなあとググってみると、マニュアルのsqrt()のページにこんな記述が。

小数点以下の精度は、precision ディレクティブの設定に依存します
PHP: sqrt – Manual より引用

こちらのページによると、取り扱う小数の桁数を指定できる項目がpnp.iniの中にあるようです。

これを使ってみることにします。冒頭にini_set()を追記です。

<?php

  //precisionの設定を変更
  ini_set('precision', 43);

  /* 標準入力に値を与えるのが面倒なので、コマンドライン引数から受け取る */
  //list($a, $b, $c) = sscanf(fgets(STDIN), "%d %d %d");
  $a = intval($argv[1]); $b = intval($argv[2]); $c = intval($argv[3]);

  print("sqrt($a):". "\n");
  print(sqrt($a). "\n");

  print("sqrt($b):". "\n");
  print(sqrt($b). "\n");

  print("sqrt($a) + sqrt($b):". "\n");
  print(sqrt($a) + sqrt($b). "\n");

  print("sqrt($c):". "\n");
  print(sqrt($c). "\n");

  print("\n");

  if(sqrt($a) + sqrt($b) < sqrt($c))
    print("Yes\n");
  else
    print("No\n");

  return ;
?>

結果はこちらです。

[vagrant@localhost ~]$ php ./SqrtInequality.php 249999999 250000000 999999998
sqrt(249999999):
15811.38826921912004763726145029067993164062
sqrt(250000000):
15811.38830084189612534828484058380126953125
sqrt(249999999) + sqrt(250000000):
31622.77657006101799197494983673095703125
sqrt(999999998):
31622.77657006101799197494983673095703125

No

おおっ、桁数めっちゃ増えた…けど加算後は等しくなってる！？(ﾟДﾟ;)

ちなみに、precisionで指定する値をこれ以上大きくしても、sqrt()の計算結果は変わりませんでした。

bcadd()で加算時の精度を高める

$aと$bの平方根はいい感じに計算できているので、どうやら加算のときに精度が下がっているようです。

マニュアルを見てみると、bcadd()なる関数がありました。

任意の精度で加算を行ってくれるみたいです。これを使ってみます。

<?php

  //precisionの設定を変更
  ini_set('precision', 43);

  /* 標準入力に値を与えるのが面倒なので、コマンドライン引数から受け取る */
  //list($a, $b, $c) = sscanf(fgets(STDIN), "%d %d %d");
  $a = intval($argv[1]); $b = intval($argv[2]); $c = intval($argv[3]);

  print("sqrt($a):". "\n");
  print(sqrt($a). "\n");

  print("sqrt($b):". "\n");
  print(sqrt($b). "\n");

  //加算処理にbcadd()を使用する                                                                                           
  print("bcadd(sqrt($a), sqrt($b), 43)". "\n");
  print(bcadd(sqrt($a), sqrt($b), 43). "\n");

  print("sqrt($c):". "\n");
  print(sqrt($c). "\n");

  print("\n");

  if(bcadd(sqrt($a), sqrt($b), 43) < sqrt($c))                                                                              print("Yes\n");
  else
    print("No\n");

  return ;
?>

それでは実行です！

[vagrant@localhost ~]$ php ./SqrtInequality.php 249999999 250000000 999999998
sqrt(249999999):
15811.38826921912004763726145029067993164062
sqrt(250000000):
15811.38830084189612534828484058380126953125
bcadd(sqrt(249999999), sqrt(250000000), 43)
31622.7765700610161729855462908744812011718700000
sqrt(999999998):
31622.77657006101799197494983673095703125

Yes

おおーっ、できた！

不等号の判定もクリアし、Yesが出力されています。

高精度の計算を行う際は、演算子でなく関数を使う必要があるいうことですね…覚えておこう。

提出をしてみる…が実行時エラー！？

最終的に整えたコードはこちらです。

<?php
  ini_set('precision', 43);

  list($a, $b, $c) = sscanf(fgets(STDIN), "%d %d %d");
  if(bcadd(sqrt($a), sqrt($b), 43) < sqrt($c))
    print("Yes\n");
  else
    print("No\n");

  return ;
?>

よーし、これで提出！
してみたのですが…結果はRE（実行時エラー）でした(´；ω；`)

コードテストでエラーを見てみると…

PHP Fatal error: Uncaught Error: Call to undefined function bcadd() in /imojudge/Main.php:5

bcadd()使えないんかーーい！

上記のエラーコードを調べてみたところ、bcmathというパッケージをインストールしていないと、bcadd()などの関数が使えないとのことでした…

マニュアルにも、インストールが必要とちゃんと書いてありました。

atcoderのテストサーバのPHPには、bcmathが含まれていないようです。

Cなんかだと、必要なライブラリは#includeで導入できますから、こういう問題で苦しまなくて済みそうです。

変数の型がないことも含めて、PHPは競技プログラミングに向いてないのかもしれません…

平方根を計算せずに解けばいいじゃない

ちなみに、この問題はPHPでACすることはできないのか？というと、そんなことはありません。

解説のPDFにもある通り、求められている不等式を展開して平方根がない形にすればACできます。

<?php
  list($a, $b, $c) = sscanf(fgets(STDIN), "%d %d %d");

  if($c-$a-$b < 0)
    print("No");
  else{
    if(($c-$a-$b)*($c-$a-$b) > 4*$a*$b)
      print("Yes");
    else
      print("No");
  }
?>

上記のコードでACの判定になりました。

まとめ：競技プログラミングは、それに適した言語で！PHPは少なくともAtcoderには向かないぽい…

そうはいっても、そもそもほかの言語では可能な「平方根を計算してAC判定を得る」、
ひいては「小数を精度高く計算する」のができない、という点では大きなハンデです。

今回は、小数を扱わずに解く方法があったからよかったものの。。。

問題が違えば、それこそ「PHPではACできない」という場合も、ありえなくはないのでしょう…
無理せず変数の型がある言語を使うほうがよさそうです(;´･ω･)

今後、Atcoderの判定サーバで、bcadd()使えるようにならないですかね？
これが使えれば改善されるんだけどな～

ちなみに、JavaScript(node.js)でもやってみましたが同じ部分でコケました。
っていうか非同期IOだから、なおさらやりづらいです。。。

適材適所、場面に応じて対応できるように複数の言語やっておいたほうがよいですね！
競技プログラミング向けに、PythonやRubyを勉強してみようかなあ…

ウチイダはあきらめてしまいましたが、PHPで挑み続ける方には最大限の敬意を表します！

以上、本日はここまで。

最後までお読みいただきありがとうございました(/・ω・)/