2009-01-20
SRM360 Div1 Easy: SumOfSelectedCells
これは難しい。むしろ撃墜レースと考えるべき問題。実際Div1でも通過率34%と、500点問題を下回っている。
- DP的に解こうとしている
- 数回のsubmit/systestの末、とりあえず以下のコードまで来た
- まだCase#37がTLE
- 後で上手な人のコードを見るとしよう
class SumOfSelectedCells {
public:
string hypothesis(vector<string> table) {
int h=sz(table);
vector<vector<int> > t(h);
rep(i,h) t[i]=map_atoi(split(table[i]));
int w=sz(t[0]);
if(w>h){
vector<vector<int> > t_(w);
rep(i,w) t_[i].resize(h);
rep(i,w) rep(j,h) t_[i][j]=t[j][i];
t=t_;
swap(w,h);
}
// w<=h
map<int,int> memo;
int mmax=1<<h;
if(w==1){
int z=t[0][0];
for(int i=1;i<h;i++) if(z!=t[i][0]) goto incorrect;
goto correct; //oops
}
if(h==2){
if (t[0][0]+t[1][1] == t[1][0]+t[0][1])
goto correct;
else
goto incorrect;
}
// nC2
rep(x,h) {
rep(i,h) {
if(i==x) continue;
rep(j,h) {
if(j==x||i>=j) continue; //j>i
int s_ij=t[i][0]+t[j][1],
s_ji=t[j][0]+t[i][1];
if(s_ij!=s_ji) goto incorrect;
int m=(1<<i)|(1<<j);
memo[m|(2<<h)]=s_ij;
}
}
}
if(w==2){
if(h>w){
int s=-1;
tr(memo,it){
int s_=it->second;
if(s<0)s=s_;
else if(s!=s_) goto incorrect;
}
}
goto correct;
}
for(int d=3;d<=w;d++){
int b=d+(h-w);
rep(m,mmax){
if(__builtin_popcount(m)!=b) continue;
int s=-1;
rep(i,h){
int x=1<<i;
if((m&x)==0) continue;
int m_=m-x;
if(d==3 && b>3){
for(int m2=3;m2<mmax;m2++){
if(__builtin_popcount(m2)!=2) continue;
if((m_&m2)==m2){ m_=m2; break; }
}
}
int s_=t[i][d-1]+memo[m_|((d-1)<<h)];
if(s<0) s=s_;
else if(s!=s_) goto incorrect;
}
memo[m|(d<<h)]=s;
}
}
correct:
return "CORRECT";
incorrect:
return "INCORRECT";
}
};
SRM361 Div1 Easy: WhiteHats
ごめんなさい２度再挑戦しました
- (白帽子数)≦(人数)
さっと書いて投稿したコードは
{7, 8, 7, 8, 8, 7, 8, 7, 8, 7, 8, 7, 7, 8, 7, 8} => 8
でコケた。
- 白帽子の人自身はその白帽子を勘定に入れられないので、合計で(白帽子数)だけのカウント漏れが発生
- 従って (投票数の合計) = (白帽子数)×(人数)-(白帽子数) = (白帽子数)×(人数 - 1)
- ∴(投票数の合計)/(人数 - 1) = (白帽子数)
再投稿したコードは
{1, 1, 1, 1, 1, 1, 1, 1, 8} => -1
でコケた。うん、それ無理。
- 各人のカウントが (白帽子数) または (白帽子数-1) になっていることを確認。そうでなければ -1 を返す。
#define sz(a) int((a).size())
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
class WhiteHats {
public:
int whiteNumber(vector <int> count) {
int n=sz(count);
int w=0;
tr(count,it){
w+=*it;
}
if(w%(n-1)>0) return -1;
int c=w/(n-1);
if(c>n) return -1;
tr(count,it){
if(*it<c-1 || c<*it) return -1;
}
return c;
}
};
SRM362 Div1 Easy: MaximizeSquares
Failed System Test...
- 使える点の数から、考えられる幅と高さについて全て試す法
- 単純なミス(コメントアウトした箇所)
class MaximizeSquares {
public:
int squareCount(int N) {
if(N<4) return 0;
int wmin=(int)sqrt(N),wmax=N/2;
int cmax=wmax-1;
for(int w=wmin;w<=wmax;w++){
int c=0;
int h0=N/w;
int w0=N-w*h0;
if(w0==1) w0=0;
int h=h0+((w0==0)?0:1);
int rmax=min(w,h);
for(int r=1;r<=rmax;r++){
// if(w>=r && h0>=r) c += (w-r)*(h0-r);
// if(w0>=r && h>=r) c += (w0-r);
if(w-1>=r && h0-1>=r) c += (w-r)*(h0-r);
if(w0-1>=r && h-1>=r) c += (w0-r);
}
cmax = max(cmax,c);
}
return cmax;
}
};
所要時間←→得点の計算
| 
→ Competing in a Rated Algorithm Competition, 12 Determining Score
以下Schemeですが
(define TT 75)
(define (point MP time)
(* MP (+ 0.3 (/ (* 0.7 TT TT) (+ (* 10 time time) (* TT TT))))))
(define (taken-time MP pt)
(* TT (sqrt (/ (- (/ 0.7 (- (/ pt MP) 0.3)) 1) 10))))
(define (minsec min)
(let* ([m (floor->exact min)]
[s (floor->exact (* (- min m) 60))])
(format #t "~d'~d''\n" m s)))
所要時間（分）から得点を得る:
(point 250 3) => 247.24409448818895
得点から所要時間（分）を得る:
(taken-time 250 203.42) => 14.283829997874937 (minsec (taken-time 250 203.42)) => 14'17''
SRM363 Div1 Easy: HandsShaking
ちょっと悩んだ。203.42点(=14'17")
- DP。最初の１人が誰と手をつなぐか。その線の右側と左側の小グループについて考える分割統治。
- 最初の１人は、右側と左側の小グループにそれぞれ偶数人が属するように相手を選んで手をつなぐ。というか、隣りの人から始めて１人おきに回り、反対側の隣りの人で終わる。
typedef long long ll;
#define found(s,e) ((s).find(e)!=(s).end())
class HandsShaking {
map<int,ll> memo;
public:
long long countPerfect(int n) {
if(n==0) return 0LL;
if(n==2) return 1LL;
if(found(memo,n)) return memo[n];
ll sum=0;
for(int i=1;i<n;i+=2){
int a=i-1, b=n-i-1;
if(a==0) sum+=countPerfect(b);
else if(b==0) sum+=countPerfect(a);
else sum+=countPerfect(a)*countPerfect(b);
}
return memo[n]=sum;
}
};
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20090120