python:(プログラミング問題)ゴールするまでに必要なガソリンの量を求めたい

Question

###やりたいこと

問.以下の問に答えなさい
あるスタート地点からゴール地点まで移動する車(P)がある.

この車の燃費は悪く1km移動するのに必要なガソリンは1Lである.

また途中で寄ることが出来るガソリンスタンドでは,
近年の中東問題の為決められた量のガソリンしか補給できない

この状況をもとに
「ガソリンを必要最低限補給したとき,ゴール地点で残っているガソリン量」
を出力しなさい.

##例
スタート地点からゴールまで10kmあり,最初車Pに入っているガソリンの量は4Lとする.
その道中に
1km地点のガソリンスタンドでは3L
4km地点のガソリンスタンドでは5L
7km地点のガソリンスタンドでは4L
だけ補給できる.

##流れ
1.1km地点のガソリンスタンドまで消費するガソリンは1L.よってこの時車Pに入っているガソリンは3L.
次のガソリンスタンドまでは足りるので,ここでは補給しない

2.4km地点のガソリンスタンドまで消費するガソリンは3L(1km地点のガソリンスタンドから考えて).
この時車Pに入っているガソリンは0L.次のガソリンスタンドまでは足りないので
このガソリンスタンドではガソリンを補給し,現在車Pに入っているガソリンは5L.

3.1km地点のガソリンスタンドまで消費するガソリンは3L(3km地点のガソリンスタンドから考えて).
この時車Pに入っているガソリンは2L.目的地までガソリンは足りないので,
このガソリンスタンドでも補給し現在車Pに入っているガソリンは6L.

4.7km地点のガソリンスタンドから10km地点まで必要なガソリン量は3L.
よってゴール地点に到達した時のこっているガソリンは3L.

よって「ガソリンを必要最低限補給したとき,ゴール地点で残っているガソリン量」は3L.

##但し以下の条件を満たさなければならない
1.目的地までの距離,最初車Pに入っているガソリン量,道中にあるガソリンスタンドの数は
上記例に従うと"10 4 3"
という文字列で入力し,ガソリンスタンドまでの距離,補給できるガソリン量は
上記例に従うと"1 3"
というように入力し,これを先ほど入力したガソリンスタンド数だけ入力する

2.車Pは無限にガソリンを補給できる

3.目的地までの最大距離は10万km,最初保有できるガソリン量は最大1万L,
道中にあるガソリンスタンドは最大1万店舗,
ガソリンスタンドは必ずスタートから目的地までの道中にあり,
各所ガソリンスタンドで補給できるガソリンの最大量は20万Lまでとする.

4.ガソリンスタンドでガソリンを補給する場合は必ず補給できる分だけ全て補給する.
また各ガソリンスタンドで補給できる回数は1回だけ.

5.もし目的地までガソリンがどうしても足りない場合,
"ガソリンが足りませんでした"
と出力する
##字数制限の関係で省略

###求めているもの
できれば自分でソースコードは考えたいので、誠に勝手ですが回答を求めるための
考え方だけご教授いただきたいと思います。

もし私の技術的に難しいものであれば、ソースコード付きで教えていただきたいです。

##過去ソースコードは字数削減の為削除しました

#追記
miyabi_sunのご回答から

1、現在の保有量で到達できるスタンドまで進む

２、到達できないスタンドが見つかれば、一番最後に利用したスタンド（もしくはスタート地点）
から到達できる最後のガソリンスタンドまでのリストを作成する

３、そのリストが1つでもあれば一番最後にいた地点からリスト内で最もガソリンを補給できるスタンドまで移動し、
移動した分のガソリンを引いたのち補給できるガソリンを補給する。そして1に戻る

４、もし先ほどのリストなければ既に通過したガソリンスタンドかつまだ利用していないガソリンスタンドのリストを作成する

５、利用していないスタンドのリストが一つでもあれば、リスト内のスタンドでガソリンを補給したこととし
現在のガソリン量に補給したガソリンを足す。これを最も多くガソリンを補給できるスタンドの中から順に行い、
現在地から先へ進めるか確かめる。進めるならば3と同じ補給と移動の計算を行い１へ

