제출 #519646

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
519646	2022-01-26 22:28:01	Giantpizzahead	Rope (JOI17_rope)	C++17	100 / 100	1286 ms	58344 KiB

rope

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
Solution: The problem statement can be simplified as follows.
Given an array C of N integers, each in the range [1, M]. (Guaranteed at least 1 of each color)
For each c in [1, M], what's the minimum # of elements you must change to create an array that:
- Only has one or two colors, one of which is c
- Can be separated into contiguous ranges of same elements, with the middle ranges having an even size
After fixing 2 colors, how to find minimum cost quickly?
. . 1 . 2 2 . 1 2 . . . 2 1 1 . 2 . . . 1
Fix parity (location of evens)
. . 1 . 2 2 . 1 2 . . . 2 1 1 . 2 . . . 1
   ^   ^   ^   ^   ^   ^   ^   ^   ^   ^
For each pair, optimal cost can be easily determined
No match (. .) = 2
One match (1 ., . 1, 2 ., . 2) = 1
Both match (1 2, 2 1) = 1
Same match (1 1, 2 2) = 0
Might need to add one element matching either of the target colors on the ends (special for loc 0 and N-1)
Don't need to fix two colors to calc above cost (can process each independently), it doesn't affect anything
O(NM^2)
Total cost of a pair = sum of min(cost 1, cost 2) for each element
Each pair can only have up to one color = 0, only up to two colors = 1, everything else will be = 2
Total cost of a pair = 2 * (# of pairs) - Places with improvement
Only 1s will conflict, and only conflict between 2 colors (call these "conflict pairs")
Total cost of a pair =
2 * (# of pairs) - 2 * # with 0 in either color - # with 1 in either color + # where colors conflict
O(N+M^2)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 20 / 20