質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
PHP

PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

Q&A

解決済

3回答

981閲覧

本文に記載のアルゴリズムを実装するためのコードの処理をもっと早くしたい

ryoo_chksl

総合スコア69

PHP

PHPは、Webサイト構築に特化して開発されたプログラミング言語です。大きな特徴のひとつは、HTMLに直接プログラムを埋め込むことができるという点です。PHPを用いることで、HTMLを動的コンテンツとして出力できます。HTMLがそのままブラウザに表示されるのに対し、PHPプログラムはサーバ側で実行された結果がブラウザに表示されるため、PHPスクリプトは「サーバサイドスクリプト」と呼ばれています。

0グッド

0クリップ

投稿2019/02/28 14:29

編集2019/03/03 01:51

下記の要件を満たす関数removeNb($n)を作っています。

  • 引数nは0より大きい数値
  • 1, 2, 3, …, nの中に含まれるいずれか2つの数字をaとbとする。aとbは「1+2+3+...+n-a-b=a*b」を満たす。
  • この関数は最後に、条件を満たすaとbのすべてのペアを配列で返す。[[a1, b1], [a2, b2], ...]というように。a1<a2<...という順番になるように並べる。
  • aとbのペアがなければ空の配列を返す。

なお、引数と返り値のペアの例をあげます。

  • removeNb(100) -> []
  • removeNb(101) -> [[55, 91], [91, 55]]
  • removeNb(102) -> [[70, 73], [73, 70]]

僕は次のようなコードを書きました。

php

1function removeNb($n) { 2 $ans = []; 3 $arr = range(1, $n); 4 $sum = array_sum($arr); 5 foreach($arr as $key => $val) { 6 for($i = $n - 1; $i >= $val; $i--) { 7 if($arr[$i] === $val) {continue;} 8 if($sum - $val - $arr[$i] === $val * $arr[$i]) { 9 $ans = array_merge($ans, array([$val, $arr[$i]])); 10 break; 11 } 12 } 13 } 14 15 if(empty($ans)) return $ans; 16 17 $revans = array_reverse($ans); 18 for($j = 0; $j < count($revans); $j++) {$revans[$j] = array_reverse($revans[$j]);} 19 return array_merge($ans, $revans); 20}

しかし、このコードだと、処理に時間がかかってしまうみたいです。処理が素早く完了するようにコードを改善したいです。ご教授ください。

<追記>
https://www.codewars.com/kata/is-my-friend-cheating/train/php

この問題を解いていました。コードを書いて「ATTEMPT」を押したら、そのコードでお題がクリアできるかどうかが検証されます。処理に時間がかかると処理が中断されてしまいます。僕のコードでも、cerfwebさんのコードでも、処理が途中で中断されてしまいました。「かかってしまうみたい」と表現しているのはこのためです。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

m.ts10806

2019/03/03 01:42

>みたいです 「みたい」「素早く」では実際の目指すところが不明です。具体的に記載してください。 なぜ自身のコードなのに「みたい」と他人事なのでしょうか。
guest

回答3

0

今のコードは、a,b 2つのループがありますが、b は a で表すことができるので、片方のループに寄せることができます。

O(n^2) のままの回答に BA がついちゃったんで追記
[初心者向け] プログラムの計算量を求める方法

O(n^2) を O(n) にしようって回答です。 競技系の問題ではよくある手法です。

投稿2019/02/28 17:37

編集2019/05/18 09:17
退会済みユーザー

退会済みユーザー

総合スコア0

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2019/05/18 09:09

計算量減らせばって回答が全く評価されないとは思わなかった^^;
guest

0

問題文が言ってる通りのことをそのまま書いてもダメでしょう。
算術的に解いてください。そうすれば一発で通ります。

php

1function removeNb($n) { 2 $sum = (1+$n) * $n / 2; 3 $ceil = $n; 4 $ret = []; 5 for($a = 1; $a < $ceil; $a++) { 6 if(($sum - $a) % ($a + 1) !== 0) continue; 7 $b = intdiv($sum - $a, $a + 1); 8 if($b > $n) continue; 9 $ret[] = [$a, $b]; 10 $ret[] = [$b, $a]; 11 $ceil = $b; 12 } 13 array_multisort($ret, array_column($ret, 0)); 14 return $ret; 15}

あとcodewarsのいいところは答えがわかることなんで、答えみましょう。
通ったあとに答えみましたが、だいたいこうやって書いてましたよ。

投稿2019/06/21 08:55

papinianus

総合スコア12705

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

forで回すよりforeachの方が若干ですが早くなるようです。

php

1function removeNb($n) 2{ 3 $ans = []; 4 if ($n > 0) 5 { 6 $arr = range(1, $n); 7 $arr2 = $arr; 8 $sum = array_sum($arr); 9 foreach ($arr as $a) 10 { 11 foreach ($arr2 as $b) 12 { 13 if ($sum - $a - $b == $a * $b) 14 { 15 if ($a != $b) 16 { 17 $ans[] = [$a, $b]; 18 } 19 } 20 } 21 } 22 } 23 24 return $ans; 25} 26

投稿2019/03/01 09:54

編集2019/03/01 09:59
cerfweb

総合スコア1899

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ryoo_chksl

2019/03/03 01:04

処理はうまく進むのですが、まだ遅いみたいです。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問