６、利用できるスタンドが一つもない、または通過したスタンド全てを利用してしまった場合ループを抜ける

7、これを目的地に到達するまで行う

というプログラムを組みましたが、まだエラーが発生しているようです。

class oasisClass():
    def __init__(self,kyori,water):
        self.kyori=kyori
        self.water=water
    def __lt__(self,other):
        return self.kyori<other.kyori
    def __repr__(self):
        return repr((self.kyori,self.water))
    #--__repr__まで同じ
    def __eq__(self,other):
        if not isinstance(other,oasisClass):
            return False
        return self.kyori==other.kyori and self.water==other.water
    def __hash__(self):
        return hash(self.kyori)

def looping(current_oasis,oasis_list,current,oasis_set):#前から順に現在地（ガソリンスタンドのインデックス）,ガソリンスタンド全体のリスト（スタート地点とゴール地点も含めた）,現在のスタートからの距離と
                                                        #現在保有しているガソリンの量を示すクラスオブジェクト,補給に使用したガソリンスタンドのset
    loop_break=False
    for p in range(current_oasis,len(oasis_list)):#現在地から
        if current.water+current.kyori>=oasis_list[len(oasis_list)-1].kyori:#目的地につけるか
            oasis_last=oasis_list[len(oasis_list)-1]
            current_oasis=oasis_list.index(oasis_last)
            current.water+=oasis_last.water-(oasis_last.kyori-current.kyori)
            current.kyori=oasis_last.kyori
            return len(oasis_set)
        
        if current.water+current.kyori>=oasis_list[p].kyori:#次のガソリンスタンドまでたどり着けるなら
            continue#さらに次のガソリンスタンドへ
        else:#現在のガソリンではたどり着けないスタンドが見つかったら
            pre_oasis_list=[oasis_list[j] for j in range(current_oasis,p) if current.water+current.kyori>=oasis_list[j].kyori and oasis_list[j] not in oasis_set]
            #現在地点から到達可能地点までのガソリンスタンド
            if len(pre_oasis_list)>0:#現在のガソリンでたどり着けるガソリンスタンドがあれば
                pre_oasis_list2=sorted(pre_oasis_list,key=lambda k:k.water)#ガソリン補給量の多い順にソート
                pre_oasis_last=pre_oasis_list2[len(pre_oasis_list2)-1]
                current_oasis=oasis_list.index(pre_oasis_last)#利用したガソリンスタンドのインデックスを検索
                    #ガソリンスタンドで補給した量からそれまでの距離で引く
                current.water+=pre_oasis_last.water-(pre_oasis_last.kyori-current.kyori)
                #スタート地点からの距離を代入
                current.kyori=pre_oasis_last.kyori
                #利用したガソリンスタンドをsetがたに保存
                oasis_set.add(pre_oasis_last)
                break
                    #ここで次のループに入る
            else:#到達できるところがない場合
                #既に通過したスタンドかつまだ利用していないところから補給する
                pre_oasis_list2=[oasis_list[j] for j in range(1,current_oasis) if oasis_list[j] not in oasis_set]
                pre_oasis_list2.sort(key=lambda u:u.water)
                pre_all=0
                if len(pre_oasis_list2)>0:#まだ補給していないところがあれば
                    for idx,h in enumerate(reversed(pre_oasis_list2)):
                        pre_all+=h.water#他のガソリンスタンドにもよる可能性があるのでいったん貯める
                        if pre_all+current.water+current.kyori>=oasis_list[len(oasis_list)-1].kyori:#ためたガソリンで目的地にまで到達すれば
                            oasis_last=oasis_list[len(oasis_list)-1]
                            current.water+=pre_all#ためたガソリンを補給
                            oasis_set.add(h)#利用したガソリンスタンドとして保存
                            current.water+=oasis_last.water-(oasis_list_last.kyori-current.kyori)
                            current.kyori=oasis_last.kyori
                            current_oasis=oasis_list.index(oasis_last)
                            return len(oasis_set)
                        
                        if pre_all+current.water+current.kyori>=oasis_list[p].kyori:#ためたガソリンで次の目的地にまで到達すれば
                            #それまで貯めたガソリンを貯蓄
                            #利用したスタンドとして保存
                            current.water+=pre_all
                            oasis_set.add(h)
                            #ここからは次の地点に到達したものとして処理
                            current.water+=oasis_list[p].water-(oasis_list[p].kyori-current.kyori)
                            current.kyori=oasis_list[p].kyori
                            current_oasis=oasis_list.index(oasis_list[p])
                            oasis_set.add(oasis_list[p])
                            break
                        elif idx==0:#全てのスタンドを利用しても到達しなければ
                            loop_break=True#全てのループを抜ける
                            break
                        else:#全てのスタンを利用していないが到達していない場合
                            oasis_set.add(h)#利用したスタンドとして保存
                            continue
                    else:
                        break
                else:#全てのガソリンスタンドを既に利用していたら
                    loop_break=True
                    break
                    
    if loop_break==False:#再ループ
        return looping(current_oasis,oasis_list,current,oasis_set)
    else:
        return 0
 

