SRM 555 DIV2 本番

SRM 本番 C++

DIV2とかやだー

Coding

255

Brute Forceするだけ

555

遅い。瞬殺すべき
5^nは埋め込む。状態数そんな多くないしメモ化しないでもsubstrしても十分間に合う

955

うーん…色々考えたけど時間切れ

Challenge

適当に考えたケースとして、Easyでrow,colごとにgreedyとか？とかMediumで先頭に一致したらbreakしたらだめだよね、とか。
でもそんな複雑なミスする人はDIV2にはいなくて、結局Mediumで単純なミスを落としただけ。一人他の人に落とされてた。が、まあそんな落ちる人は居ない回なのかな
システムテスト後に見たら、それ以外に落ちてる人は居なかった。まあ良かったでしょう

結果

status pt
255 Passed 250.88
555 Passed 481.57
Challenge 1/0 +50

Division Place: 7/1016 (DIV2)
Rate: 1195→1357

コメント

Mediumでメモ化しない、というね。たぶん問題ないと思うけど、メモ化ということに全く頭が回らなかった。それはだめだ。
次から、絶対DIV2落ちとかやだなー

コード

255でPassしたコード

#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;

struct XorBoardDivTwo {
	int theMax(vector <string> b) {
		int h = b.size(), w = b[0].size();
		int r = -INF;
		rep(i, h) rep(j, w) {
			vector<vector<int> > t(h);
			rep(y, h) rep(x, w) t[y].pb(b[y][x]=='1');
			rep(k, w) t[i][k] ^= 1;
			rep(k, h) t[k][j] ^= 1;
			int e = 0;
			rep(y, h) rep(x, w) {
				e += t[y][x];
			}
			r = max(r, e);
		}
		return r;
	}
};

555でPassしたコード(テンプレは255のものと同じなので略)

string d[22]={
"1","101","11001","1111101","1001110001","110000110101","11110100001001",
"10011000100101101","1011111010111100001","111011100110101100101",
"100101010000001011111001","10111010010000111011011101",
"1110100011010100101001010001","1001000110000100111001110010101",
"101101011110011000100000111101001","11100011010111111010100100110001101",
"10001110000110111100100110111111000001","1011000110100010101111000010111011000101",
"110111100000101101101011001110100111011001","100010101100011100100011000001001000100111101",
"10101101011110001110101111000101101011000110001","1101100011010111001001101011011100010111011110101"
};
set<string>e;
struct CuttingBitString {
	int rec(string s) {
		if(s.size()==0)return 0;
		int r = INF;
		rer(i, 1, s.size()) {
			if(e.count(s.substr(0,i))) {
				r = min(r, 1 + rec(s.substr(i,s.size()-i)));
			}
		}
		return r;
	}
	int getmin(string S) {
		rep(i,22)e.insert(d[i]);
		int r = rec(S);
		return r == INF ? -1 : r;
	}
};