スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Huge Easy Contest II (2/2)

2011/04/09 17:00~ 04/10 17:00 (JST)
UVa で開催された Huge Easy Contest II の参加記録

問題が 26 問もあってさすがに多いので、記事を 2 つに分割することにする。
前の記事は結果と感想パート。この記事は問題と解答パート。

Tags : プログラミング UVa 未解決

問題

問題セットの原文はここを参照。
問題数が多いので省略気味に書く。

A. Area
長方形の土地で土地の価値が P を越えないもののうち面積最大のものを求めよ。
そのような土地が複数ある場合は価値が最小のものを選ぶこと。

B. Arithmetic
A + B = C という式が与えられるので、この式が成立するためには何進数で計算すればよいかを答えよ。
答えが複数ある場合は最小のもの。答えがない場合は 0。

C. Battleships
生きている舟の位置と撃墜された船の位置が与えられる。
生きている舟の数を答えよ。
船の形は 1 × ○○ の長方形で、一箇所でも撃墜されていない箇所があれば舟は生きているとする。
2 つの船は隣接したり重なったりしない。

D. Binary Calculator
<digit> ::= 0|1
<number> ::= <digit>|<digit><number>
<unary_operator> ::= not | shr | shl
<binary_operator> ::= xor | and | or
<token> ::= <number> | <unary_operator> <token> | <token> <binary_operator> <token>
<expression> ::= <token> | <token> <expression>

で定義される expression を計算せよ。
単項演算子は二項演算子より早い。二項演算子は左結合。

E. Binomial Theorem
(A+B)^N という式を展開せよ。
A, B は文字列。N は自然数。

F. Brainfuck
Brainfuck のインタプリタを書け。
メモリの数は 100 個とし、99 番と 0 番は環状につながっている。
各メモリは 1 byte まで記憶できる。

G. Checkers
W が 1 つ、B が複数置かれたボードが与えられる。
B は移動しない。
W は 1 回の移動で左前か右前に 1 マス移動できる。ただし、目的のマスに B がいる場合は 2 マス先まで一気に進める。
W が最上段に着くための移動方法は何通りあるか。

H. Coming Home
現時刻とバスが来る時間と各バスに乗ったときの所要時間が与えられるので、一番早く家に着く時間を求めよ。

I. Dice
2 つのさいころが回転で一致するかどうか判定せよ。

J. Divisor Game
N 以下の自然数で、約数の個数が最大であるものを求めよ。

K. DNA
与えられる DNA に k 回の突然変異が起こった結果としてありうる DNA をすべて求めよ。

L. DNA II
与えられる DNA が、同じ長さをもつ DNA の中で、辞書順で何番目かを答えよ。

M. Emigration

N. Equation
x1 + 2 x2 + 4 x3 + 8 x4 + 16 x5 + ... + 2t xt = K where xi ≥ 0
の整数解の個数を mod M で答えよ。
M は 150 以下の素数で素因数分解できる。

O. Extra Spaces
文章から冗長な空白を削除せよ。
空白が 2 文字以上続くとき、2 文字目以降の空白を冗長な空白とする。

P. Galactic Bonding
星の座標が与えられる。
2 つの星は距離が D 以下であるとき同じ星座に属すとする。
星座の数を答えよ。

Q. Hic-Hac-Hoe
無限に広い 2 次元の格子点で K 目並べをする。
与えられる盤面の状態を答えよ。

R. In The Airport
全メニューの平均値に最も近い値段のケーキと飲み物を答えよ。
答えが複数ある場合は値段の小さいほうを答えること。

S. LAMApbo

T. Lucky Numbers
与えられる N に対して、X / √(N-X) が自然数になる X をすべて求めよ。

U. Polygon
棒を K 回カットして K+1 個の部分に分割する。
切る箇所は一様ランダムに選ぶ。
これらの部分を使って多角形が作れる確率を既約分数で答えよ。

V. Round Trip
無向グラフが与えられる。
各辺は高々 1 回だけ通ることができる。
スタート位置から行って戻ってくることができる頂点をすべて求めよ。

W. Sierpinski Carpet
与えられる点が、シェルピンスキーのカーペットの構成段階の何回目の図形で含まれなくなるかを求めよ。
最後まで含まれるときは -1 と答えよ。