input_line = input()
kyori0_saisyoryo1_oasiskazu2=input_line.split(" ")
kyori=int(kyori0_saisyoryo1_oasiskazu2[0])
ryo=int(kyori0_saisyoryo1_oasiskazu2[1])
oasis=int(kyori0_saisyoryo1_oasiskazu2[2])

pre_oasis_list=[oasisClass(0,ryo)]
for i in range(oasis):
    input_line=input().split(" ")
    pre_oasis_list.append(oasisClass(int(input_line[0]),int(input_line[1])))
pre_oasis_list.append(oasisClass(int(kyori),0))
oasis_list=sorted(pre_oasis_list)
#input_lineからoasis_list=sorted...まで一緒

current=oasisClass(pre_oasis_list[0].kyori,pre_oasis_list[0].water)#現在地と現在のガソリン量
current_oasis=1#ガソリンスタンド全体のインデックス番号
oasis_set={oasis_list[0]}#最初のスタート地点を既に利用したものとして保存
print(looping(current_oasis,oasis_list,current,oasis_set)-1)
                    

Comments

[退会済みユーザー]

「ガソリンを必要最低限補給」というのが良く分からないので教えてください。最初の例で「1km地点で3L補給し、7km地点で4L補給するとゴール地点でのガソリン残量は4+3+4-10=1L」ではなく3Lが正解というのはどの条件によるものでしょうか。

[miyabi-sun]

この問題、ちょっと前提条件がガバガバすぎやしませんか？
・最低限にしたいのはスタンドへ寄った「回数」なのか「給油したリットル」なのか
・移動経路は律儀にスタンドの真横を通過するのか
　スタンドは移動したい経路上にあるとは考え辛く、スタンドに寄るコストが別途かかります
　リッター1キロという昨今の1/20程度しかない欠陥車なら尚更死活問題でしょう
・車のガソリンタンクは普通車で50リットル程度入るが、初期値と最大値は？
　そもそもゴールまで50キロだとして、50リットルのタンクなら補給無しでゴールですね

こんな説明し始める教師がいたら、私が代わりに助走をつけて殴りにいきます。
前提条件の方が100万倍重要なので、可変であるならば「問題により変動する」と明記してください。

というか、前提条件さえ列挙すれば瞬殺ではないでしょうか？

[zenobread]

kichrb3さん、申し訳ありません。私の計算が間違っておりました。正しい正解はそちらの1Lで間違いないです。
miyabi-sunさん、ご回答ありがとうございます。諸事情から問題は改変しておりまして、元々求めていた答えは[ガソリンスタンドに酔った回数]です。
問題により可変の部分は入力部分のところで
目的地までの距離、最初のガソリン保有量、ガソリンスタンドの件数、
そしてガソリンスタンドそれぞれの
スタートからの距離、補給できるガソリンの量
が可変部分です。
それ以外の部分は問題によらず固定なのですが、説明下手で申し訳ありません。こちらの説明でいかがでしょうか

[fana]

