[今日の珂太練習場]-白俊1024

1486 ワード
テキストリンク

質問する



解法


最初に問題を見たとき、アルゴリズムの授業に通っているLIS問題と似ていると思ったので、LIS問題を解くのは、そうではなく、数学の公式を使って解いたものだと思います.
LIS問題は最後の要素の情報を覚えるだけでよいが,この問題では起点の情報を覚える必要がある.
要素は連続しなければならず、長さはL以上でなければならない.
では、nと長さが少なくともL以上の数列を満たす起点を見つけなければならない.
開始点がxの場合、連続数列の終了点はx+Lである必要があります.
では、どうやって出発点を見つけますか?
数列の和式を用いて始点を見つけた.
始点を見つけたら、始点からx+L-1を出力します.
始点xは(n−((i−1)*(i)/2)/iである.
始点が見つかったら、始点からx+L-1までの連続区間の和が所与のNと等しいか否かを比較する関数を呼び出し、Nが等しいか否かを決定する.
その後が正しい場合は、開始点から増加した値を出力します.

コード#コード#

package backjoon;

import java.io.IOException;
import java.util.Scanner;


public class sequence_1024 {
    public static int sumofN(int x,int L){ int sum=0;
        for(int i=0;i<L;i++){
            sum+=x+i;
        }
        return sum;
    }
    public static void main(String[] args) throws IOException {
        int N, L ;
        int x ;
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();
        L=sc.nextInt();
           for(int i=L;i<100;i++) {
               x = (N - ((i - 1) * (i) / 2)) / i;
               if(N==sumofN(x,i)&&x>=0) {
                   for (int j = 0; j < i; j++) {
                       System.out.println(x + j);
                   }
                   break;
               }
               else
               {  System.out.println(-1);}
           }

        }

    }
[Unity] 13. 部屋に入り、部屋生成モデルを作成する
スパルタWebページ開発総合半ホームページ画面