Answer Part 1 Part 2 Part 3
Solution
YDSP 2024 J
tder
2024 9 18
tder
Solution 1 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
4 Part 3
tder
Solution 2 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
4 Part 3
tder
Solution 3 / 39
Answer Part 1 Part 2 Part 3
Part 1
• ACACB DADCD DCBAC
tder
Solution 4 / 39
Answer Part 1 Part 2 Part 3
Part 2
• BAABCB BAABAD ABBDCD
tder
Solution 5 / 39
Answer Part 1 Part 2 Part 3
Part 3
• BDAAD ADCDB
tder
Solution 6 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
4 Part 3
tder
Solution 7 / 39
Answer Part 1 Part 2 Part 3
1st ∼ 3rd
• 1 .
• 2024 = 23 × 11 × 23.
• 1 .
• 1 B = 8 bit 1 KB = 1024 B 1 MB = 1024 KB. A
2024 B ≈ 1.98 KB B 41 MB = 41984 KB C
0.04 MB = 40.96 KB D 114514 b ≈ 13.98 KB. B
.
• 1 2 ∧ .
• (72)8 = (0111010)2 (110)10 = (1101110)2 .
(1010100)2 = (84)10 .
tder
Solution 8 / 39
Answer Part 1 Part 2 Part 3
4th ∼ 6th
• 3 3 .
• . 1104
1 ∼ 920 . 920 + 1 = 921
1104 .
• 2 .
• 4 × 4 = 16 .
DP
CSP-J
3 . 16 − 3 = 13 .
• 1 .
• (4 − (3 − 4)) + ((6 ÷ 2) × 1) = 8.
tder
Solution 9 / 39
Answer Part 1 Part 2 Part 3
7th ∼ 8th
• 4 4 vector .
• end() 6
3 3 30.
• 1 2 string .
• string 0
s[l − 1 ... r − 1]. i
l −1 i − (l − 1)
r −1 i − (l − 1)
(r − 1) − (i − (l − 1)) = l + r − i − 2 .
tder
Solution 10 / 39
Answer Part 1 Part 2 Part 3
9th
• 4 .
• 2i + 2i+1 < 2i+2
. e
26 − 5 + 1 = 22.
tder
Solution 11 / 39
Answer Part 1 Part 2 Part 3
10th
• 3 sort 4 queue
list .
• A list
. B STL
queue front() top() stack
. C reserve()
reverse() . D .
tder
Solution 12 / 39
Answer Part 1 Part 2 Part 3
11th ∼ 12th
• 4 .
• A∼J 3169208574
9123058746.
• 4 .
• . 7! = 5040
. 3
4 3! × 4! = 144 .
5040 − 144 = 4896 .
tder
Solution 13 / 39
Answer Part 1 Part 2 Part 3
13th ∼ 14th
• 3 .
• Alice
Alice
. 3 .
• 1 .
•
.
0 1 0
0 0 0
2 0 0
tder
Solution 14 / 39
Answer Part 1 Part 2 Part 3
15th
• 3 .
• 1 20 20 20×20
2 = 200
200 0.
20 19
. 3 10
2 × 200 − 90 = 310. 90
220 . 10
10×9
2 = 45 220 . 2
.
tder
Solution 15 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
16th
17th
18th
4 Part 3
tder
Solution 16 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
16th
17th
18th
4 Part 3
tder
Solution 17 / 39
Answer Part 1 Part 2 Part 3
16th
• 1 char 2 string .
• P1079 Vigenère .
tder
Solution 18 / 39
Answer Part 1 Part 2 Part 3
16th (1st ∼ 2nd)
• 2 ASCII .
• ASCII a ASCII 97
z ASCII 122 Z ASCII 90.
(90 − 97) + (122 − 97) = 17 > 0 Z\nz
.
• 2 ASCII .
• ASCII key
ASCII a ASCII
.
tder
Solution 19 / 39
Answer Part 1 Part 2 Part 3
16th (3rd ∼ 4th)
• 2 ASCII .
• 18 code
a z ASCII 97 122.
encode() s code
.
• 1 .
• s[i] key[i]
. 0 ≤ i < |s| . i ≥ |key |
. |s| ≤ |key |
.
tder
Solution 20 / 39
Answer Part 1 Part 2 Part 3
16th (5th ∼ 6th)
• 1 .
• . 26 z 1
a.
• 1 .
• si (keyi − a)
si (keyi − a) .
tder
Solution 21 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
16th
17th
18th
4 Part 3
tder
Solution 22 / 39
Answer Part 1 Part 2 Part 3
17th
• 1 3 4
.
•
n .
tder
Solution 23 / 39
Answer Part 1 Part 2 Part 3
17th (1st ∼ 3rd)
• 1 .
• mod ∤ n n
–1.
• 3 .
• .
• 4 .
• 38 i primej
prime i
primej .
O(n log n).
tder
Solution 24 / 39
Answer Part 1 Part 2 Part 3
17th (4th ∼ 6th)
• 1 .
• . 27 × 14 ≡ 378 ≡ 1 (mod 29).
• 3 .
• .
• 1 .
• . gcd(78, 52) = 26.
tder
Solution 25 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
16th
17th
18th
4 Part 3
tder
Solution 26 / 39
Answer Part 1 Part 2 Part 3
18th
• 1 1 3
.
•
. f1 = 1 f3 = 1
f2 = 1 .
tder
Solution 27 / 39
Answer Part 1 Part 2 Part 3
18th (1st ∼ 3rd)
• 2 .
• 13 i 1 l =0 16 1.
• 1 .
• . 707713249/349650
.
• 1 .
• 39 num = l = {1, 0, 0} f1 = 1
f2 = f3 = 0. 40 42 a =1×1+0=1
b=0 gcd(a, b) = 1 1/1.
.
tder
Solution 28 / 39
Answer Part 1 Part 2 Part 3
18th (4th ∼ 6th)
• 1 .
• f1 = f2 = f3 = 0 a b 0
gcd(a, b) = 0 53 a / gcd(a, b)
0 .
• 1 .
• f1 = f2 = 0 f3 = 1 47 50 .
• 1 .
• .
tder
Solution 29 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
4 Part 3
19th
20th
tder
Solution 30 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
4 Part 3
19th
20th
tder
Solution 31 / 39
Answer Part 1 Part 2 Part 3
19th
• 4 4 5
.
• O(V · n).
tder
Solution 32 / 39
Answer Part 1 Part 2 Part 3
19th (1st ∼ 3rd)
• 4 .
• f (x ) f (i + ⌊ ji ⌋) ← f (i) + 1.
• 0 .
• . f (x )
∑
k≥ f (bi ) ai bi ci
.
• 0 .
• .
tder
Solution 33 / 39
Answer Part 1 Part 2 Part 3
19th (4th ∼ 5th)
• 5 .
• . 01 . n
f (bi ) ci .
. g(j) ← g(j − wi ) + vi .
• 5 .
• .
tder
Solution 34 / 39
Answer Part 1 Part 2 Part 3
1 Answer
2 Part 1
3 Part 2
4 Part 3
19th
20th
tder
Solution 35 / 39
Answer Part 1 Part 2 Part 3
20th
• 4 5 .
• DFS .
tder
Solution 36 / 39
Answer Part 1 Part 2 Part 3
20th (1st ∼ 3rd)
• 5 .
• .
• 5 .
• u→v w max
DFS v. DFS
v ⇝t u→v ⇝t .
• 5 .
• u⇝t .
check .
.
tder
Solution 37 / 39
Answer Part 1 Part 2 Part 3
20th (4th ∼ 5th)
• 4 .
• 106 .
• 4 .
• mid ← mid + 1. B
a × 2k
.
tder
Solution 38 / 39
Answer Part 1 Part 2 Part 3
Thank you!
tder
Solution 39 / 39
