結果

問題 No.122 傾向と対策：門松列（その３）
ユーザー rpy3cpprpy3cpp
提出日時 2015-09-09 23:50:12
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 1,457 ms / 5,000 ms
コード長 2,203 bytes
コンパイル時間 123 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-07-19 05:08:59
合計ジャッジ時間 4,990 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 230 ms
10,880 KB
testcase_01 AC 136 ms
10,880 KB
testcase_02 AC 1,457 ms
10,880 KB
testcase_03 AC 645 ms
10,752 KB
testcase_04 AC 64 ms
11,008 KB
testcase_05 AC 1,389 ms
11,008 KB
testcase_06 AC 45 ms
10,752 KB
testcase_07 AC 37 ms
11,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def read_data():
    minmaxs = []
    for i in range(7):
        min_i, max_i = map(int, input().split())
        minmaxs.append((min_i, max_i))
    return minmaxs

def solve(minmaxs):
    mod = 10**9 + 7
    minmaxs3 = (minmaxs[1], minmaxs[3], minmaxs[5])
    minmaxs4 = (minmaxs[0], minmaxs[2], minmaxs[4], minmaxs[6])
    count = 0
    for i, minmax in enumerate(minmaxs4):
        minmaxs3b = minmaxs4[:i] + minmaxs4[i + 1:]
        count += count_top_mid_bottom(minmaxs3, minmax, minmaxs3b, mod)
        count += count_top_mid_bottom(minmaxs3b, minmax, minmaxs3, mod)
    return count % mod

def count_top_mid_bottom(minmaxsA, minmax, minmaxsB, mod):
    count = 0
    for mid in range(minmax[0], minmax[1] + 1):
        top = count_top(minmaxsA, mid + 1, mod)
        if top == 0: continue
        bottom = count_bottom(minmaxsB, mid - 1, mod)
        count += top * bottom
    return count % mod

def count_top(minmaxs, lower, mod):
    for min_i, max_i in minmaxs:
        if max_i < lower: return 0
    minmaxs = [(max(lower, min_i), max_i) for min_i, max_i in minmaxs]
    return count_pattern(minmaxs, mod)

def count_bottom(minmaxs, upper, mod):
    for min_i, max_i in minmaxs:
        if min_i > upper: return 0
    minmaxs = [(min_i, min(upper, max_i)) for min_i, max_i in minmaxs]
    return count_pattern(minmaxs, mod)

def count_pattern(minmaxs, mod):
    widths = [max_i - min_i + 1 for min_i, max_i in minmaxs]
    count = widths[0] * widths[1] * widths[2]
    # 0, {1,2}
    lower = max(minmaxs[1][0], minmaxs[2][0])
    upper = min(minmaxs[1][1], minmaxs[2][1])
    if lower <= upper: count -= (upper - lower + 1) * widths[0]
    # 1, {0,2}
    lower = max(minmaxs[0][0], minmaxs[2][0])
    upper = min(minmaxs[0][1], minmaxs[2][1])
    if lower <= upper: count -= (upper - lower + 1) * widths[1]
    # 2, {0,1}
    lower = max(minmaxs[0][0], minmaxs[1][0])
    upper = min(minmaxs[0][1], minmaxs[1][1])
    if lower <= upper: count -= (upper - lower + 1) * widths[2]
    # {0,1,2}
    lower = max(lower, minmaxs[2][0])
    upper = min(upper, minmaxs[2][1])
    if lower <= upper: count += (upper - lower + 1) * 2
    return count % mod

minmaxs = read_data()
print(solve(minmaxs))
0