結城浩の「マヨイドーロ問題」

PHP

CodeIQで実施されていた結城浩さんの「マヨイドーロ問題」はなんとかPHPで100％正解が取れた。
漸化式は求められなかったが、何パターンか図示して思いついたコードで解くことができた。
反省も兼ねてコードを晒してみる。


最初に思いついたのはこちら。これで行けかもとおもいきや、N($line)が増えるとタイムアウトしてしまう。

<?php
while($line=fgets(STDIN))
{
    $line = rtrim($line);
    if (preg_match('/\D/', $line)) {
        echo 'OUT';
        break;
    }
    $line = intval($line);
    if (($line % 2) == 1) $line++;
    $line /= 2;
    $tm = time();
    echo (b($line) + c($line)) . "\n";
//    echo "tm:" . (time()-$tm) . "\n"
}

function b($x) {
  if ($x <= 1) return $x;
  if ($x == 2) return 3;
  return 1 + b($x-1) + c($x-1);
}

function c($x) {
  if ($x <= 1) return $x;
  if ($x == 2) return 4;
  return 1 + b($x-1) + 2 * c($x-1);
}
?>


高速化のため、関数b()、c()の計算結果をグローバル配列にセットしたところタイムアウトは防げるようになったが、数値表記が指数を使ったものになり、Nが増えた時の答えが不正解になる。

<?php

$br = array(0, 1, 3);
$cr = array(0, 1, 4);

while($line=fgets(STDIN))
{
    $line = rtrim($line);
    if (preg_match('/\D/', $line)) {
        echo 'OUT';
        break;
    }
    $line = intval($line);
    if (($line % 2) == 1) $line++;;
    $line /= 2;
    $tm = time();
    echo (b($line) + c($line)) . "\n";
//    echo "tm:" . (time()-$tm) . "\n"
}

function b($x) {
    global $br, $cr;
    if (array_key_exists($x, $br)) return $br[$x];
    $ret = 1;
    if (array_key_exists($x-1, $br)) {
        $ret += $br[$x-1];
    } else {
        $t = b($x-1);
        $br[$x-1] = $t;
        $ret += $t;
    }
    if (array_key_exists($x-1, $cr)) {
        $ret += $cr[$x-1];
    } else {
        $t= c($x-1);
        $cr[$x-1] = $t;
        $ret += $t;
    }
    $br[$x] = $ret;
    return $ret;
}

function c($x) {
    global $br, $cr;
    if (array_key_exists($x, $cr)) return $cr[$x];
    $ret = 1;
    if (array_key_exists($x-1, $br)) {
        $ret += $br[$x-1];
    } else {
        $t = b($x-1);
        $br[$x-1] = $t;
        $ret += $t;
    }
    if (array_key_exists($x-1, $cr)) {
        $ret += 2 * $cr[$x-1];
    } else {
        $t= c($x-1);
        $cr[$x-1] = $t;
        $ret += $t;
    }
    $cr[$x] = $ret;
    return $ret;
}
?>


更に、結果を任意の精度で求めらるように「BCMath 任意精度数学関数」を使うことで100%正解になった。

<?php
$br = array('0', '1', '3');
$cr = array('0', '1', '4');

while($line=fgets(STDIN))
{
    $line = rtrim($line);
    if (preg_match('/\D/', $line)) {
        echo 'OUT';
        break;
    }
    $line = intval($line);
    if (($line % 2) == 1) $line++;
    $line /= 2;
    $tm = time();
    echo bcadd(b($line), c($line)) . "\n";
//    echo "tm:" . (time()-$tm) . "\n";
}

function b($x) {
    global $br, $cr;
    if (array_key_exists($x, $br)) return $br[$x];
    $ret = '1';
    if (array_key_exists($x-1, $br)) {
        $ret = bcadd($ret, $br[$x-1]);
    } else {
        $t = b($x-1);
        $br[$x-1] = $t;
        $ret = bcadd($ret, $t);
    }
    if (array_key_exists($x-1, $cr)) {
        $ret = bcadd($ret, $cr[$x-1]);
    } else {
        $t= c($x-1);
        $cr[$x-1] = $t;
        $ret = bcadd($ret, $t);
    }
    $br[$x] = $ret;
    return $ret;
}

function c($x) {
    global $br, $cr;
    if (array_key_exists($x, $cr)) return $cr[$x];
    $ret = '1';
    if (array_key_exists($x-1, $br)) {
        $ret = bcadd($ret, $br[$x-1]);
    } else {
        $t = b($x-1);
        $br[$x-1] = $t;
        $ret = bcadd($ret, $t);
    }
    if (array_key_exists($x-1, $cr)) {
        $ret = bcadd($ret, bcmul($cr[$x-1], '2'));
    } else {
        $t= c($x-1);
        $cr[$x-1] = $t;
        $ret = bcadd($ret, $t);
    }
    $cr[$x] = $ret;
    return $ret;
}
?>


こちらは中１の息子がJavaScriptで作ったコード。
ブラウザ上で動くJavaScriptしか馴染みがなく、標準入力って何？という状態であったので、CodeIQにあった node.js のサンプルを教えてみた。漸化式まで作っていたのでコードがシンプルだが、Nが大きくなった時に指数表示される問題は解決できず。

process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function (chunk) {
    var lines = chunk.toString().split('\n');
    var N = lines.length;
//    for (var i = 0; i < lines.length; i++) {
        console.log(a(lines[0]));
//    }
});

function a(N)
{
	var P = 0;
	var B = 1;
	var C = 1;
	var ALL = 0;
    if (N==0) return 0;
	if (N%2 == 1){
		N++
	}
	N /= 2
	for (var i = 0; i < N; i++) {
		P = B+C
		ALL += B+C
		B = P
		C += B
	}
    return ALL;   
}