GCJ2011 Round2(6/4 23:00~01:30)
Round2に進めただけでも，進歩を感じましたが，欲を出して，Tシャツを狙いに行きました．■A. Airport Walkways
K[m]の道がある．あなたは，普段は速度S[m/s]で歩くが，（トータルで）t[s]だけ速度R[m/s]で走ることが出来る．さらに道のいくつかの部分には，動く歩道が設置されており，その速度があなたの歩くor走る速度に上乗せされる．
最短何秒でK[m]移動することが出来るか．
どこ走るかがポイント．答えは，動く歩道の速度+歩く速度が小さいところをより優先する．
あとは，走った時間が正確にt[s]になるように気をつける．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class A{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int caze;
int TT;
int x, s, r, t, n;
int[] b, e, w;
void run(){
TT=sc.nextInt();
for(caze=1; caze<=TT; caze++){
x=sc.nextInt();
s=sc.nextInt();
r=sc.nextInt();
t=sc.nextInt();
n=sc.nextInt();
b=new int[n];
e=new int[n];
w=new int[n];
for(int i=0; i<n; i++){
b[i]=sc.nextInt();
e[i]=sc.nextInt();
w[i]=sc.nextInt();
}
solve();
}
}
void solve(){
int[] v=new int[x];
fill(v, s);
for(int j=0; j<n; j++){
for(int i=b[j]; i<e[j]; i++){
v[i]+=w[j];
}
}
PriorityQueue<Integer> que=new PriorityQueue<Integer>();
for(int i=0; i<x; i++){
que.offer(v[i]);
}
double d=r-s;
double remain=t;
double ans=0;
for(int i=0; i<x; i++){
int u=que.poll();
if(1.0/(u+d)>remain+EPS){
double p=remain*(u+d);
ans+=remain+(1.0-p)/u;
remain=0;
}else{
remain-=1.0/(u+d);
ans+=1.0/(u+d);
}
}
answer(ans+"");
}
void answer(String s){
println("Case #"+caze+": "+s);
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
public static void main(String[] args){
try{
System.setIn(new FileInputStream(
"D:/contest_workspace/gcj_2011_round2/dat/A-large.in"));
System.setOut(new PrintStream(new FileOutputStream(
"D:/contest_workspace/gcj_2011_round2/dat/A-large.out")));
}catch(Exception e){}
new A().run();
System.out.flush();
System.out.close();
}
}
■B. Spinning Blade
全探索で解ける．愚直に実装すると，(x1, y1)-(x1, y1) からなる長方形の重心を求めるための計算量は， O(n5)となり(8分間では)絶対に間に合わない．
そこで，部分和を使う．
MX1(i, j)=Σ0≦k≦ia(k, j)k
MY1(i, j)=Σ0≦k≦ja(i, k)k
とする．
これで，ある行 or 列に対するある範囲の質量×位置の総和がO(1)で求まるため， 総計算量は、O(n4)になる．しかし，n=500なので，これでも厳しい．
最終的に，
MX2(i, j)=Σ0≦k≦iMX1(i, k)
MY2(i, j)=Σ0≦k≦jMY1(k, j)
とすると，
MX1(i, j) or MY1(i, j)は(1, 1)-(i, j)からなる長方形のxおよびy座標に関する質量×位置の総和になる．(1, 1)-(i, j)の長方形の総質量も同様にして求められるようにすれば，1クエリをO(1)で求めることが出来るため結局，総計算量がO(n3)になり間に合う．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class B{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int caze;
int t;
int m, n, d;
long[][] a;
void run(){
t=sc.nextInt();
for(caze=1; caze<=t; caze++){
n=sc.nextInt();
m=sc.nextInt();
d=sc.nextInt();
a=new long[n][m];
for(int j=0; j<n; j++){
String s=sc.next();
for(int i=0; i<m; i++){
a[j][i]=s.charAt(i)-'0'+d;
}
}
solve();
}
}
long[][] mx1, mx2, my1, my2, m1, m2;
double gx, gy, g;
void solve(){
mx1=new long[n][m];
mx2=new long[n][m];
my1=new long[n][m];
my2=new long[n][m];
m1=new long[n][m];
m2=new long[n][m];
for(int j=0; j<n; j++){
mx1[j][0]=a[j][0]*0;
m1[j][0]=a[j][0];
for(int i=1; i<m; i++){
mx1[j][i]=mx1[j][i-1]+a[j][i]*i;
m1[j][i]=m1[j][i-1]+a[j][i];
}
}
for(int i=0; i<m; i++){
mx2[0][i]=mx1[0][i];
m2[0][i]=m1[0][i];
for(int j=1; j<n; j++){
mx2[j][i]=mx2[j-1][i]+mx1[j][i];
m2[j][i]=m2[j-1][i]+m1[j][i];
}
}
for(int i=0; i<m; i++){
my1[0][i]=a[0][i]*0;
for(int j=1; j<n; j++){
my1[j][i]=my1[j-1][i]+a[j][i]*j;
}
}
for(int j=0; j<n; j++){
my2[j][0]=my1[j][0];
for(int i=1; i<m; i++){
my2[j][i]=my2[j][i-1]+my1[j][i];
}
}
// 1クエリO(1)
int ans=0;
for(int y=0; y<n; y++){
for(int x=0; x<m; x++){
for(int w=3; x+w<=m&&y+w<=n; w++){
calc(x, y, w);
double mx=x+(w-1)/2.;
double my=y+(w-1)/2.;
if(abs(mx-gx)<EPS&&abs(my-gy)<EPS){
ans=max(ans, w);
}
}
}
}
answer(ans>0?(ans+""):"IMPOSSIBLE");
debug(ans);
}
void calc(int x, int y, int w){
gx=mx2[y+w-1][x+w-1];
gy=my2[y+w-1][x+w-1];
g=m2[y+w-1][x+w-1];
if(x>0){
gx-=mx2[y+w-1][x-1];
gy-=my2[y+w-1][x-1];
g-=m2[y+w-1][x-1];
}
if(y>0){
gx-=mx2[y-1][x+w-1];
gy-=my2[y-1][x+w-1];
g-=m2[y-1][x+w-1];
}
if(x>0&&y>0){
gx+=mx2[y-1][x-1];
gy+=my2[y-1][x-1];
g+=m2[y-1][x-1];
}
gx-=a[y][x]*x+a[y][x+w-1]*(x+w-1)+a[y+w-1][x]*x+a[y+w-1][x+w-1]*(x+w-1);
gy-=a[y][x]*y+a[y][x+w-1]*y+a[y+w-1][x]*(y+w-1)+a[y+w-1][x+w-1]*(y+w-1);
g-=a[y][x]+a[y][x+w-1]+a[y+w-1][x]+a[y+w-1][x+w-1];
gx/=g;
gy/=g;
}
void answer(String s){
println("Case #"+caze+": "+s);
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
public static void main(String[] args){
try{
System.setIn(new FileInputStream(
"D:/contest_workspace/gcj_2011_round2/dat/B-large.in"));
System.setOut(new PrintStream(new FileOutputStream(
"D:/contest_workspace/gcj_2011_round2/dat/B-large.out")));
}catch(Exception e){}
new B().run();
System.out.flush();
System.out.close();
}
}
■Result
38pts. 756th
念願のTシャツゲットです．もう少し頑張れば，Round3に進めたかもしれないですが，ここ最近で最高レベルに集中出来たので良かったと思います．
