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

Commit478dc6c

Browse files
authored
Improved tasks 1659, 3435
1 parent4157c3e commit478dc6c

File tree

3 files changed

+163
-137
lines changed
  • src

3 files changed

+163
-137
lines changed
Lines changed: 81 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -1,74 +1,96 @@
11
packageg1601_1700.s1659_maximize_grid_happiness;
22

33
// #Hard #Dynamic_Programming #Bit_Manipulation #Bitmask #Memoization
4-
// #2022_04_23_Time_95_ms_(75.00%)_Space_53.1_MB_(58.33%)
4+
// #2025_04_04_Time_39_ms_(86.36%)_Space_54.76_MB_(72.73%)
55

6+
@SuppressWarnings("java:S107")
67
publicclassSolution {
7-
privateintm;
8-
privateintn;
9-
privateint[][][][][]dp;
10-
privateintnotPlace =0;
11-
privateintintro =1;
12-
privateintextro =2;
13-
privateintmod;
8+
privatestaticfinalintNONE =0;
9+
privatestaticfinalintINTROVERT =1;
10+
privatestaticfinalintEXTROVERT =2;
1411

15-
publicintgetMaxGridHappiness(intm,intn,intintrovertsCount,intextrovertsCount) {
16-
this.m =m;
17-
this.n =n;
18-
intnumOfState = (int)Math.pow(3,n);
19-
this.dp =newint[m][n][introvertsCount +1][extrovertsCount +1][numOfState];
20-
this.mod =numOfState /3;
21-
returndfs(0,0,introvertsCount,extrovertsCount,0);
22-
}
23-
24-
privateintdfs(intx,inty,intic,intec,intstate) {
25-
if (x ==m) {
12+
privateintmaxHappiness(
13+
intindex,
14+
intm,
15+
intn,
16+
intintroverts,
17+
intextroverts,
18+
intboard,
19+
int[][][][]dp,
20+
inttmask) {
21+
if (index >=m *n) {
2622
return0;
27-
}elseif (y ==n) {
28-
returndfs(x +1,0,ic,ec,state);
2923
}
30-
if (dp[x][y][ic][ec][state] !=0) {
31-
returndp[x][y][ic][ec][state];
24+
if (dp[index][introverts][extroverts][board] !=0) {
25+
returndp[index][introverts][extroverts][board];
3226
}
33-
// 1 - not place
34-
intmax =dfs(x,y +1,ic,ec, (state %mod) *3);
35-
intup =state /mod;
36-
intleft =state %3;
37-
// 2 - place intro
38-
if (ic >0) {
39-
inttemp =120;
40-
if (x >0 &&up !=notPlace) {
41-
temp -=30;
42-
temp +=up ==intro ? -30 :20;
43-
}
44-
if (y >0 &&left !=notPlace) {
45-
temp -=30;
46-
temp +=left ==intro ? -30 :20;
47-
}
48-
intnextState =state;
49-
nextState %=mod;
50-
nextState *=3;
51-
nextState +=intro;
52-
max =Math.max(max,temp +dfs(x,y +1,ic -1,ec,nextState));
27+
intintroScore = -1;
28+
intextroScore = -1;
29+
if (introverts >0) {
30+
intnewBoard = ((board <<2) |INTROVERT) &tmask;
31+
introScore =
32+
120
33+
+adjust(board,INTROVERT,n,index)
34+
+maxHappiness(
35+
index +1,
36+
m,
37+
n,
38+
introverts -1,
39+
extroverts,
40+
newBoard,
41+
dp,
42+
tmask);
43+
}
44+
if (extroverts >0) {
45+
intnewBoard = ((board <<2) |EXTROVERT) &tmask;
46+
extroScore =
47+
40
48+
+adjust(board,EXTROVERT,n,index)
49+
+maxHappiness(
50+
index +1,
51+
m,
52+
n,
53+
introverts,
54+
extroverts -1,
55+
newBoard,
56+
dp,
57+
tmask);
5358
}
54-
// 3 - place extro
55-
if (ec >0) {
56-
inttemp =40;
57-
if (x >0 &&up !=notPlace) {
58-
temp +=20;
59-
temp +=up ==intro ? -30 :20;
59+
intnewBoard = ((board <<2) |NONE) &tmask;
60+
intskip =maxHappiness(index +1,m,n,introverts,extroverts,newBoard,dp,tmask);
61+
dp[index][introverts][extroverts][board] =Math.max(skip,Math.max(introScore,extroScore));
62+
returndp[index][introverts][extroverts][board];
63+
}
64+
65+
privateintadjust(intboard,intthisIs,intcol,intindex) {
66+
intshiftBy =2 * (col -1);
67+
intleft =board &0x03;
68+
if (index %col ==0) {
69+
left =NONE;
70+
}
71+
intup = (board >>shiftBy) &0x03;
72+
int[]combination =newint[] {left,up};
73+
intadjustment =0;
74+
for (intneighbor :combination) {
75+
if (neighbor ==NONE) {
76+
continue;
6077
}
61-
if (y >0 &&left !=notPlace) {
62-
temp +=20;
63-
temp +=left ==intro ? -30 :20;
78+
if (neighbor ==INTROVERT &&thisIs ==INTROVERT) {
79+
adjustment -=60;
80+
}elseif (neighbor ==INTROVERT &&thisIs ==EXTROVERT) {
81+
adjustment -=10;
82+
}elseif (neighbor ==EXTROVERT &&thisIs ==INTROVERT) {
83+
adjustment -=10;
84+
}elseif (neighbor ==EXTROVERT &&thisIs ==EXTROVERT) {
85+
adjustment +=40;
6486
}
65-
intnextState =state;
66-
nextState %=mod;
67-
nextState *=3;
68-
nextState +=extro;
69-
max =Math.max(max,temp +dfs(x,y +1,ic,ec -1,nextState));
7087
}
71-
dp[x][y][ic][ec][state] =max;
72-
returnmax;
88+
returnadjustment;
89+
}
90+
91+
publicintgetMaxGridHappiness(intm,intn,intintrovertsCount,intextrovertsCount) {
92+
int[][][][]dp =newint[m *n][introvertsCount +1][extrovertsCount +1][(1 << (2 *n))];
93+
inttmask = (1 << (2 *n)) -1;
94+
returnmaxHappiness(0,m,n,introvertsCount,extrovertsCount,0,dp,tmask);
7395
}
7496
}
Lines changed: 80 additions & 76 deletions
Original file line numberDiff line numberDiff line change
@@ -1,109 +1,113 @@
11
packageg3401_3500.s3435_frequencies_of_shortest_supersequences;
22

33
// #Hard #Array #String #Bit_Manipulation #Graph #Enumeration #Topological_Sort
4-
// #2025_01_29_Time_16_ms_(95.35%)_Space_45.52_MB_(93.02%)
4+
// #2025_04_04_Time_20_ms_(97.26%)_Space_45.52_MB_(83.56%)
55

66
importjava.util.ArrayList;
7-
importjava.util.Arrays;
8-
importjava.util.HashSet;
97
importjava.util.List;
10-
importjava.util.Set;
118

9+
@SuppressWarnings("unchecked")
1210
publicclassSolution {
13-
privateintm;
14-
privateintforcedMask;
15-
privateint[]adj;
16-
privatechar[]idxToChar =newchar[26];
17-
privateint[]charToIdx =newint[26];
18-
privateboolean[]used =newboolean[26];
11+
privateintmin =Integer.MAX_VALUE;
12+
privateList<int[]>lists =newArrayList<>();
1913

2014
publicList<List<Integer>>supersequences(String[]words) {
21-
Arrays.fill(charToIdx, -1);
22-
for (Stringw :words) {
23-
used[w.charAt(0) -'a'] =true;
24-
used[w.charAt(1) -'a'] =true;
15+
boolean[][]pairs =newboolean[26][26];
16+
int[]counts =newint[26];
17+
for (Stringword :words) {
18+
inta =word.charAt(0) -'a';
19+
intb =word.charAt(1) -'a';
20+
if (!pairs[a][b]) {
21+
pairs[a][b] =true;
22+
counts[a]++;
23+
counts[b]++;
24+
}
25+
}
26+
List<Integer>[]links =newArrayList[26];
27+
for (inti =0;i <26;i++) {
28+
links[i] =newArrayList<>();
2529
}
26-
// Map each used letter to an index [0..m-1]
27-
for (intc =0;c <26;c++) {
28-
if (used[c]) {
29-
idxToChar[m] = (char) (c +'a');
30-
charToIdx[c] =m++;
30+
int[]counts1 =newint[26];
31+
int[]sides =newint[26];
32+
for (inti =0;i <26;i++) {
33+
for (intj =0;j <26;j++) {
34+
if (pairs[i][j]) {
35+
links[i].add(j);
36+
counts1[j]++;
37+
sides[i] |=1;
38+
sides[j] |=2;
39+
}
3140
}
3241
}
33-
adj =newint[m];
34-
// Build graph and record forced duplicates
35-
for (Stringw :words) {
36-
intu =charToIdx[w.charAt(0) -'a'];
37-
intv =charToIdx[w.charAt(1) -'a'];
38-
if (u ==v) {
39-
forcedMask |= (1 <<u);
42+
int[]arr =newint[26];
43+
for (inti =0;i <26;i++) {
44+
if (counts[i] <=1) {
45+
arr[i] =counts[i];
46+
}elseif (counts1[i] ==0 ||sides[i] !=3) {
47+
arr[i] =1;
48+
}elseif (pairs[i][i]) {
49+
arr[i] =2;
4050
}else {
41-
adj[u] |= (1 <<v);
51+
arr[i] = -1;
4252
}
4353
}
44-
// Try all supersets of forcedMask; keep those that kill all cycles
45-
intbest =9999;
46-
List<Integer>goodSets =newArrayList<>();
47-
for (ints =0;s < (1 <<m);s++) {
48-
if ((s &forcedMask) !=forcedMask) {
49-
continue;
50-
}
51-
intsize =Integer.bitCount(s);
52-
if (size <=best && !hasCycle(s)) {
53-
if (size <best) {
54-
best =size;
55-
goodSets.clear();
56-
}
57-
goodSets.add(s);
54+
dfs(links,0,arr,newint[26],0);
55+
List<List<Integer>>res =newArrayList<>();
56+
for (int[]arr1 :lists) {
57+
List<Integer>list =newArrayList<>();
58+
for (intn :arr1) {
59+
list.add(n);
5860
}
61+
res.add(list);
62+
}
63+
returnres;
64+
}
65+
66+
privatevoiddfs(List<Integer>[]links,inti,int[]arr1,int[]arr,intn) {
67+
if (n >min) {
68+
return;
5969
}
60-
// Build distinct freq arrays from these sets
61-
Set<String>seen =newHashSet<>();
62-
List<List<Integer>>ans =newArrayList<>();
63-
for (ints :goodSets) {
64-
int[]freq =newint[26];
65-
for (inti =0;i <m;i++) {
66-
freq[idxToChar[i] -'a'] = ((s & (1 <<i)) !=0) ?2 :1;
70+
if (i ==26) {
71+
if (!chk(links,arr)) {
72+
return;
6773
}
68-
Stringkey =Arrays.toString(freq);
69-
if (seen.add(key)) {
70-
List<Integer>tmp =newArrayList<>();
71-
for (intf :freq) {
72-
tmp.add(f);
73-
}
74-
ans.add(tmp);
74+
if (n <min) {
75+
min =n;
76+
lists =newArrayList<>();
77+
lists.add(arr.clone());
78+
}elseif (n ==min) {
79+
lists.add(arr.clone());
7580
}
81+
return;
82+
}
83+
if (arr1[i] >=0) {
84+
arr[i] =arr1[i];
85+
dfs(links,i +1,arr1,arr,n +arr1[i]);
86+
}else {
87+
arr[i] =1;
88+
dfs(links,i +1,arr1,arr,n +1);
89+
arr[i] =2;
90+
dfs(links,i +1,arr1,arr,n +2);
7691
}
77-
returnans;
7892
}
7993

80-
privatebooleanhasCycle(intmask) {
81-
int[]color =newint[m];
82-
for (inti =0;i <m;i++) {
83-
if (((mask >>i) &1) ==0 &&color[i] ==0 &&dfs(i,color,mask)) {
84-
returntrue;
94+
privatebooleanchk(List<Integer>[]links,int[]arr) {
95+
for (inti =0;i <26;i++) {
96+
if (arr[i] ==1 &&dfs1(links,arr,newboolean[26],i)) {
97+
returnfalse;
8598
}
8699
}
87-
returnfalse;
100+
returntrue;
88101
}
89102

90-
privatebooleandfs(intu,int[]color,intmask) {
91-
color[u] =1;
92-
intnxt =adj[u];
93-
while (nxt !=0) {
94-
intv =Integer.numberOfTrailingZeros(nxt);
95-
nxt &= (nxt -1);
96-
if (((mask >>v) &1) ==1) {
97-
continue;
98-
}
99-
if (color[v] ==1) {
100-
returntrue;
101-
}
102-
if (color[v] ==0 &&dfs(v,color,mask)) {
103+
privatebooleandfs1(List<Integer>[]links,int[]arr,boolean[]seens,inti) {
104+
seens[i] =true;
105+
for (intnext :links[i]) {
106+
if (arr[next] ==1 && (seens[next] ||dfs1(links,arr,seens,next))) {
103107
returntrue;
104108
}
105109
}
106-
color[u] =2;
110+
seens[i] =false;
107111
returnfalse;
108112
}
109113
}

‎src/test/java/g3401_3500/s3435_frequencies_of_shortest_supersequences/SolutionTest.java

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -14,10 +14,10 @@ void supersequences() {
1414
equalTo(
1515
List.of(
1616
List.of(
17-
2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
17+
1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1818
0,0,0,0,0,0),
1919
List.of(
20-
1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
20+
2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
2121
0,0,0,0,0,0))));
2222
}
2323

0 commit comments

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