回数かよ！
（「ガソリンを必要最低限補給」とだけ言われたら普通は「量」と捉える気がする）

[退会済みユーザー]

給油の回数であれば、プログラミングコンテストチャレンジブックという本のp73にc++での解答が載っています(本の内容なのでここには貼りません)。POJ 2431 Expeditionというプログラム問題を対象にしていますが、ほぼ同じ内容です。"POJ 2431 python"で検索すればいろいろ解答例が出てくると思いますよ。

[Y.H.]

質問のタイトルに思いっきり
「必要なガソリンの量を求めたい」
と記載されてるので・・・

質問本文にも
> この状況をもとに
> 「ガソリンを必要最低限補給したとき,ゴール地点で残っているガソリン量」
> を出力しなさい
と・・・
回数なら質問を編集し変更してください。

Answer 1

i番目のガソリンスタンドの位置をPi、補給可能な量をGiとすると、
i番目のガソリンスタンドに到達可能なのは、i-1番目までのガソリンスタンドで初期値と合わせてPiリットルのガソリンを補給できる場合だけです。
ここで配列DP[i][g]をi番目までのガソリンスタンドで初期値と合わせてgリットルのガソリンを補給可能な時True、そうでないときFalseになるものとすると、
DP[i][g + Gi] = DP[i - 1][g] or DP[i - 1][g + Gi]（ただし g >= Pi )
が成り立ちます。
DP[0]をタンクの初期値だけTrue、そのほかをFalseにしてDP[1]、AbleDP2]と更新していけば、最終的に目的地に到達可能な最小ガソリン量は、目的地がPにあるとしたとき、
x >= P && DP[ガソリンスタンド数][x] == True
を満たす最小のxです。

このまま愚直に実装するとメモリを大量に使う上、無駄な計算に時間がとられますが、DP配列を使いまわすようにしたり、DPの長さをPまで切り詰める（Pに到達可能なガソリンがある状態から補給する必要がない。超えた部分は別途管理する）ようなことをすれば数分~数十分レベルまで実行時間を短くできるでしょう。

ちなみにこの問題は部分和問題の一種のようなので、おそらくこれ以上に効率のいいアルゴリズムはないんじゃないかと思います。本当にこの問題設定であってますか?

---

当初の問題設定だと、ガソリンを補給する量が多すぎても少なすぎてもダメなので、ガソリンをどれだけ補給したか正確に記録しておく必要があります。

DP[i][g + Gi] = DP[i - 1][g] or DP[i - 1][g + Gi]（ただし g >= Pi )

この部分についてですが、
「i番目のガソリンスタンドにたどり着くには、i-1番目までのガソリンスタンドでもっている保有量と等しいかそれ以上(但し保有量の方がガソリンスタンドで補給する量と等しいかそれ以上)」
という意味でしょうか。

なのでDP[i][g + Gi]はぴったりg + Giのガソリンを補給することが可能かどうかを表しています。
右辺を分解すると、DP[i - 1][g + Gi]がi番目のガソリンスタンドを使わない場合で、DP[i - 1][g]がi番目のガソリンスタンドを使わない場合です。（この点最初の式は不正確で、実際にはg + Gi >= Pi and g < Pi の時にはDP[i][g] = DP[i - 1][g]が成り立ちます)

とはいえ最小回数を求めるだけならこの辺は全く関係なく、プライオリティキューをつかって貪欲に補給していくだけで計算可能です。詳しくはPOJ 2431という条件が違うだけの問題が有名なので、その解説を参考にしてください。

Comments

[zenobread]

ご回答ありがとうございます。
ご察しの通り、本当は「回数」を求める問題なのですがそのまま問題を示すことが諸事情でできず、「最低補給回数=最低補給量」になると判断して車とガソリンという演出部分と、最低補給回数部分だけ改変しました。

DP[i][g + Gi] = DP[i - 1][g] or DP[i - 1][g + Gi]（ただし g >= Pi )
この部分についてですが、
「i番目のガソリンスタンドにたどり着くには、i-1番目までのガソリンスタンドでもっている保有量と等しいかそれ以上(但し保有量の方がガソリンスタンドで補給する量と等しいかそれ以上)」
という意味でしょうか。

