SRM DIV2 486 - kyuridenamidaのブログ

人生初の全完…かと思いきや1000点の解法がおかしく死んだ。悔しい。

TxMsg

分かりそうで分からない問題。条件が謎かった。最初間違った解釈してて、途中で気づいて慌てて考え直した。stringstreamを使うと非常に楽。

198.08 Pt.

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
class TxMsg {
public:
	string getMessage(string original) {
		string table = "aiueo";
		stringstream ss(original);
		vector<string> r;
		string token;
		while(ss >> token){
			bool flag = true;
			for(int i=0;i<token.length();i++){
				if(count(table.begin(),table.end(),token[i])==0){
					flag = false;
				}
			}
			if(flag){
				r.push_back(token);
				continue;
			}
			
			while(~token.find_first_of("aiueo")){
				token[token.find_first_of("aiueo")] = ' ';
			}
			stringstream s2(token);
			string want = "";
			string s;
			while( s2 >> s){
				want+=s[0];
			}
			r.push_back(want);
		}
		stringstream ret;
		rep(i,r.size()){
			if(i)ret << " ";
			ret << r[i];
		}
 		return ret.str();
	}

	

};

500

sから辞書順になるように幅優先探索していって最初にtになったものが解。

みんなシステムテスト落ちてた。先輩はtからsに逆算して落ちたと言っていた。

ていうか提出する前に色々自分で穴探してたけど、先に提出して、後でもし気づいたらリサブミットの方が良いのかもしれない・・・。なんかこんな点数なのに部屋で一番Submit早かった。

342.97 Pt.

#include <iostream>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
class NODE{
public:
	ll value;
	string cur;
};

ll calc(ll a,ll b,char c){
	switch(c){
	case '+':return a+b;
	case '-':return a-b;
	case '/':return a/b;
	case '*':return a*b;
	};
	return -1;
}

class OneRegister {
public:
	string getProgram(int s, int t) {
		string ret;
		string table = "*+-/";
		queue<NODE> Q;
		NODE aq;
		aq.value = (ll)s;
		aq.cur = "";
		Q.push(aq);
		map<ll,bool> done;
		
		while(Q.size()){
			NODE q = Q.front();Q.pop();
			//cout << q.value << endl;
			if(q.value == t){	
				return q.cur;
			}
			for(int i=0;i<4;i++){
				char p = table[i];
				NODE next;
				next.value = calc(q.value,q.value,p);
				if(next.value == 0)continue;
				if(next.value > t){
					continue;
				}
				if(done[next.value])continue;
				done[next.value] = true;
				next.cur = q.cur;
				next.cur += p;
				Q.push(next);
			}
				
		}		
 		return ":-(";
	}
};

1000 CrazyLine

隣り合う者同士の身長の差の総和が最大になるような順列を求める。

問題開く→すぐ理解する→テキトウな思いついたグリーディー→なんかおかしい→

悩む→辺のコストの正負を反転させたダイクストラ→SystemTestFaild..

純粋に解法が間違っていたので納得はいったが悔しかった。

0.0 Pt.

#include <cstdio>
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

struct NODE{
	int cost;
	int last;
	int pos;
	bool done[50];
};

bool operator<(const NODE& a,const NODE& b){
	return a.cost < b.cost;
}
class CrazyLine {
public:
	int maxCrazyness(vector <int> he) {
		int n = he.size();
		int ret = 0;
		for(int x=0;x<n;x++){
			priority_queue<NODE> Q;
			NODE t; rep(i,50)t.done[i] = false;
			 t.cost = 0;
			 t.last = he[x];
			 t.pos = x;
			 t.done[x] = true;
			Q.push(t);
			while(Q.size()){
				NODE q = Q.top();Q.pop();
				if( count(q.done,q.done+n,1) == n){
					return q.cost;
				}
				rep(i,n){
					if(q.done[i]){continue;}
					NODE next = q;
					 next.cost = q.cost + abs(q.last-he[i]);
					 next.done[i] = true;
					 next.last = he[i];
					 next.pos = i;
					Q.push(next);
				}
			}
		}
		return -1; // Something is wrong.
	}
};

Challenge Phase

1000点問題を順列で解いてるやつを殺そうとテストケースを作った。(多分みんなやる)

しかし、

「誰もnext_permutation使ってないしグリーディーで解いてる……。くそー……。」とか思ってたらnext_permutationひっそり使ってるやつがいてチャレンジされてたらしく、見落としてしまったことを悔しく感じた。

250は他人のソースホント見る気にならなかったし、500もどうチャレンジしていいのか分からなかった。想像力と読解力の欠如……。

± 0.0Pt.

結果

198.08 + 342.97 + 0.0 + 0.0 = 541.05Pt.

Div2 Place : 17位/1272人

Room Place : 2位/20人

Rate : 1024 → 1177

今回は正直250+チャレンジ回だった気がするなぁ。Rateグンと上がった。初めて2桁台を取ったし、10位台だったけどいつか1桁目指したいです。今回のは1000点通せれば2位だった!次がんばろう。

そういや1200からdiv1か……。