X. Switch The Lights
N 個のランプ、M 個のスイッチがあって、スイッチを押すと対応する (複数の) ランプの状態が反転する。
最初、すべてのランプは点灯している。
すべてのランプを消灯するために押すスイッチの最小個数を求めよ。

Y. Tele-loto

Z. Time Deposit
yyyy/mm/dd ~ yyyy/mm/dd の形式で期間が与えられるので、期間中に何日働いたかを求めよ。
平日は働き、土日は働かないとする。
ただし、別途与えられる特別な日についてはその限りではない。

解答

言語は C++。テンプレはここを参照。

A. (時間外)
int p[100][100];
ll dp[100][100];

inline ll rectVal(int u,int l,int b,int r){
ll ans=dp[b][r];
if(u>0) ans-=dp[u-1][r];
if(l>0) ans-=dp[b][l-1];
if(u>0 && l>0) ans+=dp[u-1][l-1];
return ans;
}

int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int m,n,bud; scanf("%d%d%d",&m,&n,&bud);
rep(i,m)rep(j,n) scanf("%d",p[i]+j);

rep(i,m)rep(j,n){
if(i==0 && j==0) dp[i][j]=p[i][j];
else if(i==0) dp[i][j]=dp[i][j-1]+p[i][j];
else if(j==0) dp[i][j]=dp[i-1][j]+p[i][j];
else dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+p[i][j];
}

pair<int,ll> ans(0,0);
rep(r,n)rep(l,r+1){ // fix x-coordinates
for(int u=0,b=0;u<m;u++){
for(b=max(b,u);b<m && rectVal(u,l,b,r)<=bud;b++);
if(u<b){
int bb=b-1;
ans=max(ans,mp((r-l+1)*(bb-u+1),-rectVal(u,l,bb,r)));
}
}
}

printf("Case #%d: %d %lld\n",t,ans.first,-ans.second);
}

return 0;
}

[ 2011/04/13 追記 ]

解いた。
まず、DP で任意の矩形の価値を O(1) で求められるようにしておく。
その後、x 方向は全探索、y 方向は尺取メソッドで探索する。
O(m n2).

なぜか WA になると思ったら、土地を 1 つも選べないときの処理を忘れているだけだった。

B. (時間外)
int maxdgt(int a){
int ans=0;
while(a){ ans=max(ans,a%10); a/=10; }
return ans;
}

int toBaseN(int a,int n){
int ans=0;
for(int d=1;a;a/=10,d*=n) ans+=(a%10)*d;
return ans;
}

bool is1s(int a){ return a==1 || a==11 || a==111 || a==1111 || a==11111; }

int main(){
int T; scanf("%d",&T);
while(T--){
int a,b,c; scanf("%d %*c%d %*c%d",&a,&b,&c);

if(is1s(a) && is1s(b) && is1s(c)){
char s[32]; sprintf(s,"%d%d",a,b);
if(atoi(s)==c){ puts("1"); continue; }
}

int base=2;
base=max(base,maxdgt(a)+1);
base=max(base,maxdgt(b)+1);
base=max(base,maxdgt(c)+1);
for(;base<100;base++){
if(toBaseN(a,base)+toBaseN(b,base)==toBaseN(c,base)) break;
}

if(base<100) printf("%d\n",base); else puts("0");
}

return 0;
}

[ 2011/09/07 追記 ]

1 進数の扱いを間違えていただけみたい。
問題文に明記されていないのが悪いということにしておこう。

C.
int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n; scanf("%d",&n);
char grid[100][101];
rep(i,n) scanf("%s",grid[i]);

int ans=0;
rep(i,n)rep(j,n)if(grid[i][j]!='.'){
bool sunk=true;
queue<pii> qu; qu.push(mp(i,j));
while(!qu.empty()){
pii a=qu.front(); qu.pop();
int y=a.first,x=a.second;
if(grid[y][x]=='x') sunk=false;
grid[y][x]='.';
rep(k,4){
int xx=x+dx[k],yy=y+dy[k];
if(0<=xx && xx<n && 0<=yy && yy<n && grid[yy][xx]!='.'){
qu.push(mp(yy,xx));
}
}
}
if(!sunk) ans++;
}

printf("Case %d: %d\n",t,ans);
}