Answer 2

よくわかりませんが……

例えば最後のスタンドの給油量が4Lで，最後のスタンドからゴールまでの距離が6kmであるとき，
最後のスタンドにたどり着いたときには
最低でも2Lだけのガソリンが車に残っていないとならない．
残り2L以上，且つ，残りガソリン量をなるべく少なくするように，ここまでのガソリン補給方法を考える．
↓
これは，
元の問題から最後のスタンドを取っ払って
さらにゴール位置を「元の問題の最後のスタンドから2kmだけ先の地点」に設定した問題
と等価になるのでは？
↓
であれば，同様に…

…みたいな感じで，問題を次々に小さくしていく的なアプローチはないものでしょうか？

Comments

[zenobread]

返信が遅れておらず失礼いたしました。
そちらの問題の分割を行おうとも考えたのですが、ガソリンの補給量が目的地までの距離に依存せず問題によって可変する為、難しいと判断しました。

Answer 3

コンピューターってのは高速に計算するのが得意なので
全ての経路の通る・通らないのリストを作って、
そこから算出していくのが良いんじゃないですかね？

ヒントにならないようにJavaScriptのコードでふんわり説明します。

const stands = [
  {point: 2, liter: 3},
  {point: 5, liter: 6},
  {point: 8, liter: 4},
];

// choicesというリストをfor文や再帰関数等を使ってなんとか作る
const choices = [
  [], // どこのガソリンスタンドにも寄らずにゴールを目指す
  [{point: 2, liter: 3}], // 2キロ地点のガソリンスタンドだけ寄ってからゴールを目指す
  [{point: 5, liter: 6}],
  [{point: 8, liter: 4}],
  [{point: 2, liter: 3}, {point: 5, liter: 6}],
  [{point: 2, liter: 3}, {point: 8, liter: 4}],
  [{point: 5, liter: 6}, {point: 8, liter: 4}],
  [{point: 2, liter: 3}, {point: 5, liter: 6}, {point: 8, liter: 4}], // 全選択
];

// この条件下ではゴールが出来るのか否かを調べる関数を準備
// pythonで関数を作る時はdef？要調査
// 引数はchoiceだけになっているが、初期のガソリン量、ゴールまでの距離などの引数も計算には必要になる
function isGoal(choice) {
  // choiceには寄るガソリンスタンドの情報が入っている、これをfor文で回しながら調査することになる
  // choice = [{point: 2, liter: 3}, {point: 8, liter: 4}],

  // 初期のガソリン量、タンクの量、途中で力尽きないかを調査する
  // ゴール出来ないならばfalseを返す
  if (reason) return false;

  // 全ての条件をクリアしたらtrueを返す
  return true;
}

// ゴールできる組み合わせのみをピックアップする
const goals = [];
for (const choice of choices) {
  if (isGoal(choices)) goals.push(choice);
}

// 補給回数ならば、補給回数が最も小さいものを選択する
// 今回は寄ったガソリンスタンドのリストなので、リストの要素数で求められる
// JavaScriptならlist.lengthというプロパティを確認すればよいがPythonは下記を参照
// 参考サイト: https://note.nkmk.me/python-list-len/
let result = goals[0].length;
for (const goal of goals) {
  // goal = [{point: 2, liter: 3}, {point: 8, liter: 4}];
  if (result > goal.length) result = goal.length;
}

質問しにきた背景は、スタンドの数は可変なのにスタンド毎にfor文が必要になるやんけ！
これ、もしかして計算することは不可能なんじゃないだろうか？って不安ですよね。
コンビネーション的な二次元配列は一度覚えれば一生役に立つので、
困った時はデータの持ち方を工夫するというアプローチで考えてみてください。

こんな風に「予めどのガソリンスタンドに寄る」か決めておいて、
条件の違うドライバーを沢山用意してよーいどんで走らせられるという、
物量で攻める選択肢が取れるのがプログラミングの良い所です。

