SRM 563 DIV1 本番 - antaの競技プログラミング練習日記

休日深夜のSRM。寒い

Coding

Easy (300)

適当に辞書順greedyやった。
しかしこの先できるか？の判定ミスってた。
greedyではランダムテストをすることにしているので、Submitしたあとテスト書いたら明らかに「この先できるか？」判定がおかしい。
ラスト10分程度になってからResubmitすることに決めて、書き始めて、なんか適当にやったらランダムテスト通ったのでResubmitした。
90.00ptになってしまった。

Medium (500)

適当に書いた区間DPが通ったのでSubmitした。252.75pt

Challenge

Easy、自分がミスしていたのもあって、みんな落ちそうだなーと思っていた。
そして、適当な人をランダムケースでChallengeしてみたら、成功した。
しかしそのあと、調子に乗って5人に読まずにChallengeしたところ、+100/-125 と、マイナスになってしまった。
やはり、連続の爆撃は、完全に読まずにではなく、「明らかなミスがぱっと見でわかる」状態でないとやるべきでないと思う。
最終的な順位への影響は、+50だったとしても10位あがったくらいだったが、この10位というのは大きいか小さいか？

結果

Easy: +90.00/300
Medium: 252.75/500
Challenge: 2/5 = -25
Division Place: 145/609
Rating: 1442→1540

まあ。
もう少し速く確実に解きたい。

コード

Easy

※不要なルーチンがある

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define mset(m,v) memset(m,v,sizeof(m))

using namespace std;
typedef vector<int> vi;  

int dp[55][55];
struct FoxAndHandle {
	string S, t, a, ss;
	bool rec(int i, int j) {
		if(dp[i][j] != -1) return dp[i][j];
		bool r = false;
		if(i == t.size()) {
			string e;
			string tt = t;
			reu(k, 0, j) {
				bool q = false;
				rep(l, tt.size()) if(tt[l] == S[k]) {
					tt[l] = ' ';
					q = true;
					break;
				}
				if(!q) e += S[k];
			}
			reu(k, j, S.size()) {
				bool q = false;
				rep(l, a.size()) if(a[l] == S[k]) {
					a[l] = ' ';
					q = true;
					break;
				}
				if(!q) e += S[k];
			}
			sort(all(e));
//			cout << e << ", " << ss << endl;
			r = true;
			if(e != ss) r = false;
//			rep(k, a.size()) if(a[k] != ' ') r = false;
		}else if(j == S.size()) ;
		else {
			if(t[i] == S[j]) r |= rec(i+1, j+1);
			r |= rec(i, j+1);
		}
		return dp[i][j] = r;
	}
	string lexSmallestName(string S_) {
		S = S_;
		map<char,int> m; each(i, S) m[*i] ++;
		string s;
		each(i, m) rep(j, i->second/2) s += i->first;
		sort(all(s)); ss = s;
		int n = s.size();
		vi b(n);
		string r = "";
		rep(i, n) {
			rep(j, n) if(!b[j]) {
				t = r; t += s[j];
				a = ""; rep(k, n) if(!b[k] && j != k) a += s[k];
				mset(dp, -1);
				if(rec(0, 0)) {
					r = t;
					b[j] = 1;
					break;
				}
			}
		}
		return r;
	}
};

Medium

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#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 mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f

using namespace std;
typedef vector<int> vi;

int dp1[111][111][55];
int dp2[111][111];
struct SpellCards {
	vi d, e; int n;
	int rec2(int l, int u) {
		if(dp2[l][u] != -1) return dp2[l][u];
		int r = -INF;
		if(l == u) r = 0;
		rer(i, l+1, u) {
			int x = rec(l+1, i, e[l%n]-1);
			if(x != -INF) r = max(r, d[l%n] + x + rec2(i, u));
		}
		return dp2[l][u] = r;
	}
	int rec(int l, int u, int k) {
		if(dp1[l][u][k] != -1) return dp1[l][u][k];
		int r = -INF;
		if(k == 0) r = 0;
		else reu(i, l, u) {
			r = max(r, rec2(l, i) + rec(i+1, u, k-1));
		}
		return dp1[l][u][k] = r;
	}
	int maxDamage(vector <int> level, vector <int> damage) {
		e = level, d = damage; n = e.size();
		int r = 0;
		mset(dp1, -1); mset(dp2, -1);
		reu(l, 0, n) rer(u, l+1, min(l+n, n*2)) r = max(r, rec2(l, u));
		return r;
	}
};