効率のいいエネルギー消費

Question

（問題)二つの正の整数値(a と b とする)が与えられる。それに対して以下に示す処理を
行うプログラムを作成したい。
B君が、前向きに aメートルを、ジャンプしながら移動しようとしてい
ます。
B君が最も効率良くジャンプできる距離はbメートルであり、1回のジャンプ
で、エネルギーを 1 単位しか消費しません。
B君は、正の整数値であれば、いかなる距離でもジャンプすることができますが、
ジャンプした距離をj としたとき、
1 + (j–b)^2
のエネルギーを使用することになります。
移動中のジャンプに使ったエネルギーの和が最も小さくなるような方法で、B君が
aメートル移動するとき、そのエネルギーの和が何単位なのか出力しなさい。
なお、B君は前以外の向きに飛んだり、途中で向きを変えることはできません。

(質問)エネルギー1単位しか消費しない時の計算はできたのですが、その後に手をつける場所がわからなくなってしまって、ヒントなどいただけると嬉しいです

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        int a=sc.nextInt();
        int b=sc.nextInt();
        int j=a%b;
        int energy=1+((j-b)*(j-b));
        if(a%b==0){
            System.out.println(a/b);
        }else if(a%b>b/2){//ここからの書き方がわからないです
            System.out.println((a/b)+((a%b)*energy));
        }
    }
}

Comments

[hoshi-takanori]

a / b の余りを j として、1 + (j–b)^2 の式に当てはめれば良いのでは。(…と思ったけど、余りが商の 1/2 以下の場合は一気にジャンプしたほうがいいのかも…。)

というか、この問題、考え方として、
・数学的に正しい計算方法を考えて (かつ照明もして) それを実装する (これだとほぼ数学の問題)
・候補となりうる値をいくつか計算して、その中から最小値を選ぶ (こっちの方が計算機の問題っぽい)
の 2 通りあるけど、出題者の意図はどっちだろう…。

[dodox86]

> その後に手をつける場所がわからなくなってしまって、

コード上での書く場所、書き方が分からないのではなく、考え方（解法）が分からない、ということではありませんか。bメートルの最大値などの制約条件が分かりませんが、愚直に総当たりで計算しても、O(n)で求められる気がします。当問題の引用元やテストケースなどを提示すると、回答が得やすくなると思います。

[dodox86]

質問のタグに「アルゴリズム」を付けると、より広く適切な回答を得られる可能性が高くなりそうです。

Answer 1

数式をいじれば以下のことがわかります。

• 最適なジャンプの仕方ではジャンプした距離の最大値と最小値の差は1以下になる。

差が2以上離れた二つのジャンプがあるとき、距離の長いほうを-1、短いほうを+1することで総距離を変えずにコストを下げることができます。
これからジャンプの回数を決めれば、その回数での最小コストとその飛び方がわかります。

• ジャンプ距離の最小値がb以上であるようなジャンプ回数がわかっているとき、そこからジャンプの回数を減らしてもコストは減少しない。

「最小ジャンプ距離以上であるようなジャンプ距離を1増やした時のコストの増加分×最小ジャンプ距離」が「最小ジャンプ距離のコスト」以上なのでわかります。

• ジャンプ距離の最大値がb以下であるようなジャンプ回数がわかっているとき、そこからジャンプの回数を増やすとコストが増加する。

これも同様です。

これだけわかれば調べるべき飛び方は2パターン(最小値がb以上であるような飛び方のうち飛ぶ回数が最大のものと最大値がb以下であるような飛び方のうち飛ぶ回数が最小のもの)です。(間違ってるかもしれないので一応ご自分でも証明してください）
この問題はどうにかなりますが、こういう問題はパラメーターのサイズ次第で適したアルゴリズムが変わるのでそれもあったほうがいいです。

Answer 2

aメートル先に到達する最後のジャンプの直前にいた場所をiメートル先とすると、
iは0からa-1までのいずれかの値になります。

直前の場所がiメートル先の場合の最小コストは、
何回かジャンプしてiメートル先に到達する際の最小コストと、
そこからaメートル先にジャンプするための1+(a-i-b)^2のコストとの和となります。

iは0からa-1なので、この範囲で変化させて上記のコストを計算し、最小のものを見つければ、
それがaメートル先に到達する際の最小コストということになります。

iメートル先に到達する最小コストの計算には、自分自身の計算を流用できます。(再帰呼び出し)

ただ、上記計算をそのまま実装すると非効率なので、何らかの工夫が必要でしょう。