Codeforces Round #224 (Div. 2)
5064 ワード
B:
if(b>=x) b=b-x
if(bb=b-x+w
実はbはずっとxを減らして、0より小さいならば、1回wをプラスします.また、wを加えるたびに必ずb−x+wが0より大きくなる.
では、二分してどのくらい時間tが過ぎたか、不等式b-t*x+k*w>0からkを求める.だからa-k回、つまりc++k回です.
c-t+k<=aと判定します.
code:
C:
n=1,n=2,n>=3の3種類に分けて議論すればよい.
code:
D:
明らかに私たちは最も長いパスを要求して、記憶化して検索すればいいです.
次に、最長パスMaxの場合、答えは少なくとも2*Max-1(前から後へ最長パス)です.2つの最長パスが存在しない限り、ある時点で2つの駒は一緒にぶつからない.駒がぶつかるかどうかを判断するのは簡単です.各格子は一方向に歩くので、終点が同じであれば、必然的に2つの経路が重なる.だから検索するときにゴールを記録すればいいです.
code:
if(b>=x) b=b-x
if(b
実はbはずっとxを減らして、0より小さいならば、1回wをプラスします.また、wを加えるたびに必ずb−x+wが0より大きくなる.
では、二分してどのくらい時間tが過ぎたか、不等式b-t*x+k*w>0からkを求める.だからa-k回、つまりc++k回です.
c-t+k<=aと判定します.
code:
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 2013
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define bit(st,i) ((1ll<<i)&st)
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000003;
const double EPS=1e-7;
ll a,b,w,x,c;
bool check(ll t){
ll dif=max(0ll,t*x-b);
ll d=(dif+w-1)/w;
return c-t+d<=a;
}
int main(){
cin>>a>>b>>w>>x>>c;
ll l=0,r=1ll<<62;
while(l<r){
ll mid=(l+r)>>1;
if(!check(mid)) l=mid+1;
else r=mid;
}
cout<<r<<endl;
return 0;
}
C:
n=1,n=2,n>=3の3種類に分けて議論すればよい.
code:
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 100010
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define bit(st,i) ((1ll<<i)&st)
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000003;
const double EPS=1e-7;
int a[N];
int main(){
int n,d;
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sort(a,a+n);
if(n==1) puts("-1");
else if(n==2){
if(a[0]!=a[1]){
d=a[1]-a[0];
if(d%2==0) puts("3");
else puts("2");
printf("%d",a[0]-d);
if(d%2==0) printf(" %d",a[0]+d/2);
printf(" %d
",a[1]+d);
}else{
puts("1");
printf("%d
",a[0]);
}
}else{
d=a[1]-a[0];
int x;
for(int i=1;i<n;i++) d=min(d,a[i]-a[i-1]);
int cnt=0;
for(int i=1;i<n;i++) if(a[i]-a[i-1]!=d){
if(a[i]-a[i-1]==2*d) cnt++,x=a[i-1]+d;
else{
puts("0");
return 0;
}
}
if(cnt>1){
puts("0");
return 0;
}
if(cnt){
puts("1");
printf("%d
",x);
return 0;
}
if(a[0]-d!=a[n-1]+d){
puts("2");
printf("%d %d
",a[0]-d,a[n-1]+d);
}else{
puts("1");
printf("%d
",a[0]);
}
}
return 0;
}D:
明らかに私たちは最も長いパスを要求して、記憶化して検索すればいいです.
次に、最長パスMaxの場合、答えは少なくとも2*Max-1(前から後へ最長パス)です.2つの最長パスが存在しない限り、ある時点で2つの駒は一緒にぶつからない.駒がぶつかるかどうかを判断するのは簡単です.各格子は一方向に歩くので、終点が同じであれば、必然的に2つの経路が重なる.だから検索するときにゴールを記録すればいいです.
code:
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
#define N 2013
#define ll long long
#define ALL(x) x.begin(),x.end()
#define CLR(x,a) memset(x,a,sizeof(x))
#define bit(st,i) ((1ll<<i)&st)
typedef pair<int,int> PI;
const int INF=0x3fffffff;
const int MOD =1000003;
const double EPS=1e-7;
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
char mp[N][N];
int n,m,dp[N][N],f[N][N];
int sx,sy;
int dir(char c){
switch(c){
case '^':return 0;
case 'v':return 1;
case '<':return 2;
case '>':return 3;
}
}
int dfs(int x,int y){
if(dp[x][y]!=-1) return dp[x][y];
dp[x][y]=1;
f[x][y]=m*x+y;
int d=dir(mp[x][y]);
int xx=dx[d]+x;
int yy=dy[d]+y;
if(mp[xx][yy]!='#'){
if(xx==sx && yy==sy){
puts("-1");
exit(0);
}
if(dp[x][y]<dfs(xx,yy)+1){
dp[x][y]=dp[xx][yy]+1;
f[x][y]=f[xx][yy];
}
}
return dp[x][y];
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",mp[i]);
CLR(dp,-1);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(mp[i][j]!='#' && dp[i][j]==-1){
sx=i,sy=j;
dfs(i,j);
}
int ans=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(mp[i][j]!='#') ans=max(ans,dp[i][j]);
vector<int> d;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(dp[i][j]==ans) d.push_back(f[i][j]);
sort(ALL(d));
d.erase(unique(ALL(d)),d.end());
ans*=2;
if(d.size()==1) ans--;
printf("%d
",ans);
return 0;
}