https://codeforces.com/contest/1561/problem/C
시간 2초, 메모리 512MB

input :

• t (1 ≤ t ≤ 105)
• n (1 ≤ t ≤ 105)
• ki ai,1, ai,2, ..., ai,ki (1 ≤ ki ≤ 105)(1 ≤ ai, j ≤ 105)

output :

• For each test case print a single integer — the smallest possible power the hero must start the level with to be able to enter all the caves in some order and beat all the monsters.
  각 테스트 케이스에서 hero가 모든 동굴을 섬멸할 수 있기 위해 가져야 하는 최소한의 power를 출력하시오..

조건 :

• n개의 동굴이 존재한다.

• 동굴에 입장을 하는 순서는 마음대로 정할 수 있다.

• 동굴에 입장 하면 존재하는 ki의 몬스터와 싸워야 한다.

• hero의 power가 몬스터의 armour보다 커야만 이길 수 있다.

• 몬스터를 쓰러트릴 때 마다 hero의 power는 1씩 상승한다.

---

가장 처음 잘못된 접근으로는 각 동굴에서 가장 강한 몬스터를 쓰러뜨리기 위한 최소의 조건을 맞추면 되지 않을까 였다.

그러나 이런 경우에는 가장 강한 놈을 쓰러뜨리기 위해 용사가 성장을 하는 경우로 따졌다. 즉 인덱스를 따져서 hero가 최소한 몇을 가지고 있으면 몇을 얻은 다음에 무찌를 수 있겠다는 식이었다.

9 9 9 9 9 10의 동굴이 있다고 치면 내가 계산을 한 것은 한 7쯤 맨처음 들고 오면 가장 강한 10은 이기지만 시작할 때부터 문제가 발생한다.

그래서 해야 할 것은 뭐냐?

각 동굴에 입장을 해서 모든 몬스터를 이기려면 레벨 업을 해서 몬스터를 상대할 때 그 몬스터 보다 가진 값이 커야 한다. 솔직히 별 차이 없어 보이는데 생각보다 큰 차이가 있다.

나는 오직 하나의 원소만 따졌지만 모든 원소에 대해 power 상승까지 따져서 계산을 하기 때문에 당연히 이렇게 해야하는 거였다....

x > ai,1 ;
x + 1 > ai,2;
x + 2 > ai,3;
...
x + (ki − 1) > ai,ki.

풀이를 봐도 이렇게 써져 있다.
그렇게 입력을 들어올 때 각 원소에 대해 인덱스 계산을 통해서 해당 지점에서 몇의 power를 가져야 하는지를 계산 했다.

어떤 동굴을 들어갈 지 도 생각해야 한다.

동굴은 가장 좋은 것이 내림차순의 경로만 아니면 된다.
낮은 힘에서 높은 힘으로 가면 더 낮은 힘을 얻을 수 있지만 내림차순의 경우에는 가장 큰 값에서 시작하는 거니까 문제가 생긴다.

동굴을 돌 때 하나의 동굴을 돌면 그 안에 존재하는 몬스터만큼 힘의 증가가 발생한다.
맨 처음에 들고 있어야 하는 값이 이 힘의 증가를 포함한 상황에서 가장 큰 값보다 1 더 커야 조건을 만족시킬 수 있다.

이도 위의 부등식처럼 동일하게 힘의 상승을 누적한 값을 계속 더한 값을 x에 더해 나타낼 수 있다.

import sys

for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    monsters = []

    for _ in range(n):
        temp = list(map(int, sys.stdin.readline().split()))
        need_power, level_up = -float('inf'), temp[0]

        for i in range(1, 1 + level_up):
            need_power = max(need_power, temp[i] - i + 1)

        monsters.append((need_power, level_up))

    monsters.sort()
    level, need_power = 0, -float('inf')
    for i in range(n):
        need_power = max(need_power, monsters[i][0] - level + 1)
        level += monsters[i][1]

    print(need_power)