SRM diary(Sigmar)

SRM479 Div1 250 TheCoffeeTimeDivOne

SRM479, Div1 | 13:02 |

Problem Statement

問題を見る

→問題が長い

→何か実装が面倒な問題

→nが4500万くらいだからnaiveにシミュレーションで何往復もするとTLEしそうだ

→前の座席から7席ずつ一気に進んでいくシミュレーションを記述する

→最初だけ、7で割った余りの席数進む必要があるな・・でも、サンプルで対応しているからチャレンジはできなさそう

→サンプル合う

→提出

→書き方で悩みすぎて25分くらいかかった

チャレンジフェーズ

→何か1からnまで1歩ずつシミュレーションしている人がいる。TLEするんじゃないのか・・

→大きいケースを投げる→失敗

→ああ・・そうか、別に1歩ずつのシミュレーションでも、コーヒーメーカーに戻るところを省略すれば全然間に合うのか・・チャレンジが適当すぎた。。。

→他の人を見ると、ほとんどが後ろからシミュレーションしてる。後ろからだと、余りを計算してとかごちゃごちゃしたことを書かなくて良いのか・・・うーむ・・・

システムテスト

→Failed

→なんで・・(T-T)

終了後

→よく見たら、必要なbreak文が1つ抜けている

→これは気づかない・・きっと、for文の中で終了条件用の変数を更新するという行為が危険だということなんだろうな。。

以下、修正したソースです。

class TheCoffeeTimeDivOne {
public:
	long long find(int n, vector <int> tea) {
		long long res=n*4LL;
		ll tsz=tea.size();
		ll csz=n-tsz;

		sort(tea.begin(), tea.end());
		int rem=tsz%7;
		if(rem>0) res+=47+tea[rem-1]*2LL;
		for(int i=rem+6; i<tsz; i+=7) {
			res+=47+tea[i]*2LL;
		}

		rem=csz%7;
		int tid=0;
		if(rem>0) {
			while(tid<tsz && tea[tid]<=rem) {
				tid++;
				rem++;
			}
			res+=47+rem*2LL;
		}
		for(int i=rem+7; i<=n; i+=7) {
			while(tid<tsz && tea[tid]<=i) {
				tid++;
				i++;
			}
			if(i>n) break;//抜けてた文
			res+=47+i*2LL;
		}
			
		return res;
	}
};

SRM479 Div1 500 TheAirTripDivOne

SRM479, Div1 | 13:02 |

Problem Statement

問題を見る

→いかにも二分探索な予感がする

→OKNGの判定は・・どう見てもダイクストラでできそう

→あまりに簡単に方針にたどり着いてしまったんだが本当にこれで大丈夫なのか・・・

→うーん・・大丈夫だな・・

→書く

→色々間違ってる

→色々直す

→残り1分でサンプル合う

→提出

→サンプルは合ったけど、またぎりぎりになってしまったが大丈夫なのか・・

チャレンジフェーズ

→うーん・・みんな同じような方針に見えるなあ

→何もせず

システムテスト

→Failed

→え・・・(T-T)

→total-25点とか・・酷い・・・

終了後

→あれ

→これ、同じ路線のフライトは複数ある場合もあるよね（サンプルにもある）

→問題文読んでるときにも気をつけないとって思ったポイントだ

→コーディングするときには完全に抜けていた

→こういうのを気づいたときにメモにでも書き留めておかないと、ダメだな・・・

以下、修正したソースです。

vector <int> strspltoi(string str, const char delim) {
    vector <int> result;
    int ssize=0, prev=-1;
	int tmp;
    string tmps;

	if(str.empty()) return result;
    ssize=str.size();

    for(int i=0; i<ssize; i++) {
        if(str[i]==delim) {
			if(i==prev+1) {prev=i; continue; }
			stringstream ss;
			ss << str.substr(prev+1, i-prev-1);
			ss >> tmp;
			result.push_back(tmp);
            prev=i;
        }
    }
	if(prev<ssize-1) {
		stringstream ss;
		ss << str.substr(prev+1, ssize-prev-1);
		ss >> tmp;
		result.push_back(tmp);
	}

    return result;
}

vector <string> strspl(string str, const char delim) {
    vector <string> result;
    int i=0, ssize=0, prev=-1;
    string tmps;

    ssize=str.size();

    for(i=0; i<ssize; i++) {
        if(str[i] == delim) {
            tmps.assign(str, prev+1, i-prev-1);
            result.push_back(tmps);
            prev=i;
        }
    }
    tmps.assign(str, prev+1, ssize-prev-1);
    result.push_back(tmps);

    return result;
}

vector <vector <int> > f;
vector <ll> val;
vector <ll> dad;
vector <map <int, vector <vector <int> > > > adj;
const ll unseen=2000000000;
const ll INF=2000000000;

class TheAirTripDivOne {
public:
	void visit(int k, int safe) {
		int m;
		priority_queue <pair <ll, int> > pq;
		pair <ll, int> qt;
		map <int, vector <vector <int> > >::iterator mit;

		val[k]=0; dad[k]=k;
		qt.first=0; qt.second=k;
		pq.push(qt);
		while(!pq.empty()) {
			qt=pq.top(); pq.pop();
			m=qt.second;
			if(val[m]<-qt.first) continue;
			for(mit=adj[m].begin(); mit!=adj[m].end(); mit++) {
				int i=mit->first;
				vector <vector <int> > wvv=mit->second;
				ll w=INF;
				for(int i=0; i<(int)wvv.size(); i++) {
					ll rem;
					if(val[m]<wvv[i][0]) rem=wvv[i][0]-val[m];
					else {
						rem=(val[m]-wvv[i][0])%wvv[i][2];
						if(rem>0) rem=wvv[i][2]-rem;
					}
					w=min(w, safe+rem+wvv[i][1]);
				}
				if(val[i]>val[m]+w) {
					val[i]=val[m]+w; dad[i]=m;
					qt.first=-val[i]; qt.second=i;
					pq.push(qt);
				}
			}
		}
	}

	int find(int n, vector <string> flights, int time) {
		int res;
		string s;
		vector <string> ft;

		f.clear();
		adj.clear();
		adj.resize(n+1);

		for(int i=0; i<(int)flights.size(); i++) {
			s+=flights[i];
		}
		ft=strspl(s, ' ');
		for(int i=0; i<(int)ft.size(); i++) {
			f.push_back(strspltoi(ft[i], ','));
		}
		for(int i=0; i<(int)f.size(); i++) {
			vector <int> vi;
			vi.push_back(f[i][2]);
			vi.push_back(f[i][3]);
			vi.push_back(f[i][4]);
			adj[f[i][0]][f[i][1]].push_back(vi);
		}

		int hi=time+1, lo=0, mid;
		while(hi-lo>1) {
			mid=(hi+lo)/2;
			dad.assign(n+1, -1);
			val.assign(n+1, unseen);
			visit(1, mid);
			if(val[n]-mid>time) hi=mid;
			else lo=mid;
		}

		res=lo;
		if(lo==0) res=-1;
		return res;
	}
};