2010-06-07
GCJ 2010 Round 2 : A. Elegant Diamond
| 
教訓
・問題はよく嫁
・処理しやすい座標系を考える
・斜め移動は（自分の場合）バグりやすいのでご用心
サンプルは通るけどA-smallでIncorrect、なコード
- enhanced diamondの中心になりうるすべての点について、symmetricなdiamondが作れるか調べてるだけ。O(k^4)。
- アイデアはコンテスト中に思いついたままだけど、実装するのに時間かかってるしA-small通らないしAからやってても駄目だったなと…泣
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar) for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c) (c).begin(),(c).end()
#define found(s,e) ((s).find(e)!=(s).end())
#define skiplf() do{char buf[256];cin.getline(buf,256);}while(0)
#define X 52
#define W (X*2+1)
char raw[W][W];
bool centerable[W][W];
int k,l,w;
#define VISUALIZE 1
bool test(int cy,int cx){
rep(i,l){
int dy=i-w, ay=cy*2-dy; /// (ax+dx)/2=cx, ax=2cx-dx
if(ay<-X || X<ay) continue;
rep(j,l){
int dx=j-w, ax=cx*2-dx;
if(ax<-X || X<ax) continue;
if (abs(dx)+abs(dy)>w) continue;
int d=raw[X+dy][X+dx], a=raw[X+ay][X+ax];
if(d<0 || a<0) continue;
if(d!=a) return false;
}
}
return true;
}
int main(){
int T;cin>>T;
rep(t,T){
rep(i,W) rep(j,W) { raw[i][j]=-1; centerable[i][j]=false; }
cin>>k; l=k*2-1; w=k-1;
skiplf();
rep(i,l){
char buf[256]; cin.getline(buf,256);
int dy=i-w;
rep(j,l){
if(!buf[j]) break;
if(buf[j]<'0' || '9'<buf[j]) continue;
int dx=j-w;
raw[X+dy][X+dx] = buf[j]-'0';
}
}
#ifdef VISUALIZE
rep(i,l){
int dy=i-w;
rep(j,l){
int dx=j-w;
int n=raw[X+dy][X+dx];
if(n>=0)
printf(" %d", n);
else
printf(" ");
}
cout<<endl;
}
#endif
// x:[-w,+w], y:[-w,+w]; abs(x)+abs(y)<=w
int minarea = 99999999;
rep(i,l){
int dy=i-w;
rep(j,l){
int dx=j-w;
if (abs(dx)+abs(dy)>w) continue; // |dx|+|dy|<=w
if (centerable[X+dy][X+dx] = test(dy,dx)) {
int abx=abs(dx), aby=abs(dy);
int k_ = k + abx+aby;
minarea=min(minarea,k_*k_);
}
}
}
#ifdef VISUALIZE
rep(i,l){
int dy=i-w;
rep(j,l){
int dx=j-w;
if (abs(dx)+abs(dy)>w) printf(" ");
else printf(" %c", centerable[X+dy][X+dx] ? 'o' : 'x');
}
cout<<endl;
}
#endif
printf("Case #%d: %d\n", 1+t, minarea-k*k);
}
return 0;
}
間違い発見
- あ、これでは（上下左右対称ではなく）点対称か…orz (nodchipさんのエントリを見て気がつきました)
- というわけで上下左右対称に書き直したらsmall/largeともに通った。
- 主な書き換えポイントはtest()、あと探索範囲をダイヤモンド内だけでなくダイヤモンドを含む（45度ずれた）正方形に広げた
bool test(int cy,int cx){ /// ★MODIFIED
rep(i,l){
int dy=i-w, ay=dy, by=cy*2-dy;
rep(j,l){
int dx=j-w, ax=cx*2-dx, bx=dx;
int d=raw[X+dy][X+dx]; if (d<0) continue;
int a=(-w<=ax && ax<=w && -w<=ay && ay<=w)? raw[X+ay][X+ax] : -1;
if (a>=0 && d!=a) return false;
int b=(-w<=bx && bx<=w && -w<=by && by<=w)? raw[X+by][X+bx] : -1;
if (b>=0 && d!=b) return false;
}
}
return true;
}
int main(){
int T;cin>>T;
rep(t,T){
rep(i,W) rep(j,W) { raw[i][j]=-1; centerable[i][j]=false; }
cin>>k; l=k*2-1; w=k-1;
skiplf();
rep(i,l){
char buf[256]; cin.getline(buf,256);
int dy=i-w;
rep(j,l){
if(!buf[j]) break;
if(buf[j]<'0' || '9'<buf[j]) continue;
int dx=j-w;
raw[X+dy][X+dx] = buf[j]-'0';
}
}
#ifdef VISUALIZE
rep(i,l){
int dy=i-w;
rep(j,l){
int dx=j-w;
int n=raw[X+dy][X+dx];
if(n>=0)
printf(" %d", n);
else
printf(" ");
}
cout<<endl;
}
#endif
// x:[-w,+w], y:[-w,+w]; abs(x)+abs(y)<=w
int minarea = 99999999;
rep(i,l){
int dy=i-w;
rep(j,l){
int dx=j-w;
// if (abs(dx)+abs(dy)>w) continue; /// ★REMOVED
if (centerable[X+dy][X+dx] = test(dy,dx)) {
int abx=abs(dx), aby=abs(dy);
int k_ = k + abx+aby;
minarea=min(minarea,k_*k_);
}
}
}
#ifdef VISUALIZE
rep(i,l){
int dy=i-w;
rep(j,l){
int dx=j-w;
printf(" %c", centerable[X+dy][X+dx] ? 'o' : '.'); /// ★CHANGED
}
cout<<endl;
}
#endif
printf("Case #%d: %d\n", 1+t, minarea-k*k);
}
return 0;
}
補足
if (centerable[X+dy][X+dx] = test(dy,dx)) {
とか書いてるけど if ( (c.. = t..) == true ) の意味ですからね。仕事コードではこういう書き方は厳禁ですよ！
GCJ 2010 Round 2 : B. World Cup 2010
| 
後回しにしてたBが簡単すぎて泣きそう
教訓
もちつけ
コンテスト中の思考
- そもそも何で後回しにしたかというと最初に個々のチームについて考えてしまったからで
- それだと上の方で重複しててどうのこうのとか。（もう馬鹿かと。）
- 再帰でなんとかなるよねきっと
- 各チームについて、買わなければならないチケット数 = (P-見逃してもよい回数) だよね。そこまでは簡単
- あるぇーどういう再帰で書いたらいいんだ（焦）
- 後で考えるか…
- その「後」が来なかった件
冷静に解き直したコード
- 落ち着いて書いたら20分かからなかった
- small/largeとも瞬殺＆一発AC
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar) for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c) (c).begin(),(c).end()
#define found(s,e) ((s).find(e)!=(s).end())
int P, es;
vector<int> M;
vector<vector<int> > prices;
vector<vector<int> > minm;
#define NON 1e9+1 // 100000x1000=1e9...
map<int,int> mm;
int sub(int lev,int idx,int seen){
// 0..10<4>, 0..1023<10>, 0..10<4>
int k=(lev<<14)|(idx<<4)|seen;
if(found(mm,k)) return mm[k];
if (seen < minm[lev][idx]) return mm[k]=NON;
if (lev==P) return mm[k]=0;
int skip_this = sub(lev+1,2*idx,seen) + sub(lev+1,2*idx+1,seen);
int watch_this = prices[lev][idx] + sub(lev+1,2*idx,seen+1) + sub(lev+1,2*idx+1,seen+1);
int min_ = min(skip_this, watch_this);
return mm[k]=((min_ >= NON)? NON : min_);
}
int main(){
int T;cin>>T;
rep(t,T){
mm.clear();
cin>>P; es=1<<P;
M.resize(es);
rep(i,es) cin>>M[i];
prices.resize(P); minm.resize(P+1); minm[P].resize(es);
rep(i,es) minm[P][i]=P-M[i];
for(int j=P-1;j>=0;--j){
int es_j=1<<j;
prices[j].resize(es_j); rep(i,es_j) cin>>prices[j][i];
minm[j].resize(es_j); rep(i,es_j) minm[j][i]=max(minm[j+1][i*2]-1,minm[j+1][i*2+1]-1);
}
int ans=sub(0,0,0);
printf("Case #%d: %d\n", 1+t, ans);
}
return 0;
}
GCJ 2010 Round 2 : C. Bacteria
| 
smallは簡単なシミュレーションで解ける。
small版 (AC)
- 気がつくべきこと：上と左の両方に誰かいないと発生しない＝最初にバクテリアがいる座標をすべて含む長方形を考えると、その外へは決して広がって行かない
int main(){
int C;cin>>C;
rep(c,C){
char mp[2][103][103]; memset(mp,0,sizeof(mp));
int R;cin>>R;
int xmin=100,xmax=0,ymin=100,ymax=0;
rep(r,R){
int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
x1++; y1++; x2++; y2++;
xmin=min(xmin,x1); xmax=max(xmax,x1);
ymin=min(ymin,y1); ymax=max(ymax,y1);
xmin=min(xmin,x2); xmax=max(xmax,x2);
ymin=min(ymin,y2); ymax=max(ymax,y2);
for(int x=x1;x<=x2;x++) for(int y=y1;y<=y2;y++) mp[0][x][y]=1;
}
int st=0;
while(1){
int s0 = st%2, s1 = (st+1)%2, cells = 0;
#ifdef VISUALIZE
printf("step %d\n", st+1);
for(int y=ymin;y<=ymax;y++) {
for(int x=xmin;x<=xmax;x++) putchar('0'+mp[s0][x][y]);
putchar('\n');
}
#endif
rep(x,103) rep(y,103) cells += (mp[s1][x][y] = mp[s0][x][y]);
if (cells == 0) break;
for(int x=xmin;x<=xmax;x++) {
for(int y=ymin;y<=ymax;y++) {
if(mp[s0][x][y]){
if(mp[s0][x-1][y]==0 && mp[s0][x][y-1]==0) mp[s1][x][y]=0;
} else {
if(mp[s0][x-1][y]==1 && mp[s0][x][y-1]==1) mp[s1][x][y]=1;
}
}
}
st++;
}
printf("Case #%d: %d\n", 1+c, st);
}
return 0;
}
large対策版（途中）
- 盤面をバクテリア満載長方形のブロックに区切ってlifeゲーム
- smallで試すと #5,#50,#91,#100が通らない。漏れているパターンがありそう
- 1ステップごとに進めてるのでlargeが不安 →（間違ってるけど）現状で2分前後で完了
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar) for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(__typeof__((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
#define mset(arr,val) memset(arr,val,sizeof(arr))
typedef pair<int,int> 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
typedef pair<ii,ii> box;
int main(){
int C;cin>>C;
rep(c,C){
int R;cin>>R;
int xmin=100,xmax=0,ymin=100,ymax=0;
vector<int> x1(R),y1(R),x2(R),y2(R);
set<int> xx,yx;
rep(r,R){
cin>>x1[r]>>y1[r]>>x2[r]>>y2[r];
// 切れ目の座標を集めておく
x2[r]++; y2[r]++;
xx.insert(x1[r]); yx.insert(y1[r]);
xx.insert(x2[r]); yx.insert(y2[r]);
}
// 切れ目を並べ替えて
vector<int> x_(all(xx)); int xn=x_.size()-1;
vector<int> y_(all(yx)); int yn=y_.size()-1;
map<int,int> xm; rep(i,xn+1) xm[x_[i]]=i;
map<int,int> ym; rep(i,yn+1) ym[y_[i]]=i;
vector<int> wx(xn+1,1); rep(i,xn) wx[1+i]=x_[i+1]-x_[i];
vector<int> wy(yn+1,1); rep(i,yn) wy[1+i]=y_[i+1]-y_[i];
vector<vector<ii> > mp(xn+1,vector<ii>(yn+1,ii(0,0)));
vector<vector<int> > full(xn+1,vector<int>(yn+1,1)); rep(x,xn) rep(y,yn) full[1+x][1+y] = wx[1+x]+wy[1+y]-1;
rep(r,R){
for (int x=xm[x1[r]]; x<xm[x2[r]]; ++x)
for (int y=ym[y1[r]]; y<ym[y2[r]]; ++y)
mp[1+x][1+y] = ii(full[1+x][1+y], 0);
}
int st=0;
do {
vector<vector<ii> > mp2=mp;
int cnt=0; rep(x,xn) rep(y,yn) if (mp[1+x][1+y].first + mp[1+x][1+y].second) cnt++;
if (cnt==0) break;
#ifdef VISUALIZE
printf("st=%d¥n", st);
FOR(y,1,yn) {
FOR(x,1,xn)
printf(" %2d", mp[x][y].first);
//printf(" %2d/%2d/%2d", mp[x][y].first, mp[x][y].second, full[x][y]);
cout << endl;
}
#endif
cnt=0;
FOR(x,1,xn) FOR(y,1,yn) {
if (mp[x][y].first > 0 && mp[x][y].second == 0 && mp[x][y].first < full[x][y]) {
mp2[x][y].first++; cnt=max(cnt,1);
}
if (mp[x][y].first > 0) {
// dismiss
if ((mp[x-1][y].first==0 || wx[x-1]<=(-mp[x-1][y].second))
&& (mp[x][y-1].first==0 || wy[y-1]<=(-mp[x][y-1].second))) {
mp2[x][y].second--;
cnt=max(cnt,1);
}
} else {
// gen
if ((mp[x-1][y].first >= wx[x-1] && -mp[x-1][y].second < wx[x-1])
&& (mp[x][y-1].first >= wy[y-1] && -mp[x][y-1].second < wy[y-1])) {
mp2[x][y] = ii(1,0);
cnt=max(cnt,1);
}
}
// regularize
if (mp2[x][y].first + mp2[x][y].second == 0) mp2[x][y] = ii(0,0);
}
st += cnt;
mp=mp2;
} while (1);
printf("Case #%d: %d¥n", 1+c, st);
}
return 0;
}
GCJ 2010 Round 2 : D. Grazing Google Goats
| 
長らくハマってしまい敗退の原因となった問題D。
比較的容易と思って飛びついたD-smallでしたが、結果が合わないのは精度の問題でした。long doubleで解決するような話。
教訓
浮動小数点数の精度とかたまには考えたほうがいいよ。long doubleかわいいよlong double
- 1位のbmerryのコード(AC)をダウンロードしてsmallのデータを食わせてみたら自分のと随分違う値が出てる
- あー。これってもしかしてdoubleの計算誤差かー！！！
- double変数をlong doubleに置き換える。
- sin→sinl,cos→cosl,hypot→hypotlなど
- で、とりあえずsmallはAC
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0,lim=(n);var<lim;var++)
typedef long double ldouble;
typedef pair<ldouble,ldouble> dd;
int N,M;
vector<dd> p,q;
ldouble hypot(dd x1, dd x2){
return hypotl(x1.first-x2.first, x1.second-x2.second);
}
ldouble yogen(ldouble a,ldouble b,ldouble c){
return acosl((a*a+b*b-c*c)/(a*b*2));
}
ldouble ougi(ldouble r,ldouble th=M_PI*2){
return th*r*r/2;
}
ldouble deg(ldouble rad){
return 180.0*rad/M_PI;
}
ldouble area2(int m){
dd qm = q[m];
dd p0=p[0], p1=p[1];
ldouble r0=hypot(p0,qm), r1=hypot(p1,qm), d=hypot(p0,p1);
if(r0<r1) { swap(r0,r1); swap(p0,p1); } // r0 > r1に揃える
ldouble theta=yogen(r0,r1,d);
ldouble th0=yogen(r0,d,r1), th1=yogen(r1,d,r0);
ldouble h=r0*sinl(th0);
if (r0+r1==d) {
return 0; // midpoint
//} else if (th1 <= M_PI/4) {
// return ougi(r0,2*th0) + ougi(r1,2*th1) - d*h;
} else if (r0<r1+d) {
return ougi(r0,2*th0) + ougi(r1,2*th1) - d*h;
} else {
return ougi(r1);
}
return m;
}
int main(){
int T;cin>>T; // S:1-100 L:1-10
rep(t,T){
p.clear(); q.clear();
cin>>N>>M;
rep(n,N){ double x,y; cin>>x>>y; p.pb( dd(x,y) ); } // S:2 L:2-5000
rep(m,M){ double x,y; cin>>x>>y; q.pb( dd(x,y) ); } // S:1-10 L:1-1000
printf("Case #%d:", 1+t);
rep(m,M) printf(" %.9Lf", area2(m));
printf("¥n");
}
return 0;
}
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100607