https://yukicoder.me/problems/2699
まず、pekempeyさんの解説にある以下の条件
1
2
3
4
| 0<=a1
0<=b1
a1+...+an==b1+...+bn
ai+bi<=a1+...+an for all i
|
をコードに落とし込むと以下のようになる。なお、a1==x, b1==y==x+sa-sbとする。
1
2
3
4
5
6
7
8
| n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p (0..10**6).count{|x|
x+sa-sb>=0 && x<=sb && (0...n).all?{|i|
a[i]+b[i]<=x+sa
}
}
|
このコードを効率化したいわけだが、今回、範囲が
1
2
3
4
5
6
7
8
| false
...
false
true
...
true
false
...
|
のようであるため、二分探索は使えない。別の方法で効率化を図る。
まず、少し移項すると以下のようになる。
1
2
3
4
5
6
7
8
| n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p (0..10**6).count{|x|
sb-sa<=x && x<=sb && (0...n).all?{|i|
a[i]+b[i]-sa<=x
}
}
|
sb-sa<=x && x<=sbはxの範囲を示すから、これを使う。また、a[i]+b[i]-saは不変量なので、条件を整理する。すると、以下のようになる。
1
2
3
4
5
6
| n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p ([0,sb-sa].max..sb).count{|x|
(0...n).map{|i|a[i]+b[i]-sa}.max<=x
}
|
これもxの範囲となるため、最終的に以下のようになる。
1
2
3
4
| n=gets.not_nil!.to_i-1
a,b=n.times.map{gets.not_nil!.split.map &.to_i}.to_a.transpose
sa,sb=[a,b].map &.sum
p sb-[0,sb-sa,(0...n).map{|i|a[i]+b[i]}.max-sa].max+1
|
ここまで最適化されていれば、Rubyでも十分ACできる。
1
2
3
4
5
| #!/usr/bin/ruby
n=gets.to_i-1
a,b=$<.map{|e|e.split.map &:to_i}.transpose
c,d=[a,b].map &:sum
p d-[0,d-c,*(0...n).map{|i|a[i]+b[i]-c}].max+1
|
重複を減らすと以下のようになる。
1
2
3
4
5
| gets
m=0
a,b=$<.map{|e|e.split.map(&:to_i).tap{|a,b|m=[m,a+b].max}}.transpose
c,d=[a,b].map &:sum
p d-[0,d-c,m-c].max+1
|
そもそも配列を取っておく必要はなかったようだ。
1
2
3
4
| gets
m=c=d=0
$<.map{|e|x,y=e.split.map &:to_i;m=[m,x+y].max;c+=x;d+=y}
p d-[0,d-c,m-c].max+1
|
Crystalも一応書き換えておく。
1
2
3
4
| n=gets.not_nil!.to_i-1
m=c=d=0
n.times{x,y=gets.not_nil!.split.map &.to_i;m=[m,x+y].max;c+=x;d+=y}
p d-[0,d-c,m-c].max+1
|
最終的に関数型っぽいことはしなくても良くなったので、C言語でも書ける。以下のようになる。勿論ifはfmaxで書き換えても良いだろう。
1
2
3
4
5
6
| m,c,d,x,y;
main(){
for(scanf("%d",&x);~scanf("%d%d",&x,&y);c+=x,d+=y)if(m<x+y)m=x+y;
x=0;if(x<d-c)x=d-c;if(x<a-c)x=a-c;
printf("%d\n",d-x+1);
}
|
以上、不変量を見つけてまとめることで計算量が減ってコードも短くなる過程を楽しんでいただけたなら幸いです。