Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit6c86c47

Browse files
authored
Added tasks 3627-3630
1 parentd2a5001 commit6c86c47

File tree

12 files changed

+517
-0
lines changed

12 files changed

+517
-0
lines changed
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
packageg3601_3700.s3627_maximum_median_sum_of_subsequences_of_size_3;
2+
3+
// #Medium #Weekly_Contest_460 #2025_07_27_Time_22_ms_(100.00%)_Space_129.50_MB_(86.95%)
4+
5+
importjava.util.Arrays;
6+
7+
publicclassSolution {
8+
publiclongmaximumMedianSum(int[]nums) {
9+
intn =nums.length;
10+
Arrays.sort(nums);
11+
intm =n /3;
12+
longsum =0;
13+
for (inti =n -2;i >=n -2 *m;i =i -2) {
14+
sum =sum +nums[i];
15+
}
16+
returnsum;
17+
}
18+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
3627\. Maximum Median Sum of Subsequences of Size 3
2+
3+
Medium
4+
5+
You are given an integer array`nums` with a length divisible by 3.
6+
7+
You want to make the array empty in steps. In each step, you can select any three elements from the array, compute their**median**, and remove the selected elements from the array.
8+
9+
The**median** of an odd-length sequence is defined as the middle element of the sequence when it is sorted in non-decreasing order.
10+
11+
Return the**maximum** possible sum of the medians computed from the selected elements.
12+
13+
**Example 1:**
14+
15+
**Input:** nums =[2,1,3,2,1,3]
16+
17+
**Output:** 5
18+
19+
**Explanation:**
20+
21+
* In the first step, select elements at indices 2, 4, and 5, which have a median 3. After removing these elements,`nums` becomes`[2, 1, 2]`.
22+
* In the second step, select elements at indices 0, 1, and 2, which have a median 2. After removing these elements,`nums` becomes empty.
23+
24+
Hence, the sum of the medians is`3 + 2 = 5`.
25+
26+
**Example 2:**
27+
28+
**Input:** nums =[1,1,10,10,10,10]
29+
30+
**Output:** 20
31+
32+
**Explanation:**
33+
34+
* In the first step, select elements at indices 0, 2, and 3, which have a median 10. After removing these elements,`nums` becomes`[1, 10, 10]`.
35+
* In the second step, select elements at indices 0, 1, and 2, which have a median 10. After removing these elements,`nums` becomes empty.
36+
37+
Hence, the sum of the medians is`10 + 10 = 20`.
38+
39+
**Constraints:**
40+
41+
* <code>1 <= nums.length <= 5 * 10<sup>5</sup></code>
42+
*`nums.length % 3 == 0`
43+
* <code>1 <= nums[i] <= 10<sup>9</sup></code>
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
packageg3601_3700.s3628_maximum_number_of_subsequences_after_one_inserting;
2+
3+
// #Medium #Weekly_Contest_460 #2025_07_27_Time_12_ms_(100.00%)_Space_45.76_MB_(72.28%)
4+
5+
publicclassSolution {
6+
publiclongnumOfSubsequences(Strings) {
7+
longtc =0;
8+
char[]chs =s.toCharArray();
9+
for (charc :chs) {
10+
tc += (c =='T') ?1 :0;
11+
}
12+
longls =0;
13+
longcs =0;
14+
longlcf =0;
15+
longctf =0;
16+
longlct =0;
17+
longocg =0;
18+
longtp =0;
19+
for (charcurr :chs) {
20+
longrt =tc -tp;
21+
longcg =ls *rt;
22+
ocg = (cg >ocg) ?cg :ocg;
23+
if (curr =='L') {
24+
ls++;
25+
}else {
26+
if (curr =='C') {
27+
cs++;
28+
lcf +=ls;
29+
}else {
30+
if (curr =='T') {
31+
lct +=lcf;
32+
ctf +=cs;
33+
tp++;
34+
}
35+
}
36+
}
37+
}
38+
longfcg =ls * (tc -tp);
39+
ocg =fcg >ocg ?fcg :ocg;
40+
longmaxi =0;
41+
long[]bo = {lcf,ctf,ocg};
42+
for (longop :bo) {
43+
maxi =op >maxi ?op :maxi;
44+
}
45+
returnlct +maxi;
46+
}
47+
}
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
3628\. Maximum Number of Subsequences After One Inserting
2+
3+
Medium
4+
5+
You are given a string`s` consisting of uppercase English letters.
6+
7+
You are allowed to insert**at most one** uppercase English letter at**any** position (including the beginning or end) of the string.
8+
9+
Return the**maximum** number of`"LCT"` subsequences that can be formed in the resulting string after**at most one insertion**.
10+
11+
**Example 1:**
12+
13+
**Input:** s = "LMCT"
14+
15+
**Output:** 2
16+
17+
**Explanation:**
18+
19+
We can insert a`"L"` at the beginning of the string s to make`"LLMCT"`, which has 2 subsequences, at indices[0, 3, 4] and[1, 3, 4].
20+
21+
**Example 2:**
22+
23+
**Input:** s = "LCCT"
24+
25+
**Output:** 4
26+
27+
**Explanation:**
28+
29+
We can insert a`"L"` at the beginning of the string s to make`"LLCCT"`, which has 4 subsequences, at indices[0, 2, 4],[0, 3, 4],[1, 2, 4] and[1, 3, 4].
30+
31+
**Example 3:**
32+
33+
**Input:** s = "L"
34+
35+
**Output:** 0
36+
37+
**Explanation:**
38+
39+
Since it is not possible to obtain the subsequence`"LCT"` by inserting a single letter, the result is 0.
40+
41+
**Constraints:**
42+
43+
* <code>1 <= s.length <= 10<sup>5</sup></code>
44+
*`s` consists of uppercase English letters.
Lines changed: 88 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,88 @@
1+
packageg3601_3700.s3629_minimum_jumps_to_reach_end_via_prime_teleportation;
2+
3+
// #Medium #Weekly_Contest_460 #2025_07_27_Time_116_ms_(99.81%)_Space_76.00_MB_(67.96%)
4+
5+
importjava.util.ArrayDeque;
6+
importjava.util.ArrayList;
7+
importjava.util.Arrays;
8+
9+
publicclassSolution {
10+
publicintminJumps(int[]nums) {
11+
intn =nums.length;
12+
if (n ==1) {
13+
return0;
14+
}
15+
intmaxVal =0;
16+
for (intv :nums) {
17+
maxVal =Math.max(maxVal,v);
18+
}
19+
boolean[]isPrime =sieve(maxVal);
20+
@SuppressWarnings("unchecked")
21+
ArrayList<Integer>[]posOfValue =newArrayList[maxVal +1];
22+
for (inti =0;i <n;i++) {
23+
intv =nums[i];
24+
if (posOfValue[v] ==null) {
25+
posOfValue[v] =newArrayList<>();
26+
}
27+
posOfValue[v].add(i);
28+
}
29+
boolean[]primeProcessed =newboolean[maxVal +1];
30+
int[]dist =newint[n];
31+
Arrays.fill(dist, -1);
32+
ArrayDeque<Integer>q =newArrayDeque<>();
33+
q.add(0);
34+
dist[0] =0;
35+
while (!q.isEmpty()) {
36+
inti =q.poll();
37+
intd =dist[i];
38+
if (i ==n -1) {
39+
returnd;
40+
}
41+
if (i +1 <n &&dist[i +1] == -1) {
42+
dist[i +1] =d +1;
43+
q.add(i +1);
44+
}
45+
if (i -1 >=0 &&dist[i -1] == -1) {
46+
dist[i -1] =d +1;
47+
q.add(i -1);
48+
}
49+
intv =nums[i];
50+
if (v <=maxVal &&isPrime[v] && !primeProcessed[v]) {
51+
for (intmult =v;mult <=maxVal;mult +=v) {
52+
ArrayList<Integer>list =posOfValue[mult];
53+
if (list !=null) {
54+
for (intidx :list) {
55+
if (dist[idx] == -1) {
56+
dist[idx] =d +1;
57+
q.add(idx);
58+
}
59+
}
60+
}
61+
}
62+
primeProcessed[v] =true;
63+
}
64+
}
65+
return -1;
66+
}
67+
68+
privateboolean[]sieve(intn) {
69+
boolean[]prime =newboolean[n +1];
70+
if (n >=2) {
71+
Arrays.fill(prime,true);
72+
}
73+
if (n >=0) {
74+
prime[0] =false;
75+
}
76+
if (n >=1) {
77+
prime[1] =false;
78+
}
79+
for (inti =2; (long)i *i <=n;i++) {
80+
if (prime[i]) {
81+
for (intj =i *i;j <=n;j +=i) {
82+
prime[j] =false;
83+
}
84+
}
85+
}
86+
returnprime;
87+
}
88+
}
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
3629\. Minimum Jumps to Reach End via Prime Teleportation
2+
3+
Medium
4+
5+
You are given an integer array`nums` of length`n`.
6+
7+
You start at index 0, and your goal is to reach index`n - 1`.
8+
9+
From any index`i`, you may perform one of the following operations:
10+
11+
***Adjacent Step**: Jump to index`i + 1` or`i - 1`, if the index is within bounds.
12+
***Prime Teleportation**: If`nums[i]` is a prime number`p`, you may instantly jump to any index`j != i` such that`nums[j] % p == 0`.
13+
14+
Return the**minimum** number of jumps required to reach index`n - 1`.
15+
16+
**Example 1:**
17+
18+
**Input:** nums =[1,2,4,6]
19+
20+
**Output:** 2
21+
22+
**Explanation:**
23+
24+
One optimal sequence of jumps is:
25+
26+
* Start at index`i = 0`. Take an adjacent step to index 1.
27+
* At index`i = 1`,`nums[1] = 2` is a prime number. Therefore, we teleport to index`i = 3` as`nums[3] = 6` is divisible by 2.
28+
29+
Thus, the answer is 2.
30+
31+
**Example 2:**
32+
33+
**Input:** nums =[2,3,4,7,9]
34+
35+
**Output:** 2
36+
37+
**Explanation:**
38+
39+
One optimal sequence of jumps is:
40+
41+
* Start at index`i = 0`. Take an adjacent step to index`i = 1`.
42+
* At index`i = 1`,`nums[1] = 3` is a prime number. Therefore, we teleport to index`i = 4` since`nums[4] = 9` is divisible by 3.
43+
44+
Thus, the answer is 2.
45+
46+
**Example 3:**
47+
48+
**Input:** nums =[4,6,5,8]
49+
50+
**Output:** 3
51+
52+
**Explanation:**
53+
54+
* Since no teleportation is possible, we move through`0 → 1 → 2 → 3`. Thus, the answer is 3.
55+
56+
**Constraints:**
57+
58+
* <code>1 <= n == nums.length <= 10<sup>5</sup></code>
59+
* <code>1 <= nums[i] <= 10<sup>6</sup></code>
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
packageg3601_3700.s3630_partition_array_for_maximum_xor_and_and;
2+
3+
// #Hard #Array #Math #Greedy #Enumeration #Weekly_Contest_460
4+
// #2025_07_31_Time_82_ms_(96.35%)_Space_50.76_MB_(39.58%)
5+
6+
publicclassSolution {
7+
publiclongmaximizeXorAndXor(int[]nums) {
8+
intn =nums.length;
9+
intfull =1 <<n;
10+
int[]xorMask =newint[full];
11+
int[]andMask =newint[full];
12+
int[]orMask =newint[full];
13+
for (intmask =1;mask <full;mask++) {
14+
intlb =mask & -mask;
15+
inti =Integer.numberOfTrailingZeros(lb);
16+
intprev =mask ^lb;
17+
xorMask[mask] =xorMask[prev] ^nums[i];
18+
andMask[mask] =prev ==0 ?nums[i] :andMask[prev] &nums[i];
19+
orMask[mask] =orMask[prev] |nums[i];
20+
}
21+
longbest =0;
22+
intall =full -1;
23+
for (intb =0;b <full;b++) {
24+
longandB =andMask[b];
25+
intrest =all ^b;
26+
if (andB +2L *orMask[rest] <=best) {
27+
continue;
28+
}
29+
for (inta =rest; ;a = (a -1) &rest) {
30+
intc =rest ^a;
31+
longsum =xorMask[a] +andB +xorMask[c];
32+
if (sum >best) {
33+
best =sum;
34+
}
35+
if (a ==0) {
36+
break;
37+
}
38+
}
39+
}
40+
returnbest;
41+
}
42+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp