結果

問題 No.325 マンハッタン距離2
ユーザー LeonardoneLeonardone
提出日時 2015-12-18 09:49:57
言語 Ruby
(3.2.2)
結果
AC  
実行時間 83 ms / 1,000 ms
コード長 6,094 bytes
コンパイル時間 141 ms
コンパイル使用メモリ 11,492 KB
実行使用メモリ 15,384 KB
最終ジャッジ日時 2023-08-27 01:27:42
合計ジャッジ時間 3,726 ms
ジャッジサーバーID
(参考情報)
judge15 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
15,236 KB
testcase_01 AC 75 ms
15,384 KB
testcase_02 AC 74 ms
15,112 KB
testcase_03 AC 72 ms
15,096 KB
testcase_04 AC 76 ms
15,272 KB
testcase_05 AC 74 ms
15,256 KB
testcase_06 AC 79 ms
15,012 KB
testcase_07 AC 75 ms
15,072 KB
testcase_08 AC 73 ms
15,204 KB
testcase_09 AC 74 ms
15,148 KB
testcase_10 AC 75 ms
15,308 KB
testcase_11 AC 75 ms
15,188 KB
testcase_12 AC 74 ms
15,140 KB
testcase_13 AC 72 ms
15,116 KB
testcase_14 AC 75 ms
15,144 KB
testcase_15 AC 75 ms
15,144 KB
testcase_16 AC 74 ms
15,180 KB
testcase_17 AC 72 ms
15,008 KB
testcase_18 AC 74 ms
15,276 KB
testcase_19 AC 76 ms
15,208 KB
testcase_20 AC 76 ms
15,188 KB
testcase_21 AC 77 ms
15,116 KB
testcase_22 AC 82 ms
15,292 KB
testcase_23 AC 81 ms
15,112 KB
testcase_24 AC 81 ms
15,116 KB
testcase_25 AC 79 ms
15,244 KB
testcase_26 AC 81 ms
15,328 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff #

#! ruby
# yukicoder My Practice
# author: Leonardone @ NEETSDKASU

def gs() gets.chomp end
def gi() gets.to_i end
def gss() gets.chomp.split end
def gis() gss.map(&:to_i) end
def nmapf(n,f) n.times.map{ __send__ f } end
def arr2d(h,w,v=0) h.times.map{[v] * w} end
def ngs(n) nmapf n,:gs end
def ngi(n) nmapf n,:gi end
def ngss(n) nmapf n,:gss end
def ngis(n) nmapf n,:gis end
def for2p(hr,wr,&pr) hr.each{|i|wr.each{|j| yield(i,j)}} end
def nsum(n) n * (n + 1) / 2 end

RANDOM_TEST = 0
TEST_RUN = (RANDOM_TEST == 0) && false


=begin
1) D範囲に完全内包
1.1: 軸に接しない 
3 1 10 9 100

1.2: 軸に接する
3 0 10 8 100

1.3: 軸をまたぐ
3 -1 10 7 100

1.4: 原点を含む
-3 -4 10 8 100

2) D範囲を完全内包
-10 -12 15 14 9

3) 一部だけD範囲と重なる
3.1: 三角範囲Dに入る
3.1.1: 軸に接しない
2 3 12 11 10

3.1.2: 片軸にだけ接する
0 3 12 11 10

3.1.3: 両軸に接する
0 0 12 11 10

3.2: 台形範囲Dに入る
3.2.1: 軸に接しない
4 2 15 6 13

3.2.2: 片軸に接する
4 0 15 6 13

3.2.3: 両軸に接する
0 0 15 6 13

3.3: 五角形範囲Dに入る
3.3.1: 軸に接しない
5 2 16 12 24 

3.3.2: 片軸に接する
5 0 16 12 24 

3.3.3: 両軸に接する
0 0 16 12 24 

4) Dの範囲の完全外側
10 13 19 18 11

[1] テストケース
-3 -12 8 -1 11

[2] テストケース
-13 -8 10 8 12

[3] テストケース
4 7 10 11 11

[4] テストケース
5 3 11 20 30

=end


def bruteforce(x1, y1, x2, y2, d)
    count = 0
    (y1..y2).each do |y|
        (x1..x2).each do |x|
            count += 1 if x.abs + y.abs <= d
        end
    end
    count
end

def make_random_case()
    x1 = rand(-20..20)
    y1 = rand(-20..20)
    x2 = x1 + rand(1..40)
    y2 = y1 + rand(1..40)
    d = rand(0..50)
    [x1, y1, x2, y2, d]
end

def bunkatsu(z1_,z2_)
    z1, z2 = [z1_, z2_].minmax
    zmin, zmax = [z1.abs, z2.abs].minmax
    case
    when zmin == 0
        [[0, 0], [1, zmax]]
    when z2 < 0 || 0 < z1
        [[zmin, zmax]]
    when z1 < 0 && 0 < z2
        [[0, 0], [1, zmin], [1, zmax]]
    else
        sleep 10
        []
    end
