AtCoder ABC 023 A&B&C AtCoder - 023
private void solveA() {
int x = nextInt();
int res = 0;
while (x != 0) {
res += x % 10;
x /= 10;
}
out.println(res);
}
"Da die Reihenfolge der Kombination von" a "," c "und" b "nicht berücksichtigt wird", handelt es sich tatsächlich um eine "Lügenlösung". .. .. Ein Fix wird bald kommen.
'a' xxx 'c'
- 'c' xxx 'a'
- 'b' xxx 'b'
――Sehen Sie links und rechts nach dem mittleren "b" private void solveB() {
int numN = nextInt();
String s = next();
if ((numN & 1) == 0) {
out.println(-1);
return;
}
int max = numN / 2;
int res = 0;
for (int i = 0; i < max; i++) {
char down = s.charAt((numN - 1) - (max + 1) - i);
char up = s.charAt((max + 1) + i);
if ((down == 'a' && up == 'c') || (down == 'c' && up == 'a') || (down == 'b' && up == 'b')) {
res = i + 1;
} else {
out.println(-1);
return;
}
}
out.println(res);
}
AtCoder Beginner Contest 023 Erklärung S.12 ~
-Ich schreibe nur eine Beilage über [Feineinstellung \ Untersuchen, wo die Süßigkeiten platziert wurden]
| col no\row no | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| col count\Reihenanzahl | 2 | 1 | 2 | ||
| 1 | 1 | 〇 | |||
| 2 | 2 | 〇 | 〇 | ||
| 3 | 2 | 〇 | 〇 |
Wenn der Ort, an dem Sie die Süßigkeiten ablegen, $ col count + row count = K $ ist, zählen Sie die Orte, die nicht gezählt werden sollten.
| col no\row no | 1 | 2 | 3 | ||
|---|---|---|---|---|---|
| col count\Reihenanzahl | 2 | 1 | 2 | ||
| 1 | 1 | 〇 | |||
| 2 | 2 | 〇 | 〇 | ||
| 3 | 2 | 〇 | 〇 |
Wenn k = 3
An der Position von $ (Spalte Nr., Zeile Nr.) = (3,3) $ können Sie problemlos 3 Süßigkeiten erhalten.
$ (col count, row count) = (2,2) $, also ist die Summe 4
Wenn der Ort, an dem Sie die Süßigkeiten ablegen, $ col count + row count = K + 1 $ ist, werden die Süßigkeiten zweimal gezählt. ―― +1, weil ich die Süßigkeiten gezählt habe, die ich zweimal gelegt habe
private void solveC() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
int[] rI = new int[n];
int[] cI = new int[n];
int[] rP = new int[r + 1];
int[] cP = new int[c + 1];
for (int i = 0; i < n; i++) {
int tmpR = nextInt() - 1;
int tmpC = nextInt() - 1;
rI[i] = tmpR;
cI[i] = tmpC;
//Anzahl der Süßigkeiten für jede Zeile von r
rP[tmpR]++;
//Anzahl der Süßigkeiten für jede Spalte von c
cP[tmpC]++;
}
/*
*Aggregieren Sie die Anzahl der Süßigkeiten für jede Reihe
*Wenn diese Nummer für jede Zeile gilt
* [1, 2, 2, 0]
*Zählen Sie wie folgt
* 0=1
* 1=1
* 2=2
* 3=0
*Die rPCount-Größe ist N.+1 ist, weil es keine Süßigkeiten mehr gibt
*/
int[] rPCount = new int[n + 1];
for (int i = 0; i < r; i++) {
rPCount[rP[i]]++;
}
//Verarbeiten Sie jede Spalte wie eine Zeile
int[] cPCount = new int[n + 1];
for (int i = 0; i < c; i++) {
cPCount[cP[i]]++;
}
long res = 0;
/*
*Berechnen Sie die Kombination grob
*Für Eingabebeispiel 1:
*Wenn die Anzahl der Süßigkeiten in der Reihe 0 ist, muss die Anzahl der Süßigkeiten in Spalte 3 sein
*aus diesem Grund,[Anzahl der Zeilen, in denen r Candy 0 ist]×[Die Anzahl der Zeilen, in denen die Süßigkeit von c 3 beträgt]Berechnung
*Wenn die Anzahl der Süßigkeiten in der Reihe 1 beträgt, muss die Anzahl der Süßigkeiten in Spalte 2 betragen.
* [Anzahl der Zeilen, in denen r Süßigkeiten 1 sind]×[Die Anzahl der Zeilen, in denen die Süßigkeit von c 2 beträgt]Berechnung
*Dies ergibt eine grobe Kombination
*/
for (int i = 0; i <= k; i++) {
res += rPCount[i] * cPCount[k - i];
}
/*
*Optimieren
*Untersuchen Sie, wo die Süßigkeiten platziert wurden
*/
for (int i = 0; i < n; i++) {
long sum = rP[rI[i]] + cP[cI[i]];
if (sum == k) {
/*
*Die Tatsache, dass die Summe gleich K ist, zählt die Objekte, die bei der groben Kombinationsberechnung nicht gezählt werden sollten.
*Daher wird diese Position von der Zählung ausgeschlossen
*/
res--;
} else if (sum == k + 1) {
/*
*Die Summe ist K.+1 liegt zum Zeitpunkt der groben Kombinationsberechnung außerhalb des Zählbereichs
*Daher zählt diese Position
*/
res++;
}
}
out.println(res);
}
--Ist der Speicher niedrig? Es scheint, aber die Geschwindigkeit ist nicht genug. .. ..
private void solveC3() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
// int[][] masu = new int[r][c];
Map<Integer, Set<Integer>> wk = new HashMap<Integer, Set<Integer>>();
int[] rP = new int[r];
int[] cP = new int[c];
for (int i = 0; i < n; i++) {
int tmpR = nextInt() - 1;
int tmpC = nextInt() - 1;
// masu[tmpR][tmpC] = 1;
Set<Integer> tmpSet = new HashSet<Integer>();
tmpSet.add(tmpC);
wk.merge(tmpR, tmpSet, (oldV, newV) -> {
oldV.addAll(newV);
return oldV;
});
rP[tmpR]++;
cP[tmpC]++;
}
long res = 0;
Set<Integer> defSet = new HashSet<Integer>();
for (int i = 0; i < rP.length; i++) {
for (int j = 0; j < cP.length; j++) {
int val = wk.getOrDefault(i, defSet).contains(j) ? 1 : 0;
// int val = wk.getOrDefault(i, new HashSet<Integer>()).contains(j) ? 1 : 0;
if (rP[i] + cP[j] - val == k) {
res++;
}
}
}
out.println(res);
}
/**
* MLE
*/
private void solveC2() {
int r = nextInt();
int c = nextInt();
int k = nextInt();
int n = nextInt();
int[][] masu = new int[r][c];
int[] rP = new int[r];
int[] cP = new int[c];
for (int i = 0; i < n; i++) {
int tmpR = nextInt();
int tmpC = nextInt();
masu[tmpR - 1][tmpC - 1] = 1;
rP[tmpR - 1]++;
cP[tmpC - 1]++;
}
long res = 0;
for (int i = 0; i < rP.length; i++) {
for (int j = 0; j < cP.length; j++) {
if (rP[i] + cP[j] - masu[i][j] == k) {
res++;
}
}
}
out.println(res);
}
Recommended Posts