for文の中にfor文を作って、更にfor文を作って……とforのネスト構造を見事避ける事に成功できました。
これにより、自分が今何を考えているのかという一つの事に集中出来ますので、バグが出る可能性を劇的に減らす効果があります。

計算量は2のx乗なので、ガソリンスタンド10件ならば1024件ですか。
20件を超えると100万になるので瞬殺はこの辺がギリギリで、30件になると辛いと思います。
ただまぁ競技プログラミングなら兎も角、課題レベルだとそんなやばい条件は指定されないと思います。

---

【おまけ】 最強の回答を考える

計算量にこだわるなら、
人間がどうやったら最も楽に計算出来るかを考え、
その手順をなぞる事が重要です。

例えば、もし人間がこの問題を手計算で解いてくださいと言われたらこうやりますよね？

1. 給油せずにゴール出来るか否かを確認
2. 給油せずに最もゴールに近いガソリンスタンドへ寄る
3. 経路上のガソリンスタンドの内、「最も条件の良いスタンド」で給油
4. 給油後、ゴール出来るか否かを再計算
5. 2-4を繰り返してゴールして答えを求める

最も条件の良いスタンドというのは、
一言で言えば「タンクからガソリンが溢れずに最も沢山給油出来るスタンド」と定義できますね。
タンクサイズの指定が無いなら一番補給出来るリットル数が多いスタンドを脳死で選べば良いですね。

この2-4の手順を繰り返しての所で役に立つのが無限ループと再帰関数です。

これは私が考えた多分最善だろうという解き方であり、
他にもっと効率の良い手法があるかも知れません。
その場その場で考える必要があり、どういうコードを書けば良いかは都度考える必要があります。
この辺を詰めるのが競技プログラミングというジャンルで競技になる程に選択肢があって楽しい分野ではあります。

Comments

[zenobread]

回答ありがとうございます。実はガソリンスタンドの件数は10000件まで考慮せよと言われておりまして、一つ目の方法ではちょっと辛いかと考えています。

ですので今現在別の回答者様が書かれた方法と、miyabi-sunが書かれた2つ目の方法の両方で考えてみます。

Answer 4

こういう流れで補給するしないの組み合わせを全部調べればいいんじゃないでしょうか。

入力
10 1 3
1 1
2 10
3 1

1. (する, する, する)の組み合わせは可能で総補給量は12L、最後に残る量は3L
2. (する, する, しない) の組み合わせは可能で総補給量は11L、最後に残る量は2L
3. (する, しない, X)の組み合わせは(する, しない, する)と(する, しない, しない)を個別に調べるまでもなく不可能
4. (しない, X, Y)の組み合わせも同様に全部不可能

よって最小の補給量は11Lで、その時のゴール地点での残量は2L

追記

ガソリンが足りないパターンが一つ見つかったからといってその後の全部の組み合わせをスキップすることはできないです。全組み合わせをループするというやり方だとちょっとやりづらいかもしれません。

もうちょっと丁寧に書くとこんな感じですかね。
(簡単に書くために、補給するを「1」、補給しないを「0」と略記)
1から始まる組み合わせをスキップできるかを確認する。
11から始まる組み合わせをスキップできるかを確認する。
111の組み合わせを調べる(1.)。
110の組み合わせを調べる(2.)。
10から始まる組み合わせをスキップできるかを確認する(3.)。今回はできるので次の二つの手続きをスキップ。
101の組み合わせを調べる。
100の組み合わせを調べる。
0から始まる組み合わせをスキップできるかを確認する(4.)。今回はできるので残りの手続きを全部スキップ。
01から始まる組み合わせをスキップできるかを確認する。
011の組み合わせを調べる。
010の組み合わせを調べる。
00から始まる組み合わせをスキップできるかを確認する。
001の組み合わせを調べる。
000の組み合わせを調べる。

深さ優先探索が参考になると思います。

Comments

[zenobread]

ご回答ありがとうございます。
そちらの方法ですが、その場合for文で組み合わせ方を回し
途中でガソリンが足りなくなったらbreak,という形になるでしょうか

[zenobread]

追記された部分で理解できました！ありがとうございます