return 0;
}

舟が隣接しないという条件から、連結成分の数を数えるだけでいい。
ただし、撃墜されている船は数えない。

D. (時間外)
stack<string> tokens;

string trim(const string &s){
int len=s.length();
rep(i,len)if(i==len-1 || s[i]=='1') return s.substr(i);
}

string pad(const string &s,int len2){
int len=s.length();
return string(len2-len,'0')+s;
}

string NOT(string s){
int len=s.length();
rep(i,len) s[i]=(s[i]=='0'?'1':'0');
return trim(s);
}

string SHR(const string &s){
int len=s.length();
if(len==1) return "0";
else return trim(s.substr(0,len-1));
}

string SHL(const string &s){
return trim(s+'0');
}

string XOR(string s,string t){
int len=max(s.length(),t.length());
s=pad(s,len),t=pad(t,len);
rep(i,len) s[i]=(s[i]!=t[i]?'1':'0');
return trim(s);
}

string AND(string s,string t){
int len=max(s.length(),t.length());
s=pad(s,len),t=pad(t,len);
rep(i,len) s[i]=(s[i]=='1'&&t[i]=='1'?'1':'0');
return trim(s);
}

string OR(string s,string t){
int len=max(s.length(),t.length());
s=pad(s,len),t=pad(t,len);
rep(i,len) s[i]=(s[i]=='1'||t[i]=='1'?'1':'0');
return trim(s);
}

string TOKEN2(){
string s=tokens.top(); tokens.pop();
if(s=="not") return NOT(TOKEN2());
if(s=="shr") return SHR(TOKEN2());
if(s=="shl") return SHL(TOKEN2());
return trim(s);
}

string TOKEN1(){
string s=TOKEN2();
while(!tokens.empty()){
string t=tokens.top();
if(t!="xor" && t!="and" && t!="or") break;
tokens.pop();

string u=TOKEN2();
if (t=="xor") s=XOR(s,u);
else if(t=="and") s=AND(s,u);
else s=OR(s,u);
}
return s;
}

string EXPRESSION(){
string s=TOKEN1();
if(!tokens.empty()) s+=" "+EXPRESSION();
return s;
}

string solve(string expr){
stringstream ss(expr);
stack<string> tmp;
while(!ss.eof()){
string s; ss>>s;
tmp.push(s);
}
while(!tmp.empty()){
tokens.push(tmp.top());
tmp.pop();
}

return EXPRESSION();
}

int main(){
int T; cin>>T;
cin.ignore();
for(int t=1;t<=T;t++){
string expr; getline(cin,expr);
cout<<"Case "<<t<<": "<<solve(expr)<<endl;
}
return 0;
}

[ 2011/04/13 追記 ]

解いた。
問題文の BNF のままだと書きにくかったので、
<expression> ::= <token1> | <token1> <expression>
<token1> ::= <token2> (<binary_operator> <token2>)*
<token2> ::= <number> | <unary_operator> <token2>

と変形してからコーディングした。
あとは、いつもの構文解析。

E.
int main(){
const int Nb=50;
ull nCr[Nb+1][Nb+1]={}; rep(n,Nb+1) nCr[n][0]=1;
for(int n=1;n<Nb+1;n++)for(int r=1;r<=n;r++) nCr[n][r]=nCr[n-1][r]+nCr[n-1][r-1];

int T; cin>>T;
for(int t=1;t<=T;t++){
string expr; cin>>expr;
rep(i,expr.length())if(!isalnum(expr[i])) expr[i]=' ';
stringstream ss(expr);
string term1,term2;
int k; ss>>term1>>term2>>k;

cout<<"Case "<<t<<": ";
rep(i,k+1){
int ka=k-i,kb=i;
if(i>0) cout<<"+";
if(nCr[k][ka]>1) cout<<nCr[k][ka]<<"*";
if(ka>0){
cout<<term1;
if(ka>1) cout<<"^"<<ka;
}
if(ka>0 && kb>0) cout<<"*";
if(kb>0){
cout<<term2;
if(kb>1) cout<<"^"<<kb;
}
}
cout<<endl;
}

return 0;
}

二項係数は DP で前計算しておく。

F.
int main(){
int T; scanf("%d ",&T);
for(int t=1;t<=T;t++){
int ptr=0;
unsigned char mem[100]={};
for(char c;c=getchar(),c!='\n'&&c!='\0';){
switch(c){
case '>':
ptr=(ptr+1)%100;
break;
case '<':
ptr=(ptr-1+100)%100;
break;
case '+':
mem[ptr]++;
break;
case '-':
mem[ptr]--;
break;
}
}

printf("Case %d:",t);
rep(i,100) printf(" %02X",mem[i]);
putchar('\n');
}

return 0;
}


G.
const int M=1000007;

int n,memo[100][100];
char grid[100][101];

int dfs(int x,int y){
if(~memo[y][x]) return memo[y][x];

if(y==n-1) return memo[y][x]=1;

int cnt=0;
if(x>0 && grid[y+1][x-1]=='.') cnt+=dfs(x-1,y+1);
if(x<n-1 && grid[y+1][x+1]=='.') cnt+=dfs(x+1,y+1);
if(x>1 && y<n-2 && grid[y+1][x-1]=='B' && grid[y+2][x-2]=='.') cnt+=dfs(x-2,y+2);
if(x<n-2 && y<n-2 && grid[y+1][x+1]=='B' && grid[y+2][x+2]=='.') cnt+=dfs(x+2,y+2);
return memo[y][x]=cnt%M;
}

int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
scanf("%d",&n);
memset(memo,-1,sizeof memo);

int sx,sy;
for(int i=n-1;i>=0;i--){
scanf("%s",grid[i]);
rep(j,n)if(grid[i][j]=='W'){ sx=j,sy=i; break; }
}

printf("Case %d: %d\n",t,dfs(sx,sy));
}

return 0;
}

メモ化再帰

H.
int main(){
int T; scanf("%d",&T);
for(int T1=1;T1<=T;T1++){
int n,h,m; scanf("%d%d:%d",&n,&h,&m);
int t0=60*h+m;
int ans=INF;
rep(i,n){
int q; scanf("%d:%d%d",&h,&m,&q);
int t=60*h+m;
if(t0>t) t+=24*60;
ans=min(ans,t-t0+q);
}
printf("Case %d: %d\n",T1,ans);
}

return 0;
}



I.
void rotx(string &s){
string t=s;
s[0]=t[2];
s[1]=t[4];
s[2]=t[1];
s[4]=t[0];
}

void roty(string &s){
string t=s;
s[0]=t[5];
s[1]=t[3];
s[3]=t[0];
s[5]=t[1];
}

void rotz(string &s){
string t=s;
s[2]=t[5];
s[3]=t[2];
s[4]=t[3];
s[5]=t[4];
}

string toCanonicalForm(string s){
string ans=s;
rep(i,6){
rep(j,4){
ans=min(ans,s);
rotz(s);
}
if(i<4) rotx(s);
if(i==3) roty(s);
if(i==4) roty(s),roty(s);
}
return ans;
}

int main(){
int T; scanf("%d",&T);
while(T--){
char s[7],t[7]; scanf("%s%s",s,t);
puts(toCanonicalForm(s)==toCanonicalForm(t)?"Equal":"Not Equal");
}
return 0;
}

辞書式最小のものを求めて比較した。

J.
int main(){
const int Ne=1100;
static bool er[Ne+1]; er[0]=er[1]=true;
for(int i=2;i*i<=Ne;i++) if(!er[i]) for(int j=i*i;j<=Ne;j+=i) er[j]=true;
vi p; rep(i,Ne+1) if(!er[i]) p.pb(i);

static int num[1000001];
for(int i=1;i<=1000000;i++){
num[i]=1;
int m=i;
rep(j,p.size()){
int pr=p[j];
if(pr>m) break;
if(m%pr==0){
int cnt=1;
do{
m/=pr;
cnt++;
}while(m%pr==0);
num[i]*=cnt;
break;
}
}
num[i]*=num[m];
}

static int dp[1000001]; dp[1]=1;
for(int i=2;i<=1000000;i++) dp[i]=(num[dp[i-1]]<=num[i])?i:dp[i-1];

int T; scanf("%d",&T);
while(T--){
int n; scanf("%d",&n);
printf("%d\n",dp[n]);
}

return 0;
}

最初に約数の個数を全部求めておいて、N 以下で最大のものは DP で求める。
約数の個数は素因数分解すればわかる。
前の値を使って高速化している。

K.
const char base[]="ACGT";

int n,k;
set<string> memo[11];

void dfs(string &DNA,int mut,set<string> &DNAs){
if(memo[mut].count(DNA)>0) return;
memo[mut].insert(DNA);

if(mut==k){ DNAs.insert(DNA); return; }
rep(i,n){
char tmp=DNA[i];
rep(j,4){
DNA[i]=base[j];
dfs(DNA,mut+1,DNAs);
}
DNA[i]=tmp;
}
}

int main(){
int T; scanf("%d",&T);
while(T--){
char DNA[11]; scanf("%d%d%s",&n,&k,DNA);
rep(i,n+1) memo[i].clear();
k=min(n,k);

string DNA2=DNA;
set<string> DNAs;
dfs(DNA2,0,DNAs);

printf("%d\n",DNAs.size());
set<string>::iterator it;
for(it=DNAs.begin();it!=DNAs.end();++it) puts(it->c_str());
}

return 0;
}

DFS で全部生成しながら set につっこむ。
遅かったので適当にメモ化した。

L.
int main(){
int f[128]; f['A']=0,f['C']=1,f['G']=2,f['T']=3;

int T; cin>>T;
for(int t=1;t<=T;t++){
string s; cin>>s;
int len=s.length();
ll ans=0;
rep(i,len) ans=ans*4+f[s[i]];
cout<<"Case "<<t<<": ("<<len<<":"<<ans<<")"<<endl;
}

return 0;
}


M.



N. (時間外)
const int maxK=100000;
const ull maxM=1000000000000000ULL;

map<ull,int> PrimeFactorization(ull a){
map<ull,int> res;
for(ull i=2;i*i<=a;i++)if(a%i==0){
int cnt=0;
do{ a/=i; cnt++; }while(a%i==0);
res[i]=cnt;
}
if(a>1) res[a]=1;
return res;
}

ll xgcd(ll a,ll b,ll &x,ll &y){
if(b==0){ x=1; y=0; return a; }
ll g=xgcd(b,a%b,y,x); y-=a/b*x;
return g;
}

ll modinv(ll a,ull m){
ll x,y;
if(xgcd(a,m,x,y)==1) return (x+m)%m;
return -1;
}

ull ChineseRemainder(vector<ll> a,vector<ull> m){
int n=a.size();
ull m0=1;
rep(i,n) m0*=m[i];
ull ans=0;
rep(i,n) ans=(ans+a[i]*(m0/m[i])*modinv(m0/m[i],m[i]))%m0;
return (ans+m0)%m0;
}

int main(){
const int Ne=150;
static bool er[Ne]; er[0]=er[1]=true;
for(int i=2;i*i<Ne;i++) if(!er[i]) for(int j=i*i;j<Ne;j+=i) er[j]=true;
vi p; rep(i,Ne) if(!er[i]) p.pb(i);

int f[150];
vector<ll> M;
rep(i,p.size()){
f[p[i]]=i;
ll q;
for(q=p[i];q*p[i]<=maxM;q*=p[i]);
M.pb(q);
}

static ll dp[40][maxK+1];
rep(k,p.size()){
dp[k][0]=1;
for(int i=1;i<=maxK;i++){
if(i&1) dp[k][i]=dp[k][i-1];
else{
dp[k][i]=dp[k][i-1]+dp[k][i/2];
if(dp[k][i]>=M[k]) dp[k][i]-=M[k];
}
}
}

int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int K;
ull MOD; scanf("%d%llu",&K,&MOD);

map<ull,int> pf=PrimeFactorization(MOD);
vector<ll> a;
vector<ull> m;
map<ull,int>::iterator it;
for(it=pf.begin();it!=pf.end();++it){
ull q=1;
rep(i,it->second) q*=it->first;
ll res=dp[f[it->first]][K]%q;
a.pb(res);
m.pb(q);
}

printf("Case %d: %llu\n",t,ChineseRemainder(a,m));
}

return 0;
}

[ 2011/04/24 追記 ]

一日格闘してやっと解けた。難しかった。

まず、固定された M に対して、解の個数 a(K, M) を計算する方法を考えた。
これは、xi まで見たときに、和が k 以下なる場合の数を dp[i][k] とする DP でできる。
ただし、DP の更新式をちょっと工夫してループを 1 つ減らさないと間に合わない。

でも実は、そんなことをしなくても OEIS A018819 に答えがあった。上記コードでは、そこに載っていた漸化式を使っている。

固定された M に対して答えを求めることができたが、クエリが 105 個もあるので、1 回ずつ計算しなおしていては間に合わない。
そこで、M は 150 以下の素数で素因数分解できるという仮定を使う。
M = Πi=1→n piqi
と素因数分解したとすると、
a(K, piqi) がすべての i について分かれば、中国人剰余定理から、a(K, M) が一意に定まる。
さらに、a ≧ b のとき、a(K, pia) がわかれば a(K, pib) もわかる。
なので、150 以下の素数 pi と十分大きい qi についてのみ、a(K, piqi) を計算しておけばいい。

O.
int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
printf("Case %d:\n",t);
int n; scanf("%d",&n);
getchar();
rep(i,n){
char s[510]; fgets(s,510,stdin);
for(int j=0;s[j];j++){
if(j>0 && s[j-1]==' ' && s[j]==' ');
else putchar(s[j]);
}
}
if(t<T) putchar('\n');
}
return 0;
}


P.
template<class T>
struct AdjMatrix:public vector< vector<T> >{
AdjMatrix(){}
AdjMatrix(int n,const vector<T> &v=vector<T>()):vector< vector<T> >(n,v){}
template<class U> AdjMatrix(U b,U e):vector< vector<T> >(b,e){}
};

vvi toConnectedComponents(const AdjMatrix<bool> &adj){
int n=adj.size();
vvi res;
vb visited(n);
rep(i,n)if(!visited[i]){
vi comp;
queue<int> qu; qu.push(i); visited[i]=true;
while(!qu.empty()){
int u=qu.front(); qu.pop();
comp.pb(u);
rep(v,n)if(adj[u][v] && !visited[v]){ qu.push(v); visited[v]=true; }
}
res.pb(comp);
}
return res;
}

int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n;
double d; scanf("%d%lf",&n,&d);
double x[1000],y[1000];
rep(i,n) scanf("%lf%lf",x+i,y+i);

AdjMatrix<bool> adj(n,vb(n));
rep(u,n)rep(v,n){
if((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v])<d*d+EPS){
adj[u][v]=true;
}
}

printf("Case %d: %d\n",t,toConnectedComponents(adj).size());
}

return 0;
}

無向グラフの連結成分の個数

Q. (時間外)
int solve(set< pair<ll,ll> > &stone,int k){
int cnt=0;
set< pair<ll,ll> >::iterator it;
for(it=stone.begin();it!=stone.end();++it){
ll x=it->first,y=it->second;
if(stone.count(mp(x-1,y))==0){ // horizontal
bool ok=true;
for(ll xx=x+1;xx<x+k;xx++)if(stone.count(mp(xx,y))==0){ ok=false; break; }
if(ok) cnt++;
}
if(stone.count(mp(x,y-1))==0){ // vertical
bool ok=true;
for(ll yy=y+1;yy<y+k;yy++)if(stone.count(mp(x,yy))==0){ ok=false; break; }
if(ok) cnt++;
}
if(stone.count(mp(x-1,y-1))==0){ // diagonal
bool ok=true;
for(ll xx=x+1,yy=y+1;xx<x+k;xx++,yy++)if(stone.count(mp(xx,yy))==0){ ok=false; break; }
if(ok) cnt++;
}
if(stone.count(mp(x-1,y+1))==0){ // diagonal
bool ok=true;
for(ll xx=x+1,yy=y-1;xx<x+k;xx++,yy--)if(stone.count(mp(xx,yy))==0){ ok=false; break; }
if(ok) cnt++;
}
}

return cnt;
}

int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n,k; scanf("%d%d",&n,&k);
set< pair<ll,ll> > stone[2];
rep(i,n){
int ii=i%2,x,y; scanf("%d%d",&x,&y);
stone[ii].insert(mp(x,y));
}