end

# 4) Dの範囲の完全外側
def perfectly_outside?((x1, x2), (y1, y2), d)
    d < x1 + y1
end

# Dの範囲に完全内包
def perfectly_inside?((x1, x2), (y1, y2), d)
    x2 + y2 <= d
end
def perfectly_inside_count((x1, x2), (y1, y2), d)
    count = (x2 - x1 + 1) * (y2 - y1 + 1)
    puts "inside [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN
    count
end

# 点
def dot?((x1, x2), (y1, y2), d)
    x1 == x2 && y1 == y2 && x1 == y1
end
def dot_count((x1, x2), (y1, y2), d)
    count = 0 <= d - (x1 + y1) ? 1 : 0
    puts "dot [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN
    count
end       

# 直線
def line?((x1, x2), (y1, y2), d)
    x1 == x2 || y1 == y2
end
def line_count((x1, x2), (y1, y2), d)
    count = 0
    if d < x2 + y2
        count = d - (x1 + y1) + 1
    else
        count = (x2 + y2) - (x1 + y1) + 1
    end
    puts "line [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN
    count
end

# 三角形
def triangle?((x1, x2), (y1, y2), d)
    d <= [x1 + y2, x2 + y1].min
end
def triangle_count((x1, x2), (y1, y2), d)
    count = nsum(d - (x1 + y1) + 1)
    puts "triangle [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN
    count
end


# 台形
def trapezoid?((x1, x2), (y1, y2), d)
    d <= [x1 + y2, x2 + y1].max
end
def trapezoid_count((x1, x2), (y1, y2), d)
    short_end, long_end = [x1 + y2, x2 + y1].minmax
    short_len = short_end - (x1 + y1) + 1
    long_len = [d, long_end].min - (x1 + y1) + 1
    count = (short_len * (long_len - short_len)) + nsum(short_len)
    puts "trapezoid [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN
    puts "end: [%d, %d], len: [%d, %d]" % [short_end, long_end, short_len, long_len] if TEST_RUN
    count
end

# 五角形
def pentagon?((x1, x2), (y1, y2), d)
    [x1 + y2, x2 + y1].max < d
end
def pentagon_count((x1, x2), (y1, y2), d)
    count = (x2 - x1 + 1) * (y2 - y1 + 1) - nsum((x2 + y2) - d)
    puts "pentagon [%d, %d] * [%d, %d], count: %d" % [x1, x2, y1, y2, count] if TEST_RUN
    count
end


def solve(x1, y1, x2, y2, d)
    # 1) D範囲に完全内包
    if [x1.abs, x2.abs].max + [y1.abs, y2.abs].max <= d
        puts "perfectly inside of D range" if TEST_RUN
        count = (x2 - x1).abs.succ * (y2 - y1).abs.succ
        return count
    end
    
    # 2) D範囲を完全内包
    if [x1..x2, y1..y2].all?{|r| r.include?(-d) && r.include?(d)}
        puts "perfectly inside of Square" if TEST_RUN
        count = nsum(d) * 4 + 1
        return count
    end
    
    xs = bunkatsu(x1, x2)
    ys = bunkatsu(y1, y2)
    
    puts "xs = %s" % [xs.to_s] if TEST_RUN
    puts "ys = %s" % [ys.to_s] if TEST_RUN
    
    count = 0
    
    for2p(ys,xs) {|yt,xt|
        args = [xt, yt, d]
        next if perfectly_outside?(*args)
        case
        when perfectly_inside?(*args)
            count += perfectly_inside_count(*args)
        when dot?(*args)
            count += dot_count(*args)
        when line?(*args)
            count += line_count(*args)
        when triangle?(*args)
            count += triangle_count(*args)
        when trapezoid?(*args)
            count += trapezoid_count(*args)
        when pentagon?(*args)
            count += pentagon_count(*args)
        end
    }
    count
end

################################################

if RANDOM_TEST > 0
    puts "starting RANDOM TEST"
    RANDOM_TEST.times do
        testcase = make_random_case
        bf = bruteforce(*testcase)
        count = solve(*testcase)
        next if bf == count
        puts "incorrect"
        puts "testcase: " + testcase.to_s
        puts "bf=%d count=%d" % [bf, count]
        break
    end
    puts "finished RANDOM TEST"
    exit
end

args = gis

puts "X1=%d, Y1=%d, X2=%d, Y2=%d, D=%d" % args if TEST_RUN
bf = bruteforce(*args) if TEST_RUN
puts "bruteforce %d" % [bf] if TEST_RUN

count = solve(*args)
puts count

puts (bf == count ? "" : "in") + "corrct!" if TEST_RUN

0