質問編集履歴

現状の修正

2020/03/12 06:45

投稿

zenobread

スコア44

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -1,7 +1,5 @@
 ###やりたいこと
-以下の問題を解きたい
 問.以下の問に答えなさい
@@ -120,103 +118,7 @@
 と出力する
-##やったこと(自分なりの考え方)
-最初は道中のガソリンスタンド全て寄ったと仮定し,最後に残っている
-ガソリン量をもとに「よらなくてもいいガソリンスタンド」を算出しようとしたが,
-計算量が多いので断念.
-現在は
-その時車Pが保有しているガソリンで進み、ガソリンスタンドは無視する
-どこか途中でガソリンが足りなくなった場合、まだ補給していない1つ前の
-ガソリンスタンドでガソリンを補給したものとし、車にあるガソリンと合算する。
-それでも足りなければさらにひとつ前のガソリンスタンドでガソリンを補給する、
-ということを繰り返す。
-足りるなら次に進む
-を繰り返す計算をしています
-##抱えている問題(省略可)
+##字数制限の関係で省略
-先程の考えだと、
-例）
-10 2 4
-1 10
-2 3
-3 1
-4 1
-6 1
-この場合
-「2km先のガソリンスタンドで3L補給（現在2km地点で残り3L）.
-6km先のガソリンスタンドまでは足りないので(4km地点で残り1L）
-1つ前の4km地点のガソリンスタンドで1L補給して
-6km先のガソリンスタンドに到着（現在6km地点で0L）.
-目的地まで6km地点のガソリンスタンドからゴールまで4kmある。
-足りないので、6km地点で補給する(現在6km地点で1L)
-それでも足りず3km地点のガソリンスタンドで補給したものとする.（現在6km地点で2L）
-それでも足りないが2，3，4km地点のガソリンスタンドはすでに補給している為
-使用できない.其の為1km地点で10L補給したとする.(現在6km地点で12L)
-ゴールまで4L消費し最終のこっているのは8L」
-となる
-だが「1km地点で補給していれば他のガソリンスタンドで補給する必要はない」ので計算が狂う
@@ -234,38 +136,236 @@
-##ソースコード
+##過去ソースコードは字数削減の為削除しました
+#追記
+miyabi_sunのご回答から
+1、現在の保有量で到達できるスタンドまで進む
+２、到達できないスタンドが見つかれば、一番最後に利用したスタンド（もしくはスタート地点）
+から到達できる最後のガソリンスタンドまでのリストを作成する
+３、そのリストが1つでもあれば一番最後にいた地点からリスト内で最もガソリンを補給できるスタンドまで移動し、
+移動した分のガソリンを引いたのち補給できるガソリンを補給する。そして1に戻る
+４、もし先ほどのリストなければ既に通過したガソリンスタンドかつまだ利用していないガソリンスタンドのリストを作成する
+５、利用していないスタンドのリストが一つでもあれば、リスト内のスタンドでガソリンを補給したこととし
+現在のガソリン量に補給したガソリンを足す。これを最も多くガソリンを補給できるスタンドの中から順に行い、
+現在地から先へ進めるか確かめる。進めるならば3と同じ補給と移動の計算を行い１へ
+６、利用できるスタンドが一つもない、または通過したスタンド全てを利用してしまった場合ループを抜ける
+7、これを目的地に到達するまで行う
+というプログラムを組みましたが、まだエラーが発生しているようです。
 ```python
-#諸事情によりガソリンスタンドをoasisと表現し、ガソリンをwaterと表現しています
-#ガソリンスタンド地点をソートする為自作クラスoasisClassを作っています
 class oasisClass():
-#引数1にはガソリンスタンドまでの距離、引数2にはガソリンスタンドで得られるガソリン量
     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()
@@ -278,13 +378,7 @@
 oasis=int(kyori0_saisyoryo1_oasiskazu2[2])
-#kyori=目的地までの距離 ryo=最初保有しているガソリン量 oasis=道中にあるガソリンスタンドの数
-#入力するガソリンスタンドは順不同なので、リストに入れてソートする
-#最初車に保有するガソリンを表現する為リストの最初に、0kmでryoだけガソリンを獲得する、という風にしている
 pre_oasis_list=[oasisClass(0,ryo)]
@@ -294,140 +388,22 @@
     pre_oasis_list.append(oasisClass(int(input_line[0]),int(input_line[1])))
-pre_oasis_list.append(oasisClass(int(kyori),0))#ゴール地点では0Lのガソリンを獲得する、というふうにしてリストに代入している
+pre_oasis_list.append(oasisClass(int(kyori),0))
-oasis_list=sorted(pre_oasis_list)#スタート、ゴール地点すべて含めた地点リストを距離順にソート
-hokyu_sum=0#補給したガソリンの合計
-hokyu_set=set()#距離set型に保存
-hokyu_list=[]#距離をキーとしてガソリン量を保存
-current_ryo=ryo#現在のガソリン量
-#地点リストごとにループ
-for i in range(0,len(oasis_list)):
-    current_ryo-=oasis_list[i].kyori
-    if i!=0: current_ryo+=oasis_list[i-1].kyori
-    if i!=0 and current_ryo<0:#次の地点へ着いた時点でガソリンがマイナスならさかのぼってガソリンを補給する
-        pre_hokyu=0
-        pre_set=set()
-        pre_list=[]
-        for p in reversed(range(1,i)):
-            current=oasis_list[p]
-            if current.kyori not in hokyu_set:#すでに補給場所に入っていないか
-                if pre_hokyu>current.water:#それまで蓄えたガソリン量と比較して少ないなら補給
-                    #この先でまだまだ補給したり、今まで以上に補給したりする可能性もあるので暫定補給とする
-                    pre_hokyu+=current.water
-                    pre_set.add(current.kyori)
-                    pre_list.append(current)
-                else:#その先で獲得するのと同じかそれ以上の水を獲得した場合
-                    #リセット処理
-                    pre_hokyu=current.water
-                    pre_set={current.kyori}
-                    pre_list=[current]
-                if current_ryo+pre_hokyu>=0:
-                    break
-                else:
-                    if i==1:#最初から補給してもダメならbreak
-                        break
-                    else:
-                        continue
-        if current_ryo+pre_hokyu>0:#余分に補給していないかどうか
-            #余分に補給しているなら捨てる
-            pre_list.sort()
-            for p in pre_list:
-                if current_ryo+pre_hokyu-p.water>=0:#ガソリンを捨ててもマイナスにならないかどうか
-                    pre_set.remove(p)
-                    pre_list.remove(p)
-                    pre_hokyu-=p.water
-                    if current_ryo+pre_hokyu>0:
-                        continue
-                    else:
-                        break
-        #ここで初めて確定処理
-        if current_ryo+pre_hokyu>=0:#きちんと次の地点まで到達できているかどうか
-            #地点に到達できているならループを続行
-            hokyu_set=hokyu_set | pre_set
-            hokyu_list.append(pre_list)
+oasis_list=sorted(pre_oasis_list)
-            hokyu_sum+=pre_hokyu
-            current_ryo+=pre_hokyu
+#input_lineからoasis_list=sorted...まで一緒
-        else:
-            #到達できないならここでループを抜ける
-            current_ryo=-1
-            break
-    else:
-        continue
-if current_ryo>=0:
+current=oasisClass(pre_oasis_list[0].kyori,pre_oasis_list[0].water)#現在地と現在のガソリン量
-    print(current_ryo)
-else:
-    print("ガソリン足りない")
+current_oasis=1#ガソリンスタンド全体のインデックス番号
+oasis_set={oasis_list[0]}#最初のスタート地点を既に利用したものとして保存
+print(looping(current_oasis,oasis_list,current,oasis_set)-1)
 ```
-よろしくお願いします