int win[]={solve(stone[0],k),solve(stone[1],k)};
if (win[0]>=1 && win[1]==0) printf("Case %d: crosses\n",t);
else if(win[0]==0 && win[1]>=1) printf("Case %d: noughts\n",t);
else if(win[0]==0 && win[1]==0) printf("Case %d: none\n",t);
else printf("Case %d: error\n",t);
}

return 0;
}

[ 2011/04/13 追記 ]

解いた。
座標値が大きくてメモリが確保できないので set を使った。
基本的にはやるだけ問題だけど、重複カウントしてしまってちょっとはまった。

R.
#define Abs(a)  ((a)<0?-(a):(a))

int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n,ncake,ntee; scanf("%d%d%d",&n,&ncake,&ntee);
ll price[1000],sum=0;
rep(i,n) scanf("%lld",price+i),sum+=price[i];

ll cake=price[0],tee=price[ncake];
rep(i,ncake){
if( Abs(n*price[i]-sum)< Abs(n*cake-sum)
|| (Abs(n*price[i]-sum)==Abs(n*cake-sum) && price[i]<cake) ){
cake=price[i];
}
}
for(int i=ncake;i<ncake+ntee;i++){
if( Abs(n*price[i]-sum)< Abs(n*tee-sum)
|| (Abs(n*price[i]-sum)==Abs(n*tee-sum) && price[i]<tee) ){
tee=price[i];
}
}
printf("Case #%d: %lld %lld\n",t,cake,tee);
}

return 0;
}


S.



T.
int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n; scanf("%d",&n);
vi a;
for(int i=1;(ll)i*i<n;i++){
int x=n-i*i;
if(x%i==0) a.pb(x);
}
reverse(a.begin(),a.end());

printf("Case %d:",t);
rep(i,a.size()) printf(" %d",a[i]);
putchar('\n');
}

return 0;
}

ルートの中が平方数になる X だけ調べた。

U. (時間外)
ull gcd(ull a,ull b){ return b?gcd(b,a%b):a; }

int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int k; scanf("%*d%d",&k);
ull deno=1ULL<<k,nume=(1ULL<<k)-k-1,g=gcd(deno,nume);
printf("Case #%d: %llu/%llu\n",t,nume/g,deno/g);
}

return 0;
}

[ 2011/04/13 追記 ]

解いた。
数式の上でやる方法が分からなかったので、小さいケースを Monte-Carlo 法でシミュレーションした。
1/4, 1/2, 11/16, 13/16, ...
という有理数列が得られたので、分母は 2 のべき乗だろうと推測できた。
これを適当に何倍かすると
1/4, 4/8, 11/16, 26/32, ...
となる。分子は階差数列っぽかったので、それで試しに送ってみると通った。

V. (時間外)
template<class T>
struct AdjMatrix:public vector< vector<T> >{
AdjMatrix(){}
AdjMatrix(int n,const vector<T> &v=vector<T>()):vector< vector<T> >(n,v){}
};

template<class T>
T augment(const AdjMatrix<T> &capa,int src,int snk,AdjMatrix<T> &flow){
int n=capa.size();
vector<int> parent(n,-1); parent[src]=-2;

T water=0;
queue< pair<T,int> > qu; qu.push(make_pair(INF,src));
while(!qu.empty()){
pair<T,int> a=qu.front(); qu.pop();
int u=a.second;
T w=a.first;
if(u==snk){ water=w; break; }
rep(v,n) if(parent[v]==-1 && capa[u][v]-flow[u][v]>0) {
qu.push(make_pair(min(w,capa[u][v]-flow[u][v]),v));
parent[v]=u;
}
}

if(water==0) return 0;

for(int v=snk,u=parent[snk];v!=src;v=u,u=parent[u]){
flow[u][v]+=water;
flow[v][u]-=water;
}

return water;
}

template<class T>
T FordFulkerson(const AdjMatrix<T> &capa,int src,int snk){
int n=capa.size();
AdjMatrix<T> flow(n,vector<T>(n));

T ans=0;
while(1){
T water=augment(capa,src,snk,flow);
if(water==0) break;
ans+=water;
}
return ans;
}

