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

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

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

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

Q&A

0回答

1241閲覧

しゃくとり法を使って、要素の和が M を超えないような A の部分列の最大の長さを求めたい。

karasumaru

総合スコア7

PHP

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

0グッド

0クリップ

投稿2020/10/19 23:51

編集2022/01/12 10:55

前提・実現したいこと

しゃくとり法を使って、要素の和が M を超えないような A の部分列の最大の長さを求めたいのですがうまくいきません。
考えている構造はこのような形です、が、最大の長さがうまくでなくて困っています。
イメージ説明

発生している問題・エラーメッセージ

リンク内容
エラーメッセージは出ないですが区間の最大値と異なる値が出ます。

該当のソースコード

php

1<?php 2 3 /* 4 数列 A の要素数 N と値 M、その要素 A_1, A_2 ... A_N が与えられます。 5 要素の和が M を超えないような A の部分列の最大の長さを求めてください。 6 */ 7 8 //取得 9 $input = explode(" ",trim(fgets(STDIN))); 10 $num = $input[0]; 11 $m = $input[1]; 12 13 $a = explode(" ",trim(fgets(STDIN))); 14 15 16 //累積和を求める 17 $sum[0] = 0; 18 for($i=0; $i<$num; $i++){ 19 $sum[$i+1] = $sum[$i] + $a[$i]; 20 } 21 22 23 //処理 24 25 $ok_flag = false; //reset 26 $right = 1;//区間の右端 27 28 for ($left = 1; $left < $num; $left++) { 29 while($right < $num){ 30 if($sum[$right] - $sum[$left] < $m){ 31 $ok_flag = true; 32 $right++;//右に伸ばせるだけ伸ばす 33 }else{ 34 //右に伸ばせなくなったのでその時点を格納 35 $save[] = $right-$left; 36 break; 37 } 38 } 39 } 40 41 42 //出力 43 if($ok_flag==false){ 44 echo(0); 45 }else{ 46 echo(max($save)); 47 } 48 49 50?>

試したこと

Aが10万個の整数のバリエがあるため、累積和としゃくとり法について調べました。しゃくとり法は区間の左端を固定し右端をのばすということで、区間の右端を伸ばせるだけ伸ばし、伸ばせなくなったら区間数を配列$saveに格納するようにしました。

補足情報(FW/ツールのバージョンなど)

しゃくとり法について調べるきっかけになった問題元はこちらですが、この問題を解きたいというよりしゃくとり法が実装できるように理解したいです。

パイザランクアップ問題集

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

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

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

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

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

karasumaru

2020/10/22 02:09

失礼いたしました。 試したことと、実現したいことに図表などを追加しました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問