2009-12-24
来年の為に
| 
今年はSRM皆勤したけどほとんど練習出来なかった。Easyがsubmitできないなんて色々終わってるので過去問で練習したい。
- Practice Roomにある過去問はSRM144から
- 毎日１回分解いてたら１年で終わる量
- やった事のある問題も当然あるけど何度でもやる。というか前より速くなってるべき
というわけでSRM144から。方針はDIV1の
- Easyは必須
- Mediumも解く
- Hardも問題は読む
という感じで始めたい。
過去問マラソン(#1):SRM144
過去問マラソン | | 
得点配分が今と違う感じ
Easy(300): BinaryCode
- 前にやった記憶あり
- こういうのすぐにコーディングすると空中分解するタイプ
- とりあえず解けるんだけどchar[]で解いてるしここはSTL使ってなんとかしたい。で
- を今頃知った。
- 入力長が1,2の場合が例外的なので気をつけて
- pの両側に門番(0)をつけた方が条件分岐なくて良いので楽。最後のpに非0が来たら"NONE"
#define sz(a) int((a).size())
#define pb push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define all(c) (c).begin(),(c).end()
class BinaryCode {
public:
string guess(string m,int p0){
int n=sz(m);
vector<char> q(all(m)), p(n+2);
rep(i,n) q[i]-='0'; p[0]=0, p[1]=p0;//, p[n+1]=0;
FOR(i,1,n+1) p[i+1]=q[i-1]-p[i]-p[i-1];
if (p[n+1]!=0) return "NONE";
FOR(i,1,n) { if(p[i]<0||1<p[i]) return "NONE"; else p[i]+='0'; }
return string(p.begin()+1, p.end()-1);
}
vector <string> decode(string message) {
vs ans;
ans.pb( guess(message,0) );
ans.pb( guess(message,1) );
return ans;
}
};
Medium(550): Lottery
- 前にも見たかも
- 文字列パース。というかsplit
- sortedはDP
- わりとすんなり書けた（と言っても25'16''）
- system test一発OK
typedef long long ll;
typedef vector<string> vs;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e) ((s).find(e)!=(s).end())
typedef pair<int,int> i_i;
// 自作split
vector<string> split(string str, string delim) {
// 略
}
vector<string> split(string str, int delim=' ') {
// 略
}
bool atob(string s){ return s[0]=='T'; }
ll pow(int x,int y){ // x^y
ll ans=1LL; rep(i,y) ans *= (ll)x; return ans;
}
ll fac(int x,int y){ // x!/(x-y)!
ll ans=1LL; rep(i,y) ans *= (ll)(x--); return ans;
}
class Lottery {
map<i_i,ll> m1, m2;
ll sub_sorted_unique(int choices,int blanks){ // 1 2 3 ...
if (blanks==0) return 1;
i_i key=cons(choices,blanks);
if(found(m1,key)) return m1[key];
ll sum=0LL;
rep(i,choices){
sum += sub_sorted_unique(choices-i-1,blanks-1);
}
m1[key]=sum;
return sum;
}
ll sub_sorted(int choices,int blanks){ // 1 1 2 ...
if (blanks==0) return 1;
i_i key=cons(choices,blanks);
if(found(m2,key)) return m2[key];
ll sum=0LL;
rep(i,choices){
sum += sub_sorted(choices-i,blanks-1);
}
m2[key]=sum;
return sum;
}
ll num(string name, int choices, int blanks, bool sorted, bool unique) {
// number of valid lottery tickets for that game...
// choices: 10-100 ... [1..choices]
// blanks: 1-8
ll cnt = 0LL;
if (sorted) {
if (unique) {
// 1 2 3 4 5
cnt = sub_sorted_unique(choices,blanks);
} else {
// 1 1 2 3 3
cnt = sub_sorted(choices,blanks);
}
} else {
if (unique) {
// 3 2 1 5 4
cnt = fac(choices,blanks);
} else {
// 3 3 1 2 1
cnt = pow(choices,blanks); // 1e2 ^ 8 = 1e16
}
}
/*
printf("name:%s choices:%d blanks:%d sorted:%s unique:%s => %lld\n",
name.c_str(), choices, blanks, sorted?"YES":"NO", unique?"YES":"NO",
cnt);
*/
return cnt;
}
public:
vector <string> sortByOdds(vector<string> rules) {
m1.clear(); m2.clear();
vector<pair<ll,string> > res;
tr(rules,st){
vs a1 = split(*st,": ");
string name = a1[0];
vs a2 = split(a1[1],' ');
int choices = atoi(a2[0].c_str()), blanks = atoi(a2[1].c_str());
bool sorted = atob(a2[2]), unique = atob(a2[3]);
res.pb(cons(num(name,choices,blanks,sorted,unique),name));
}
sort(all(res));// reverse(all(res));
vs ans;
tr(res,it) ans.pb(it->second);
return ans;
}
};
Hard(1100): PenLift
- プロッタ懐かしい
- とか言ってる場合じゃなくて
- とりあえずグラフに変換
- 同じ向きの繋がった（or 重なった）線分を検出し、union-findしといて後でまとめる
- 線分を交差点で区切り、nodeとarcを抽出
- union-findして島分割
- n回重ね書きするのでarcの本数を各n倍にする
- それぞれの島が何筆書きになるか、で行ける
- （ここまでで３時間半。sample case#5がちゃんと解けてない！intersection判定にバグあり？）
- 結局４時間半かかって解けた
- system test一発OK
- 以下駄コード
- cons,car,cdr,caar,cadr,cdar,cddrとかまあ気にしないで
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n) for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define found(s,e) ((s).find(e)!=(s).end())
typedef pair<int,int> i_i;
typedef pair<ll,ll> ll_ll;
typedef pair<double,double> d_d;
typedef pair<int,pair<int,int> > i_ii;
#define cons(x,y) make_pair((x),(y))
#define car(x) ((x).first)
#define cdr(x) ((x).second)
#define caar(x) (x).first.first
#define cdar(x) (x).first.second
#define cadr(x) (x).second.first
#define cddr(x) (x).second.second
vector<string> split(string str, int delim=' ')
{
vector<string> result;
const char *s = str.c_str();
if (delim == ' ') {
for (const char *p=s; *p; p++) {
if (*p == delim) s++;
else break;
}
if (!*s) return result;
for (const char *p=s; *p; p++) {
if (*p == delim) {
if (s < p) {
string a(s,p-s);
result.push_back(a);
}
s = p + 1;
}
}
if (*s) result.push_back(s);
} else {
for (const char *p=s; *p; p++) {
if (*p == delim) {
string a(s,p-s);
result.push_back(a);
s = p + 1;
if (*s == '¥0') result.push_back("");
}
}
if (*s) result.push_back(s);
}
return result;
}
vector<int> map_atoi(vector<string> nums)
{
vector<int> vals(nums.size());
for (int i=nums.size()-1; i>=0; i--) vals[i] = atoi(nums[i].c_str());
return vals;
}
typedef pair<int,int> point;
typedef pair<point,point> segment;
vector<segment> segments;
vector<bool> deleted;
vector<int> dirs;
int dir(const segment& s){
point p1 = car(s), p2 = cdr(s);
if (p1==p2) return -1;
if (car(p1)==car(p2)) // x1=x2
return (p2.second > p1.second)?1:3;
else
return (p2.first > p1.first)?0:2;
}
segment rev(const segment& s){
return cons(cdr(s),car(s));
}
segment joint(int i, int j){
segment s1 = segments[i], s2 = segments[j];
int dir = dirs[i]; // assume dirs[i]=dirs[j]
if (dir==0) { // horizontal
int y = cdar(s1);
int x0 = min( caar(s1),caar(s2) ),
x1 = max( cadr(s1),cadr(s2) );
return cons(cons(x0,y),cons(x1,y));
} else {
int x = caar(s1);
int y0 = min( cdar(s1),cdar(s2) ),
y1 = max( cddr(s1),cddr(s2) );
return cons(cons(x,y0),cons(x,y1));
}
}
point cross(int i, int j){
segment s1 = segments[i], s2 = segments[j];
int d1 = dirs[i], d2 = dirs[j];
if (d1==1 && d2==0) return cross(j,i);
int y=cdar(s1);
if (cdar(s2) <= y && y <= cddr(s2)) {
FOR(x,caar(s1),cadr(s1)) {
// x,y
if(x==caar(s2)) return cons(x,y);
}
}
return cons(INT_MAX,INT_MAX);
}
bool oddp(int n){
return (n & 1)? true : false;
}
class UnionFind {
vector<int> data;
public:
UnionFind(int size) : data(size, -1) { }
bool unionSet(int x, int y) {
x = root(x); y = root(y);
if (x != y) {
if (data[y] < data[x]) swap(x, y);
data[x] += data[y]; data[y] = x;
}
return x != y;
}
bool findSet(int x, int y) {
return root(x) == root(y);
}
int root(int x) {
return data[x] < 0 ? x : data[x] = root(data[x]);
}
int size(int x) {
return -data[root(x)];
}
};
class PenLift {
public:
int numTimes(vector<string> segs, int n) {
int N = sz(segs);
segments.resize(N);
deleted.resize(N);
dirs.resize(N);
rep(i,N){ // segment_id
vector<int> t = map_atoi(split(segs[i]));
segment s = cons(cons(t[0],t[1]), cons(t[2],t[3]));
if (dir(s) >= 2) s = rev(s);
segments[i] = s; deleted[i] = false;
dirs[i] = dir(s);
}
// joint
UnionFind uf0(N); set<int> jointed;
FOR(i,0,N-2){
FOR(j,i+1,N-1){
if (dirs[i]==dirs[j]) {
if (dirs[i]==0) { // h
int yi = cdar(segments[i]), yj = cdar(segments[j]);
if (yi != yj) continue;
int x0 = caar(segments[i]), x1 = cadr(segments[i]),
x2 = caar(segments[j]), x3 = cadr(segments[j]);
if (x0>x2) { swap(x0,x2); swap(x1,x3); } // x0 <= x2
if (x2 <= x1) {
uf0.unionSet(i,j);
jointed.insert(i); jointed.insert(j);
}
} else { // v
int xi = caar(segments[i]), xj = caar(segments[j]);
if (xi != xj) continue;
int y0 = cdar(segments[i]), y1 = cddr(segments[i]),
y2 = cdar(segments[j]), y3 = cddr(segments[j]);
if (y0>y2) { swap(y0,y2); swap(y1,y3); } // y0 <= y2
if (y2 <= y1) {
uf0.unionSet(i,j);
jointed.insert(i); jointed.insert(j);
}
}
}
}
}
map<int,set<int> > joint_isle;
tr(jointed,it){
int root = uf0.root(*it);
if (!found(joint_isle,root)) {
set<int> s;
joint_isle[root] = s;
}
//if (*it != root)
joint_isle[root].insert(*it);
}
tr(joint_isle,it) {
int root=it->first;
if (dirs[root] == 0) { // horizontal
int y = cdar(segments[root]);
int xmin = INT_MAX, xmax = INT_MIN;
tr(it->second,jt) {
segment s = segments[*jt];
int x0 = caar(s), x1 = cadr(s);
if (x0 > x1) swap(x0,x1);
xmin = min(xmin,x0);
xmax = max(xmax,x1);
deleted[*jt] = true;
}
segments[root] = cons(cons(xmin,y),cons(xmax,y));
deleted[root] = false;
} else { // vertical
int x = caar(segments[root]);
int ymin = INT_MAX, ymax = INT_MIN;
tr(it->second,jt) {
segment s = segments[*jt];
int y0 = cdar(s), y1 = cddr(s);
if (y0 > y1) swap(y0,y1);
ymin = min(ymin,y0);
ymax = max(ymax,y1);
deleted[*jt] = true;
}
segments[root] = cons(cons(x,ymin),cons(x,ymax));
deleted[root] = false;
}
}
// cross
vector<set<point> > seps(N,set<point>());
FOR(i,0,N-2){
if (deleted[i]) continue;
FOR(j,i+1,N-1){
if (deleted[j]) continue;
if (dirs[i]!=dirs[j]) {
point nx = cross(i,j);
if (car(nx)==INT_MAX) continue;
seps[i].insert(nx);
seps[j].insert(nx);
}
}
}
rep(segment_id,N) {
int sepsz = sz(seps[segment_id]);
if (sepsz > 0) {
deleted[segment_id] = true;
if (dirs[segment_id]==0) { // horizontal
int y = cdar(segments[segment_id]);
set<int> xs;
xs.insert(caar(segments[segment_id]));
xs.insert(cadr(segments[segment_id]));
tr(seps[segment_id],it) xs.insert(it->first);
vector<int> xsv(all(xs));
sort(all(xsv));
rep(k,sz(xsv)-1) {
segment sk = cons(cons(xsv[k],y),cons(xsv[k+1],y));
segments.pb(sk); deleted.pb(false);
}
} else { // vertical
int x = caar(segments[segment_id]);
set<int> ys;
ys.insert(cdar(segments[segment_id]));
ys.insert(cddr(segments[segment_id]));
tr(seps[segment_id],it) ys.insert(it->second);
vector<int> ysv(all(ys));
sort(all(ysv));
rep(k,sz(ysv)-1) {
segment sk = cons(cons(x,ysv[k]),cons(x,ysv[k+1]));
segments.pb(sk); deleted.pb(false);
}
}
}
}
// 両端登録
map<point,set<int> > nodes; // points[point] = { segment_ids }
rep(segment_id,sz(segments)){
if (deleted[segment_id]) continue;
vector<point> n(2);
n[0]=car(segments[segment_id]);
n[1]=cdr(segments[segment_id]);
rep(node_id,2) {
if(found(nodes,n[node_id])) {
nodes[n[node_id]].insert(segment_id);
} else {
set<int> s; s.insert(segment_id);
nodes[n[node_id]] = s;
}
}
}
UnionFind uf(sz(segments));
tr(nodes,nt){
set<int> arcs = nt->second;
vector<int> av(all(arcs)); FOR(i,1,sz(av)-1) uf.unionSet(av[0],av[i]);
}
map<int,int> isles;
rep(i,sz(segments)) {
if (deleted[i]) continue;
int root = uf.root(i);
if (!found(isles,root)) isles[root] = 0;
}
// again
tr(nodes,nt){
point node = nt->first;
set<int> arcs = nt->second;
vector<int> av(all(arcs));
int root = uf.root(av[0]);
if (oddp(sz(arcs)*n)) isles[root]++;
}
tr(isles,it) { it->second /= 2; }
int ans = sz(isles)-1;
tr(isles,it) {
if (it->second == 0) continue;
ans += it->second - 1;
}
return ans;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20091224