int main(){
int T0; scanf("%d",&T0);
rep(T,T0){
int n,m,c; scanf("%d%d%d",&n,&m,&c); c--;
AdjMatrix<int> adj(n,vector<int>(n));
rep(i,m){
int u,v; scanf("%d%d",&u,&v); u--; v--;
adj[u][v]++;
adj[v][u]++;
}

bool none=true;
printf("Case %d:",T+1);
rep(u,n) if(u!=c && FordFulkerson(adj,c,u)>=2) {
printf(" %d",u+1);
none=false;
}
printf("%s\n",none?" none":"");
}

return 0;
}

[ 2011/09/07 追記 ]

コンテスト当時は解けなかったのに、今考えると普通に解けた。うれしい。

スタート位置と各頂点の間に 2 単位以上のフローが流れればいい。
フローアルゴリズムは隣接行列表現の Ford-Fulkerson。遅い。

別解として、Spaghetti Source にある 「二重辺連結成分分解」 をすれば、スタート位置が含まれる成分が答えになる。 (やってない)

W.
int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
double xx,yy; scanf("%lf%lf",&xx,&yy);
int x=(int)(1000000*xx),y=(int)(1000000*yy);
if(x==1000000 || y==1000000){
printf("Case %d: -1\n",t);
continue;
}

int ans=-1;
rep(k,1000000){
x*=3,y*=3;
int xdgt=x/1000000,ydgt=y/1000000;
if(xdgt==1 && ydgt==1){ ans=k; break; }
x-=xdgt*1000000,y-=ydgt*1000000;
}
printf("Case %d: %d\n",t,ans);
}

return 0;
}

「三進数で書いたときに x, y ともに小数以下 i 桁目が 1 ⇔ 点 (x,y) は i 回目に集合から外れる」

三進小数は適当なところで循環するだろうから、ある程度先まで見れば十分。
小数以下 1000000 桁まで調べたら通った。

X.
int main(){
int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n,m; scanf("%d%d",&n,&m);
int sw[100]={};
rep(i,m)rep(j,n){
int tmp; scanf("%d",&tmp);
if(tmp==1) sw[i]|=1<<j;
}

static int dp[101][1<<15];
rep(i,m+1)rep(S,1<<n) dp[i][S]=INF;
dp[0][(1<<n)-1]=0;
rep(i,m)rep(S,1<<n){
dp[i+1][S^sw[i]]=min(dp[i][S^sw[i]],dp[i][S]+1);
}

printf("Case %d: ",t);
if(dp[m][0]<INF) printf("%d\n",dp[m][0]);
else puts("IMPOSSIBLE");
}

return 0;
}

DP.
何番目のスイッチまで見たかと今のランプの点灯パターンを状態にする。
O(m 2n).

Y.



Z. (時間外)
/* Zeller's congruence */
bool isHoliday(int y,int m,int q){
if(m<=2) m+=12,y--;
int K=y%100,J=y/100;
int res=(q+(m+1)*26/10+K+K/4+J/4-2*J)%7;
return (res+7)%7<=1;
}

int main(){
const int day[]={-1,31,28,31,30,31,30,31,31,30,31,30,31};

int T; scanf("%d",&T);
for(int t=1;t<=T;t++){
int n; scanf("%d",&n);
int sp[51][13][32]={};
rep(i,n){
int y,m,d;
char work; scanf("%d-%d-%d %c",&y,&m,&d,&work);
if(work=='W') sp[y-1975][m][d]=1;
else sp[y-1975][m][d]=2;
}

int cnt=0;
int y0,m0,d0,y1,m1,d1; scanf("%d-%d-%d%d-%d-%d",&y0,&m0,&d0,&y1,&m1,&d1);
for(int y=y0;y<=y1;y++){
for(int m=(y==y0?m0:1);m<=(y==y1?m1:12);m++){
int end=day[m]+(y%4==0&&m==2);
for(int d=(y==y0&&m==m0?d0:1);d<=(y==y1&&m==m1?d1:end);d++){
if( sp[y-1975][m][d]==1
|| (sp[y-1975][m][d]==0 && !isHoliday(y,m,d)) ){
cnt++;
}
}
}
}

printf("Case %d: %d\n",t,cnt);
}

return 0;
}

[ 2011/04/12 追記 ]

解いた。
全ての日付をイテレートしても間に合う。
曜日の計算は Zeller の公式を使った。



解けなかった問題も逐次解いていく予定。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。