AtCoder ABC 125 A&B&C&D AtCoder - 125
2019/05/22 Ajoutez le nom du problème
2019/06/27 Ajout d'une solution d'arbre de segmentation pour le problème C
A - Biscuit Generator
private void solveA() {
int a = nextInt();
int b = nextInt();
int t = nextInt();
int res = 0;
// double time = 0;
// while ((time += a) <= (t + 0.5)) {
// res += b;
// }
res = t / a * b;
out.println(res);
}
B - Resale
--X est $ \ sum_ {i = 1} ^ {n} V_i $ --Y est $ \ sum_ {i = 1} ^ {n} C_i $ -Parce que c'est la valeur maximale de $ X-Y $ --X devrait être plus grand -Ne comptez pas les paires avec $ V_i <C_i $
private void solveB() {
int numN = nextInt();
int[] v = IntStream.range(0, numN).map(i -> nextInt()).toArray();
int[] c = IntStream.range(0, numN).map(i -> nextInt()).toArray();
long res = 0;
for (int i = 0; i < numN; i++) {
if (v[i] > c[i]) {
res += (v[i] - c[i]);
}
}
out.println(res);
}
C - GCD on Blackboard
| position | GCD | |||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 1-5 GCD | |
| i=1 | 2 | 3 | 4 | 5 | 2-5 GCD | |
| i=2 | 1 | 3 | 4 | 5 | 1 et 3-5 GCD | |
| i=3 | 1 | 2 | 4 | 5 | 1-2 et 4-5 GCD | |
| i=4 | 1 | 2 | 3 | 5 | 1-3 et 5 GCD | |
| i=5 | 1 | 2 | 3 | 4 | 1-4 GCD |
-Lorsque $ i = 3 $, si vous prenez GCD avec GCD $ de 1-2 $ et GCD $ de 4-5 $, ce sera le GCD total.
- gcd(1-2,4-5)
/*
*Commentaire diffusé
* https://www.youtube.com/watch?v=8lm8o8L9Bmw
*/
private void solveC() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
long[] forward = new long[numN];
long[] backward = new long[numN];
long forGcd = 0;
long backGcd = 0;
for (int i = 0; i < numN; i++) {
forGcd = forward[i] = getGcd(forGcd, wk[i]);
backGcd = backward[numN - 1 - i] = getGcd(backGcd, wk[numN - 1 - i]);
}
long max = 1;
for (int i = 0; i < numN; i++) {
if (i == 0) {
max = Long.max(max, backward[i + 1]);
} else if (i == numN - 1) {
max = Long.max(max, forward[i - 1]);
} else {
max = Long.max(max, getGcd(forward[i - 1], backward[i + 1]));
}
}
out.println(max);
}
private long getGcd(long num1, long num2) {
long max = Long.max(num1, num2);
long min = Long.min(num1, num2);
if (min == 0) {
return max;
}
long amari = max % min;
while (amari != 0) {
max = min;
min = amari;
amari = max % min;
}
return min;
}
TLE
――Eh bien, parce que c'est un rappel, c'est aussi ...
private void solveC2() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
long maxGcd = 0;
for (int i = 0; i < numN; i++) {
long max = 0;
for (int j = 0; j < numN; j++) {
if (i == j) {
continue;
}
max = getGcd(max, wk[j]);
}
maxGcd = Long.max(maxGcd, max);
}
out.println(maxGcd);
}
référence: Record de dévotion professionnelle de Kenchon pour la compétition Pour vous qui souhaitez écrire une arborescence de segments dans Sora Technique de traitement de domination / requête complète sur l'arbre Structure des données dans le concours de programmation Concours de programmation Challenge Book P.153 ～
/**
* segment tree version
*
*Échantillon de valeur d'entrée
* [P-1]
* 3
* 7 6 8
*
* [P-2]
* 6
* 12 3 6 9 15 11
*
*/
private void solveC3() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
SegTree tree = new SegTree(numN);
/*
*Avant de définir
* [P-1]
* [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
*
* [P-2]
* [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647]
*/
for (int i = 0; i < wk.length; i++) {
tree.set(i, wk[i]);
}
/*
*Immédiatement après la fin de l'ensemble
* [P-1]
* [2147483647, 2147483647, 2147483647, 2147483647, 7, 6, 8, 2147483647]
*
* [P-2]
* [2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
*
*/
tree.update();
/*
*Immédiatement après la fin de la mise à jour
* [P-1]
* [2147483647, 1, 1, 1, 7, 6, 8, 2147483647]
*
*leaf est une valeur et node est un nombre promis
* 1( k 1)
* |----------------------|
* | |
* 1(2k 2) 1(2k+1 3)
* |--------| |----------|
* | | | |
* 7(2k 4) 6(2k+1 5) 8(2k 6) 2147483647(2k+1 7)
*
*
* [P-2]
* [2147483647, 1, 3, 1, 3, 3, 1, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
*
* 1( k 1)
* |----------------------------------------|
* | |
* 3(2k 2) 1(2k+1 3)
* |-----------------| |------------------------|
* | | | |
* 3(2k 4) 3(2k+1 5) 3(2k 6) 2147483647(2k+1 7)
* |-------| |------------| |----------| |--------------------|
* | | | | | | | |
* 12(2k 8) 3(2K+1 9) 6(2k 10) 9(2K+1 11) 15(2k 12) 11(2K+1 13) 2147483647(2k 14) 2147483647(2k+1 15)
*/
long res = 0;
for (int i = 0; i < numN; i++) {
/*
*Section semi-ouverte[)
* 0 - i
*GCD(je n'ai pas inclus)
*/
long left = tree.get(0, i);
/*
*Section semi-ouverte[)
* i+1 - numN(numN non inclus)
*GCD
*/
long right = tree.get(i + 1, numN);
res = Long.max(res, getGcd(left, right));
}
out.println(res);
}
/**
* segment tree
*Demi-arbre complet
* @author pc9801bx2
*
*/
private static class SegTree {
private long[] dat;
private int numOfElmSize;
private int numOfElm;
private SegTree(int numOfElm) {
this.numOfElm = numOfElm;
numOfElmSize = 1;
/*
*Réglage de la taille
*Déterminer le nombre d'éléments requis
*Exemple: numOfElm==Si 3 est numOfElmSize==4
*/
while (numOfElmSize < numOfElm) {
numOfElmSize *= 2;
}
/*
*Créer un tableau
* numOfElm==Si 3 est la taille==8
*/
dat = new long[numOfElmSize * 2];
Arrays.fill(dat, Integer.MAX_VALUE);
}
/**
*Créer un nœud parent
*/
private void update() {
/*
* segment tree
*Étant donné que la disposition des feuilles est emballée par l'arrière, recherchez par l'arrière
* dat[numOfElmSize]← Feuille la plus à gauche
* dat[numOfElmSize + n]← Feuille la plus à droite
*/
int k = numOfElmSize - 1;
/*
*À ce stade, il n'y a que des données sur les feuilles
*Créer séquentiellement à partir de l'extrémité la plus à droite du tableau
*/
while (k > 0) {
/*
*k parent
* K*2 côté gauche
* k*2+1 côté droit
*Créer à partir du parent de la feuille la plus à gauche
*/
dat[k] = getInnerGcd(dat[k * 2], dat[k * 2 + 1]);
k--;
}
}
/**
*Ensemble de valeurs
*
* @param a
* @param val
*/
private void set(int a, int val) {
/*
*Celui qui correspond à la première feuille
*Situé dans la seconde moitié du tableau
*Placez-le dans un endroit plus grand que numOfElmSize
*/
dat[a + numOfElmSize] = val;
}
/**
*
6
12 3 6 9 15 11
[2147483647, 1, 3, 1, 3, 3, 1, 2147483647, 12, 3, 6, 9, 15, 11, 2147483647, 2147483647]
1( k 1)
|----------------------------------------|
| |
3(2k 2) 1(2k+1 3)
|-----------------| |------------------------|
| | | |
3(2k 4) 3(2k+1 5) 3(2k 6) 2147483647(2k+1 7)
|-------| |------------| |----------| |--------------------|
| | | | | | | |
12(2k 8) 3(2K+1 9) 6(2k 10) 9(2K+1 11) 15(2k 12) 11(2K+1 13) 2147483647(2k 14) 2147483647(2k+1 15)
La transition lors du déplacement de i un par un vers la droite est décrite ci-dessous.
-------------------
[0:0):GCD=0
left 8
right 8
[1:6):GCD=1
left 9 -> 5 -> 3
right 14 -> 7 -> 3
-------------------
[2:6):GCD=1
left 10 -> 5 -> 3
right 14 -> 7 -> 3
-------------------
[0:2):GCD=3
left 8 -> 4 -> 2
right 10 -> 5 -> 2
[3:6):GCD=1
left 11 -> 6 -> 3
right 14 -> 7 -> 3
-------------------
[0:3):GCD=3
left 8 -> 4 -> 2
right 11 -> 5 -> 2
[4:6):GCD=1
left 12 -> 6 -> 3
right 14 -> 7 -> 3
-------------------
[0:4):GCD=3
left 8 -> 4 -> 2 -> 1
right 12 -> 6 -> 3 -> 1
[5:6):GCD=11
left 13 -> 7
right 14 -> 7
-------------------
[0:5):GCD=3
left 8 -> 4 -> 2 -> 1
right 13 -> 6 -> 3 -> 1
[6:6):GCD=0
left 14
right 14
*/
private long get(int a, int b) {
long leftGcd = 0;
long rightGcd = 0;
int left = a + numOfElmSize;
int right = b + numOfElmSize;
// System.out.println("a:b / " + a + " : " + b + " -- left : right / " + left + " : " + right);
/*
*Boucle pendant que les parents sont différents
*Suivez le parent supérieur pour trouver l'engagement maximum
*Si vous spécifiez la même position de feuille, il n'entrera pas dans la boucle,
*C'est(0,0)(n,n)Par conséquent, il n'est pas éligible à l'acquisition en premier lieu.-> [:)
*Donc, plutôt, je veux que 0 soit renvoyé.
*/
while (left < right) {
/*
*Lorsque la gauche est un nœud pair, je veux toute la plage.
*Je veux donc obtenir le parent au lieu de l'avoir ici.
*Pour même les nœuds
*moi même->Mes parents->Non apparié juste à côté du nœud pair->Transition avec le parent à droite
** Si tout est pair, et si cela devient impair au milieu, passez à la transition des nœuds impairs.
*
*Cependant, dans le cas de nœuds impairs (les feuilles peuvent être paires mais les nœuds peuvent être impairs),
*Je ne dois prendre que l'enfant et me déplacer vers la droite sans prendre le parent, donc
*Obtenir des valeurs individuelles (leftGcd==0 En d'autres termes, dans le cas des feuilles, prenez la valeur des feuilles)
*Au fait, leftGcd==Si 0, dat[i]Est retourné.
*Quand il y a des nœuds impairs
*moi même->Non apparié juste à côté du nœud pair->Transition avec le parent à droite
*/
if ((left & 1) == 1) {
leftGcd = getInnerGcd(leftGcd, dat[left]);
left++;
}
/*
*Lorsque la droite est un nœud impair, je veux toute la plage. .. Mais,
*Puisqu'il s'agit d'une section semi-ouverte, vous n'avez pas besoin de la laisser sur la droite.
** Je ne prends pas la partie numN, mais y a-t-il un problème? sur,
*En fait wk[numN]Puisque Inf est inclus dans la valeur de, vous pouvez l'ignorer.
*
*Je veux que le nœud aille au parent tel quel(Je veux que la valeur soit stockée dans le parent)Alors transition vers des nœuds pairs
*Vous pouvez maintenant aller voir vos parents la prochaine fois que vous venez.
* rightGcd==Si 0, dat[i]Est retourné.
*Quand il y a des nœuds impairs
*moi même->Nœuds pairs pairs->Transition avec parent commun à vous-même et nœud gauche
*
*Quand la droite est un nœud pair,
*moi même->Transition avec le parent
*/
if ((right & 1) == 1) {
--right;
rightGcd = getInnerGcd(rightGcd, dat[right]);
}
//Sélectionnez le nœud parent
left = left / 2;
right = right / 2;
// System.out.println("left : right / " + left + " : " + right);
}
long res = getInnerGcd(leftGcd, rightGcd);
// System.out.println("res : " + res);
return res;
}
/**
*GCD pour SegTree
* @param num1
* @param num2
* @return
*/
private long getInnerGcd(long num1, long num2) {
long max = Long.max(num1, num2);
long min = Long.min(num1, num2);
if (min == 0) {
return max;
}
long amari = max % min;
while (amari != 0) {
max = min;
min = amari;
amari = max % min;
}
return min;
}
}
――C'est plus facile que C. .. .. J'aurais dû faire D sans aller à C. .. ..
--Inverser plus et moins deux à la fois ――Si le moins est pair, vous pouvez faire une paire et en faire un plus
- est pairIl est possible d'éliminer - de la condition que $ A_i et A_ {i + 1} $ soient sélectionnés et inversés.
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| -1 | -2 | -3 | -4 | -10 | |
| 1,Inverser 2 | 1 | 2 | -3 | -4 | -4 |
| 3,Inverser 4 | 1 | 2 | 3 | 4 | 10 |
--Pattern 2 (Même si - est séparé, vous pouvez déplacer- pour le faire disparaître)
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| -1 | 2 | 3 | -4 | 0 | |
| 1,Inverser 2 | 1 | -2 | 3 | -4 | -2 |
| 2,Inverser 3 | 1 | 2 | -3 | -4 | -4 |
| 3,Inverser 4 | 1 | 2 | 3 | 4 | 10 |
- est étrangeIl est impossible d'éliminer - à cause de la condition que $ A_i et A_ {i + 1} $ sont sélectionnés et inversés.
| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| 1 | -2 | -3 | -4 | -8 | |
| 1,Inverser 2 | -1 | 2 | -3 | -4 | -6 |
| 3,Inverser 4 | -1 | 2 | 3 | 4 | 8 |
--Modèle 2 (écrit volontairement dans un détour)
--Déplacez - pour maximiser le total
-Peut être déplacé à la valeur minimale en valeur absolue (dans la figure)-Est en mouvement)-| 1 | 2 | 3 | 4 | total | |
|---|---|---|---|---|---|
| -1 | -2 | -3 | 4 | -8 | |
| 1,Inverser 2 | 1 | 2 | -3 | 4 | 4 |
| 3,Inverser 4 | 1 | 2 | 3 | -4 | 2 |
| 3,Inverser 4 | 1 | 2 | -3 | 4 | 4 |
| 2,Inverser 3 | 1 | -2 | 3 | 4 | 6 |
| 1,Inverser 2 | -1 | 2 | 3 | 4 | 8 |
/*
*Fusion des processus
*/
private void solveD() {
int numN = nextInt();
int[] wk = new int[numN];
int mCnt = 0;
long res = 0;
int zeroCnt = 0;
for (int i = 0; i < numN; i++) {
int val = nextInt();
if (val < 0) {
mCnt++;
}
if (val == 0) {
zeroCnt++;
}
wk[i] = Math.abs(val);
res += wk[i];
}
Arrays.sort(wk);
if (mCnt % 2 == 0 || zeroCnt > 0) {
out.println(res);
} else {
out.println(res - Math.abs(wk[0]) * 2);
}
}
――Je l'ai réécrit car il y a beaucoup de traitement supplémentaire, mais peut-être que le flux est plus facile à comprendre que la version en copie claire ci-dessus?
/*
*Pour obtenir ou compter les valeurs peuvent être fusionnées
*/
private void solveD2() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
int mCnt = 0;
long res = 0;
int zeroCnt = 0;
for (int i = 0; i < numN; i++) {
/*
*Compter les choses moins de 0
*/
if (wk[i] < 0) {
mCnt++;
}
/*
*Obtenez le grand total (abs)
*/
res += Math.abs(wk[i]);
/*
*Compter 0
*/
if (wk[i] == 0) {
zeroCnt++;
}
}
/*
* -Si est pair ou au moins un 0
*Toutes les valeurs+Peut être converti en
*Dans ce cas, additionnez simplement
*/
if (mCnt % 2 == 0 || zeroCnt > 0) {
out.println(res);
return;
} else {
/*
* -Est un nombre impair et il n'y a pas de 0
*Dans ce cas,|wk[i]|La plus petite valeur en-Peut être maximisé par
*Tout réécrire avec les abdos une fois
*/
for (int i = 0; i < wk.length; i++) {
wk[i] = Math.abs(wk[i]);
}
//Trier
Arrays.sort(wk);
for (int i = 0; i < wk.length; i++) {
/*
*× 2 est
*・ Total total qui ne doit pas être inclus dans le total- wk[i]
*・ Plus loin de la somme totale sans cette valeur-Total total- wk[i] - wk[i]
*/
if (wk[i] > 0) {
out.println(res - Math.abs(wk[i]) * 2);
return;
}
}
}
}
--Je ne comprends pas --J'ai juste essayé d'écrire l'éditorial
J'écrirai le contenu de dp [] [] correspondant à l'entrée, mais je n'en comprends pas le sens.
Revenons après avoir fait un concours de dp typique.
[Notez la valeur d'entrée]
5
10 -4 -8 -11 3
i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 10 / dp[i][1] : -10
i:2 / dp[i][0] : 6 / dp[i][1] : 14
i:3 / dp[i][0] : 22 / dp[i][1] : 14
i:4 / dp[i][0] : 25 / dp[i][1] : 33
i:5 / dp[i][0] : 30 / dp[i][1] : 36
30
5
10 -4 -8 -11 9
i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 10 / dp[i][1] : -10
i:2 / dp[i][0] : 6 / dp[i][1] : 14
i:3 / dp[i][0] : 22 / dp[i][1] : 14
i:4 / dp[i][0] : 25 / dp[i][1] : 33
i:5 / dp[i][0] : 34 / dp[i][1] : 42
34
5
8 8 8 8 8
i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : 8 / dp[i][1] : -8
i:2 / dp[i][0] : 16 / dp[i][1] : 0
i:3 / dp[i][0] : 24 / dp[i][1] : 8
i:4 / dp[i][0] : 32 / dp[i][1] : 16
i:5 / dp[i][0] : 40 / dp[i][1] : 24
40
5
-8 -8 -8 -8 -8
i:0 / dp[i][0] : 0 / dp[i][1] : -2147483648
i:1 / dp[i][0] : -8 / dp[i][1] : 8
i:2 / dp[i][0] : 16 / dp[i][1] : 0
i:3 / dp[i][0] : 8 / dp[i][1] : 24
i:4 / dp[i][0] : 32 / dp[i][1] : 16
i:5 / dp[i][0] : 24 / dp[i][1] : 40
24
private void solveD3() {
int numN = nextInt();
long[] wk = LongStream.range(0, numN).map(i -> nextInt()).toArray();
long[][] dp = new long[numN + 1][2];
dp[0][0] = 0;
dp[0][1] = Integer.MIN_VALUE;
for (int i = 0; i < numN; i++) {
dp[i + 1][0] = Long.max(dp[i][0] + wk[i], dp[i][1] - wk[i]);
dp[i + 1][1] = Long.max(dp[i][0] - wk[i], dp[i][1] + wk[i]);
out.println("i:" + i + " / dp[i][0] : " + dp[i][0] + " / dp[i][1] : " + dp[i][1]);
}
out.println("i:" + numN + " / dp[i][0] : " + dp[numN][0] + " / dp[i][1] : " + dp[numN][1]);
out.println(dp[numN][0]);
}
Recommended Posts