SRM 556 DIV1 本番

本番 SRM C++

DIV1での挑戦となった。部屋はふつう。
Easyはふつう解いてあわよくばMediumも…と思っていた

Coding

250

やるだけ

500

DP？と思った。
適当に考えると、
rec(i, j, b) = i番目のdigitを最終的にj番目とみたときに、bが2ならlowerより大きい最小、1ならlower以上の最小、0ならとにかく最小、という関数が思いついた。
それを書いた。色々と考えたりバグらせたりしてたらかなり遅くなってしまった。
テストして、Submit。この時点では214.44ptだった。
その後Challengeのことを考え、大きいケースないよなーと思っていると、なんと自分のコードがメモ化忘れている！
これはいかんと思ってすぐに直す。結局150.00ptに下がってしまった…

1000

部屋では誰もSubmitしてなかった

Challenge

特に目に見えての嘘解法もないよなーと思いながら、何も準備せず。
結局250・500で数人他の人に落とされて、何もできなかった。

結果

status pt
250 Passed 237.27
500 Passed 150.00
Challenge 0/0 +0

Division Place: 68/652 (DIV1)
Rate: 1357→1525

コメント

黄色！このままレートを上げてRedになりたい…！
Mediumはもう少し早く通したい。
メモ化は絶対に忘れるな。Exampleに大きいケースない時点でTestしろ。
Challengeはまあマイナスよりはよい、が、もっと落とせるようにはなりたい。Challengeも積極的に練習しよう。

コード

250
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

int a[51][1024];
struct XorTravelingSalesman {
	vector<string> d;
	vi c;
	int n;
	int rec(int i, int j) {
//		cout << i << "," << j << endl;
		int &r = a[i][j];
		if(r!=-1)return r;
		r = j;
		rep(k, n) if(d[i][k]=='Y') {
			r = max(r, rec(k, j ^ c[k]));
		}
		return a[i][j] = r;
	}
	int maxProfit(vector <int> cityValues, vector <string> roads) {
		d = roads; c = cityValues; n = c.size();
		mset(a, -1);
		return rec(0, c[0]);
	}
};
500

テンプレ略

struct lstr {
	string s;
	bool inf;
	bool ok;
	lstr(string s,bool t=false):s(s),ok(1),inf(t){}
	lstr(const char*s):s(s),ok(1),inf(0){}
	lstr(bool t):s(""),ok(1),inf(t){}
	lstr():ok(false){}
};
lstr operator+(const char x,const lstr&y){return lstr(x+y.s,y.inf);}
lstr operator+(const lstr&x,const char y){return lstr(x.s+y,x.inf);}
bool operator<(const lstr&x,const lstr&y){
	if(x.inf&&y.inf) return false;
	else if(x.inf) return false;
	else if(y.inf) return true;
	else return x.s < y.s;
}

lstr infs = lstr(true);
lstr dp[55][55][3];
struct LeftRightDigitsGame2 {
	string l; string d; int n;
	//i番目、最終的にj番目とみたときにl以上である必要がある
	//2ならlより真に大きい必要
	//0ならなにもなくていい
	lstr rec(int i, int j, int b) {
		if(dp[i][j][b].ok) return dp[i][j][b];
		if(i == 0) {
			if(b==2) {
				return infs;
			}else return "";
		}
		char c = d[i-1];
		lstr r = infs;
		if(b==0) {
			r = min(r, c+rec(i-1,j,0));
			r = min(r, rec(i-1,j,0)+c);
		}else {
			if(b==0) r = min(r, rec(i, j, 1));
			if(b<=1) r = min(r, rec(i, j, 2));
			if(c > l[j]) {
				r = min(r, c + rec(i-1, j+1, 0));
			}else if(c == l[j]) {
				r = min(r, c + rec(i-1, j+1, b));
			}else {
				
			}
			if(c > l[i+j-1]) {
				r = min(r, rec(i-1, j, 1) + c);
			}else if(c == l[i+j-1]) {
				r = min(r, rec(i-1, j, b) + c);
			}else {
				r = min(r, rec(i-1, j, 2) + c);
			}
		}
		return dp[i][j][b] = r;
	}
	string minNumber(string digits, string l_) {
		l = l_; d = digits; n = d.size();
		lstr r = rec(n, 0, 1);
		rep(i,55)rep(j,55)rep(b,3)dp[i][j][b]=lstr();
		return r.inf ? "" : r.s;
	}
};