Marathon Match 64: StreetSales
概要
過去の事を思い出しながら経過を書き起こしてみる。
序盤
- 問題を読んでみる。大きな要素は経路、商品の個数、値段の3つ。
- どう考えても一番大きな要素は経路。
- まずはpositive scoreが出るようなモノを作ってみる。スコアは2くらい。
- とりあえず個数や値段はかなり適当に決めて、経路の探索を頑張ってみる。
- 各ステップごとに経路を修正するのはstringを扱う関係上時間がかかりそうなので、最初に良い経路を探して決め打ちする。
- 前処理で、各セルに一番近い家と距離を求めておく。
- 一番近い家がまだ訪ねていなければその家を目指し、既に訪ねていれば離れるようにする。
- 離れる方向の選び方は色々あるので若干の乱択性を加える。
- 多スタート法で10回くらい探索するとスコアは10くらい。
- 商品の個数の選び方を変える。10日間で売上が負なら個数を必ず減らし、完売していたら割と高い確率で個数を増やす。
- 探索回数を50回くらいにするとスコアは40くらい。
- 商品の値段を原価+15に設定して探索回数を150万/Sにするとスコアは70くらい。
中盤
- 毎回stringを処理していたのをintで扱うようにした。
- ついでにmake_pairを何度も書くのが面倒なので座標(x,y)をy*width+xで扱うようにする。2次元配列が消えた。
- 速度が上がったので探索回数を1500万/Sまで増やした。
- 最初の300日くらいで商品を買わない家は以後無視する。
- 値段もisolatedな家の率に応じて変化させるとスコアは80over。
- 色々パラメータをいじってみるけどスコア90の壁が厚い。
- 高スコアを出すための方法について再考してみる。
- 積分値がスコアなので、早めに収束させることを考える。
- このあたりでvisualizerでseedに色々な値が使えることに気づく。
- 色々なケースを試していると、クラスタを上手く舐めれていないことに気づく。
- クラスタを規則的に舐める経路を加えてみると90の壁が破れた。
終盤
- またパラメータいじりをするけど、スコア95の壁が破れない。
- 最初の数日は色んな家を訪ねて、商品を買わない家を探索し、それを無視して経路探索するような方法に変える。
- コードを大幅に書き換えたのにスコアが落ちて心が折れかける。
- 何故ダメだったのか実は未だによくわかっていない。
- 一番近い家だけでなく、二番目に近い家も前処理で覚えておくようにする。
- これも失敗。局所解を全部拾いに行くような(比喩)挙動を示してしまった。
- あとはコツコツパラメータでもいじるか。
- よく見たら初期は商品の売れ残りが多い。最初の損はあまり影響ないだろうけど1ptくらいは稼げるかな、と思って実装。これが大当たりでついに95突破。
- あとは本当にパラメータとかの微調整をするだけ、色々試して良さそうなものを選ぶ。
- 最終提出時の順位は4/104。上との差が結構あるので多分これよりはよくならないと思う。
反省
- 弱点は分かっていたけどそれを解消する手段が見つけられなかったのが痛い。
- 弱点1:クラスタ性の低いマップでの経路の選び方が弱い。
- 弱点2:小さいマップではより正確に最適解を選ぶ必要がある。相対評価の怖い所。
- 序盤に力を入れすぎて後半息切れした感がある。
- 下手に乱数を使ってもそんなに良くはならない。そもそも乱数の使い方自体が下手。せめて商品の個数の選び方は焼きなましたほうが良かった。
- standingの見方とかあまり分かってなくて無駄なsubmitを繰り替えした。
- バージョン管理ソフトの使い方の練習にはなった。
- 順位に関してはそれなりに満足だけど、「えっ、こんな適当なのでも結構いけるじゃないか」という感想。
- 今回はレーティング高い人の参加率が低かったというのもあるけど。
- レーティング高い人が参加しなかった理由は単に実装が面倒だったからなのか、スコアに絡む要素が多くて読みにくかったからなのかは、僕には分からない。
#include <iostream> #include <cmath> #include <algorithm> #include <cstdlib> #include <cstdio> #include <vector> #include <string> #include <sstream> #include <numeric> #include <map> #include <queue> using namespace std; class StreetSales{ public: vector<int> warehousePrice; vector<int> qntUb, priceUb, qnt, price, benefits; vector<bool> visited; vector<string> houseToVisit; vector<int> houses, tmpHouses, allHouses; vector<int> houseId, bestHouseId; vector<int> houseToVisitInt; string districtMap; vector<int> visitedTime, houseToNeglect; vector<bool> isVisitedHouse; vector<int> nearestHouse; vector<int> BuyNothingHouse; vector< vector<int> > blockWalkingPath; vector<string> bestAns; vector<bool> isIsolated; int bestBenefit; int isolatedPercent, stopThinkingDay, bonus; int allHouseVisitSpan; int dx[4], dy[4]; int H, W, G, C, S, cmd, cx, cy, nHouse, day, totalItem, h, base; int miniBlockWidth, miniBlockHeight, largeBlockWidth, largeBlockHeight; int largeBlockMinX, largeBlockMaxX, largeBlockMinY, largeBlockMaxY; double houseValue; bool isRotate, rndRotate, backRotate, blockWalk; int init(vector<string> districtMapIn, vector<int> warehousePriceIn, int c, int s){ C = c; S = s; H = districtMapIn.size(); W = districtMapIn[0].size(); G = warehousePriceIn.size(); base = 30000; stopThinkingDay = 800+50*G; warehousePrice = warehousePriceIn; districtMap = ""; for(int i=0; i<H; i++) districtMap += districtMapIn[i]; dx[0] = 1; dx[1] = 0; dx[2] = -1; dx[3] = 0; dy[0] = 0; dy[1] = 1; dy[2] = 0; dy[3] = -1; day = 0; qntUb = vector<int>(G,1<<29); qnt = vector<int>(G,0); priceUb = vector<int>(G,0); price = vector<int>(G,0); benefits = vector<int>(G,0); getHousePosInfo(); checkIsolated(); checkMiniBlock(); checkLargeBlock(); setBlockWalking(); setNearestHouse(); visited = vector<bool>(W*H,false); houseToVisitInt = vector<int>(S+S/5 + 1); int best = 0; double bestVal=0.0; vector<int> tmp; blockWalk = false; isRotate = false; rndRotate = false; backRotate = false; int stp = 10000000/S, change = stp/5, rnd = stp/2, backChange = (change+rnd)/2; for(int i=0; i<stp; i++){ setRoute(); if(bestVal < houseValue){ bestVal = houseValue; best = h; tmp = houseToVisitInt; bestHouseId = houseId; } if(i==change>>1) backRotate = true; if(i==change){ isRotate = true; backRotate = false; } if(i==backChange) backChange = true; if(i==rnd){ rndRotate = true; backChange = false; } } blockWalk = true; isRotate = false; rndRotate = false; backRotate = false; stp = 10000000/S; change = stp/5; rnd = stp/2; backChange = (change+rnd)/2; for(int i=0; i<stp; i++){ setRoute(); if(bestVal < houseValue){ bestVal = houseValue; best = h; tmp = houseToVisitInt; bestHouseId = houseId; } if(i==change>>1) backRotate = true; if(i==change){ isRotate = true; backRotate = false; } if(i==backChange) backChange = true; if(i==rnd){ rndRotate = true; backChange = false; } } for(int i=0; i<best; i++){ tmpHouses.push_back(houses[bestHouseId[i]]); } nHouse = h = best; houses = tmpHouses; isolatedPercent = 0; for(int i=0; i<nHouse; i++){ if(isIsolated[houses[i]]) isolatedPercent++; } isolatedPercent = 100*isolatedPercent/nHouse; bonus = decidePrice(isolatedPercent); houseToVisitInt = tmp; bestBenefit = 0; BuyNothingHouse = vector<int>(nHouse, 0); allHouseVisitSpan = 150; return 0; } void getHousePosInfo(){ houses.push_back(-1); for(int i=0; i<H*W; i++){ if(districtMap[i] == 'X'){ houses.push_back(i); } } allHouses = houses; nHouse = houses.size(); } void checkIsolated(){ isIsolated = vector<bool>(H*W,true); for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ for(int k=0; k<4; k++){ int ny = i + dy[k], nx = j + dx[k]; if(isValidPos(ny,nx) && districtMap[ny*W+nx]=='X'){ isIsolated[i*W+j] = false; break; } } } } } void checkMiniBlock(){ for(int i=0; i<H; i++){ for(int j=0; j<W; j++)if(districtMap[i*W+j] == 'X' && !isIsolated[i*W+j]){ for(int k=0;; k++)if(districtMap[i*W+j+k+1] == '.'){ miniBlockWidth = k+1; break; } for(int k=0;; k++)if(districtMap[(i+k+1)*W+j] == '.'){ miniBlockHeight = k+1; return ; } } } } void checkLargeBlock(){ for(int i=0; i<H; i++){ for(int j=0; j<W; j++)if(districtMap[i*W+j] == 'X' && !isIsolated[i*W+j]){ largeBlockMinX = j; largeBlockMinY = i; for(int k=j+1; k<W; k++)if(districtMap[i*W+k]=='X' && !isIsolated[i*W+k]) largeBlockMaxX = k; for(int k=i+1; k<H; k++)if(districtMap[k*W+j]=='X' && !isIsolated[k*W+j]) largeBlockMaxY = k; largeBlockWidth = largeBlockMaxX - largeBlockMinX + 1; largeBlockHeight = largeBlockMaxY - largeBlockMinY + 1; return ; } } } void setBlockWalking(){ blockWalkingPath.clear(); if(miniBlockHeight==1){ blockWalkingPath.push_back(vector<int>()); int dir = 1; for(int i=largeBlockMinY + miniBlockHeight; i <= largeBlockMaxY+1; i += 4){ if(dir == 1){ for(int j=largeBlockMinX-1; j<=largeBlockMaxX+1; j++){ blockWalkingPath.back().push_back(i*W+j); } if(i<=largeBlockMaxY-3)for(int k=i+1; k<=i+3;k++){ blockWalkingPath.back().push_back(k*W+largeBlockMaxX+1); } } else{ for(int j=largeBlockMaxX+1; j>=largeBlockMinX-1; j--){ blockWalkingPath.back().push_back(i*W+j); } if(i<=largeBlockMaxY-3)for(int k=i+1; k<=i+3;k++){ blockWalkingPath.back().push_back(k*W+largeBlockMinX-1); } } dir *= -1; } blockWalkingPath.push_back(blockWalkingPath.back()); reverse(blockWalkingPath.back().begin(), blockWalkingPath.back().end()); } else if(miniBlockWidth==1){ blockWalkingPath.push_back(vector<int>()); int dir = 1; for(int j=largeBlockMinX + miniBlockWidth; j <= largeBlockMaxX+1; j += 4){ if(dir == 1){ for(int i=largeBlockMinY-1; i<=largeBlockMaxY+1; i++){ blockWalkingPath.back().push_back(i*W+j); } if(j<=largeBlockMaxX-3)for(int k=j+1; k<=j+3;k++){ blockWalkingPath.back().push_back((largeBlockMaxY+1)*W+k); } } else if(dir == -1){ for(int i=largeBlockMaxY+1; i>=largeBlockMinY-1; i--){ blockWalkingPath.back().push_back(i*W+j); } if(j<=largeBlockMaxX-3)for(int k=j+1; k<=j+3;k++){ blockWalkingPath.back().push_back((largeBlockMinY-1)*W+k); } } dir *= -1; } blockWalkingPath.push_back(blockWalkingPath.back()); reverse(blockWalkingPath.back().begin(), blockWalkingPath.back().end()); } else if(miniBlockWidth >= miniBlockHeight){ blockWalkingPath.push_back(vector<int>()); int dir = 1; for(int i=largeBlockMinY + miniBlockHeight; i <= largeBlockMaxY+1; i += miniBlockHeight+1){ if(dir == 1){ for(int j=largeBlockMinX-1; j<=largeBlockMaxX+1; j++){ blockWalkingPath.back().push_back(i*W+j); } if(i<=largeBlockMaxY)for(int k=i+1; k<=i+miniBlockHeight;k++){ blockWalkingPath.back().push_back(k*W+largeBlockMaxX+1); } } else{ for(int j=largeBlockMaxX+1; j>=largeBlockMinX-1; j--){ blockWalkingPath.back().push_back(i*W+j); } if(i<=largeBlockMaxY)for(int k=i+1; k<=i+miniBlockHeight;k++){ blockWalkingPath.back().push_back(k*W+largeBlockMinX-1); } } dir *= -1; } blockWalkingPath.push_back(blockWalkingPath.back()); reverse(blockWalkingPath.back().begin(), blockWalkingPath.back().end()); } else{ blockWalkingPath.push_back(vector<int>()); int dir = 1; for(int j=largeBlockMinX + miniBlockWidth; j <= largeBlockMaxX+1; j += miniBlockWidth+1){ if(dir == 1){ for(int i=largeBlockMinY-1; i<=largeBlockMaxY+1; i++){ blockWalkingPath.back().push_back(i*W+j); } if(j<=largeBlockMaxX)for(int k=j+1; k<=j+miniBlockWidth;k++){ blockWalkingPath.back().push_back((largeBlockMaxY+1)*W+k); } } else if(dir == -1){ for(int i=largeBlockMaxY+1; i>=largeBlockMinY-1; i--){ blockWalkingPath.back().push_back(i*W+j); } if(j<=largeBlockMaxX)for(int k=j+1; k<=j+miniBlockWidth;k++){ blockWalkingPath.back().push_back((largeBlockMinY-1)*W+k); } } dir *= -1; } blockWalkingPath.push_back(blockWalkingPath.back()); reverse(blockWalkingPath.back().begin(), blockWalkingPath.back().end()); } } inline bool isValidPos(int ny, int nx){ return 0<=ny && ny<H && 0<=nx && nx<W; } void setNearestHouse(){ queue< pair<int, int> > Q; nearestHouse = vector<int>(H*W, 0); for(int i=1; i<nHouse; i++){ for(int k=0; k<4; k++){ int ny = houses[i]/W + dy[k], nx = houses[i]%W + dx[k]; if(isValidPos(ny,nx) && districtMap[ny*W+nx]!='X'){ Q.push( make_pair(ny*W+nx, i*base+1) ); } } } while(!Q.empty()){ pair<int,int> tp = Q.front(); Q.pop(); if(nearestHouse[tp.first]/base != 0){ continue; } nearestHouse[tp.first] = tp.second; for(int k=0; k<4; k++){ int ny = tp.first/W + dy[k], nx = tp.first%W + dx[k]; if(isValidPos(ny,nx) && districtMap[ny*W+nx]!='X' && nearestHouse[ny*W+nx]%base==0){ Q.push(make_pair(ny*W+nx, tp.second+1)); } } } } void getCloser(int target){ int yy = cy, xx = cx; for(int k=0; k<4; k++){ int ny = cy + dy[k], nx = cx + dx[k]; if(isValidPos(ny,nx) && nearestHouse[ny*W+nx] == nearestHouse[cy*W+cx]-1){ cy += dy[k]; cx += dx[k]; return ; } } } void getAway(int target){ int yy = cy, xx = cx; int mi = 1<<29, key = -1; for(int k=0; k<4; k++){ int ny = cy + dy[k], nx = cx + dx[k]; if(isValidPos(ny,nx) && districtMap[ny*W+nx]!='X' && visitedTime[ny*W+nx] <= 0){ if(nearestHouse[ny*W+nx]/base != target && mi > nearestHouse[ny*W+nx]%base){ key = k; mi = nearestHouse[ny*W+nx]%base; } else if(key < 0 && nearestHouse[ny*W+nx] == nearestHouse[cy*W+cx]+1){ key = k; } } } if(key>=0){ cy += dy[key]; cx += dx[key]; return ; } if(backRotate){ rotate(dx,dx+1,dx+4); rotate(dy,dy+1,dy+4); } int tmpBest = 1<<29, tmpKey=-1; for(int k=0; k<4; k++){ int ny = cy + dy[k], nx = cx + dx[k]; if(isValidPos(ny,nx) && visitedTime[ny*W+nx] < tmpBest && districtMap[ny*W+nx]!='X'){ tmpKey = k; tmpBest = visitedTime[ny*W+nx]; } } cy += dy[tmpKey]; cx += dx[tmpKey]; return ; } void setRoute(){ h = 0; houseValue = 0.0; houseId.clear(); isVisitedHouse = vector<bool>(nHouse,false); visitedTime = vector<int>(H*W,0); int iso=0, adj=0; int pos=1, rr = rand()%((int)blockWalkingPath.size()); if(!blockWalk){ cmd = rand()%(nHouse-1)+1; if(miniBlockWidth==3 && miniBlockHeight==3){ while(!isIsolated[houses[cmd]]) cmd = rand()%(nHouse-1)+1; } for(int k=0; k<4; k++){ cy = houses[cmd]/W + dy[k]; cx = houses[cmd]%W + dx[k]; if(isValidPos(cy,cx) && districtMap[cy*W+cx] != 'X') break; } } else{ cy = blockWalkingPath[rr][1]/W; cx = blockWalkingPath[rr][1]%W; } houseToVisitInt[0] = cy*W+cx; visitedTime[houseToVisitInt[0]]++; int cnt=0; if(blockWalk){ for(cnt=0;cnt<S+S/5 && pos<(int)blockWalkingPath[rr].size() - 1;cnt++){ int k; for(k=0; k<4; k++){ int ny = cy + dy[k], nx = cx + dx[k]; if(isValidPos(ny,nx) && !visitedTime[ny*W+nx] && !(nearestHouse[ny*W+nx]%base)) break; } if(k<4){ int np = (cy+dy[k])*W+cx+dx[k]; if(cnt<S){ h++; if(isIsolated[np]) iso++; else adj++; } else{ houseValue += isIsolated[np]?1.5:1.0; } houseId.push_back(distance(houses.begin(), lower_bound(houses.begin(), houses.end(), np ))); isVisitedHouse[houseId.back()] = true; houseToVisitInt[cnt+1] = np; visitedTime[np]++; continue; } houseToVisitInt[cnt+1] = blockWalkingPath[rr][++pos]; visitedTime[blockWalkingPath[rr][pos]] += 2; cy = houseToVisitInt[cnt+1]/W; cx = houseToVisitInt[cnt+1]%W; } } for(int i=cnt; i<S+S/5 ;i++){ if(isRotate){ if(rndRotate){ int r = rand()&3; rotate(dx,dx+r,dx+4); rotate(dy,dy+r,dy+4); } else{ rotate(dx,dx+1,dx+4); rotate(dy,dy+1,dy+4); } } int k; for(k=0; k<4; k++){ int ny = cy + dy[k], nx = cx + dx[k]; if(isValidPos(ny,nx) && !visitedTime[ny*W+nx] && !(nearestHouse[ny*W+nx]%base)) break; } if(k<4){ int np = (cy+dy[k])*W+cx+dx[k]; if(i<S){ h++; if(isIsolated[np]) iso++; else adj++; } else{ houseValue += isIsolated[np]?1.5:1.0; } houseId.push_back(distance(houses.begin(), lower_bound(houses.begin(), houses.end(), np ))); isVisitedHouse[houseId.back()] = true; houseToVisitInt[i+1] = np; visitedTime[np]++; continue; } if( !isVisitedHouse[nearestHouse[cy*W+cx]/base] ){ getCloser(nearestHouse[cy*W+cx]/base); visitedTime[cy*W+cx]++; } else{ getAway(nearestHouse[cy*W+cx]/base); visitedTime[cy*W+cx]++; } houseToVisitInt[i+1] = cy*W+cx; } houseValue += sqrt(decidePrice((100*iso)/h))*(iso*1.01+adj); } void resetRoute(){ int pre = nHouse; houseToVisit.clear(); houseToVisit.reserve(1+G+S); for(int i=0; i<nHouse; i++){ if(BuyNothingHouse[i] > allHouseVisitSpan - 4){ houseToNeglect.push_back(houses[i]); } } sort(houseToNeglect.begin(), houseToNeglect.end()); if(day==allHouseVisitSpan){ for(int i=0; i<G; i++){ qnt[i] += max(decideInitQnt(nHouse - (pre - (int)houseToNeglect.size()) ,isolatedPercent), 0); } totalItem = accumulate(qnt.begin(), qnt.end(), 0); for(int i=0; totalItem > C; i = (i+1)%G)if(qnt[i]>0){ qnt[i]--; totalItem--; } } for(int i=0; i<G; i++){ ostringstream os; os << qnt[i] << ' ' << price[i]; houseToVisit.push_back(os.str()); } houses.clear(); int sz = houseToVisitInt.size(); for(int i=0; i<sz && houseToVisit.size()<G+S+1; i++){ if(districtMap[houseToVisitInt[i]]!='X' || !binary_search(houseToNeglect.begin(), houseToNeglect.end(), houseToVisitInt[i])){ if(districtMap[houseToVisitInt[i]]=='X') houses.push_back(houseToVisitInt[i]); ostringstream os; os << (houseToVisitInt[i]/W) << ' ' << (houseToVisitInt[i]%W); houseToVisit.push_back(os.str()); } } sort(houses.begin(), houses.end()); nHouse = houses.size(); BuyNothingHouse = vector<int>(nHouse, 0); return ; } void routeToString(){ int sz = houseToVisitInt.size(); for(int i=0; i<sz && houseToVisit.size()<G+S+1; i++){ ostringstream os; os << (houseToVisitInt[i]/W) << ' ' << (houseToVisitInt[i]%W); houseToVisit.push_back(os.str()); } } inline int decidePrice(int p){ if(G==2) return (p<=1)?16:(p<=10)?17:(p<=60)?18:(p<=70)?19:(p<=80)?20:(p<=85)?21:(p<=90)?22:(p<=95)?23:24; if(G==3) return (p<=20)?18:(p<=35)?19:(p<=40)?20:(p<=60)?21:(p<=75)?22:(p<=85)?23:(p<=90)?24:25; if(G==4) return (p<=20)?19:(p<=35)?20:(p<=50)?21:(p<=70)?22:(p<=80)?23:(p<=90)?24:25; if(G==5) return (p<=10)?19:(p<=25)?20:(p<=40)?21:(p<=60)?22:(p<=70)?23:(p<=85)?24:25; if(G==6) return (p<=5)?19:(p<=15)?20:(p<=30)?21:(p<=45)?22:(p<=60)?23:(p<=85)?24:25; if(G==7) return (p<=15)?20:(p<=45)?21:(p<=55)?22:(p<=65)?23:(p<=85)?24:25; if(G==8) return (p<=10)?20:(p<=25)?21:(p<=45)?22:(p<=60)?23:(p<=80)?24:25; if(G==9) return (p<=3)?20:(p<=25)?21:(p<=40)?22:(p<=55)?23:(p<=75)?24:(p<=90)?25:26; if(G==10) return (p<=20)?21:(p<=45)?22:(p<=50)?23:(p<=65)?24:(p<=85)?25:26; } int decideInitQnt(int add, int p){ int q = add/G; return (p<=30)?(q*3/4):(p<=60)?(q*7/8):(q*9/10); } vector<string> dayTrade(vector<int> visitedHouses){ if(day>stopThinkingDay && !bestAns.empty()){ day++; return bestAns; } vector<int> soldItems(G,0); for(int i=0; i<nHouse; i++){ int res = visitedHouses[houses[i]]; if(res>=0){ soldItems[res]++; benefits[res] += price[res]; } } if(day)for(int i=0; i<G; i++){ qntUb[i] = min(qntUb[i], soldItems[i]); } if(!day){ houseToVisit.clear(); houseToVisit.reserve(1+G+S); for(int i=0; i<G; i++){ price[i] = warehousePrice[i] + bonus; qnt[i] = max(nHouse/G,1); } totalItem = accumulate(qnt.begin(), qnt.end(), 0); for(int i=0; totalItem > C; i = (i+1)%G)if(qnt[i]>0){ qnt[i]--; totalItem--; } for(int i=0; i<G; i++){ ostringstream os; os << qnt[i] << ' ' << price[i]; houseToVisit.push_back(os.str()); } routeToString(); } if(day==1){ for(int i=0; i<G; i++){ qnt[i] = soldItems[i]; } for(int i=0; i<G; i++){ ostringstream os; os << qnt[i] << ' ' << price[i]; houseToVisit[i] = os.str(); } } else if(!(day%5)){ /*reset*/ if(accumulate(benefits.begin(), benefits.end(), 0) > bestBenefit){ bestAns = houseToVisit; bestBenefit = accumulate(benefits.begin(), benefits.end(), 0); } for(int i=0; i<G; i++){ if((benefits[i] < 0 || qnt[i] > qntUb[i]) && qnt[i]>0){ totalItem--; qnt[i]--; } else if(benefits[i] >= 0 && qnt[i] <= qntUb[i] && totalItem<C && (rand()%100)*G<150){ totalItem++; qnt[i]++; } } for(int i=0; i<G; i++){ ostringstream os; os << qnt[i] << ' ' << price[i]; houseToVisit[i] = os.str(); } qntUb = vector<int>(G,1<<29); benefits = vector<int>(G,0); } if(day<2*allHouseVisitSpan){ for(int i=0; i<nHouse; i++){ if(visitedHouses[houses[i]]==-1){ BuyNothingHouse[i]++; } } } if(day==allHouseVisitSpan || day==2*allHouseVisitSpan){ resetRoute(); } for(int i=0; i<G; i++){ benefits[i] -= qnt[i]*warehousePrice[i]; } day++; return houseToVisit; } };