AtCoder ABC 026 A&B&C
- ABC027すごい悩んだのに、、、難易度差が激しい
A問題
- $(x,y)$の組み合わせを全部試す
private void solveA() {
final int a = nextInt();
int res = IntStream.range(1, a).reduce(0, (sum, i) -> Integer.max(i * (a - i), sum));
out.println(res);
}
B問題
- 外から赤→白に塗っていく
- 最後、
Math.PIを使わずに3.1415って手入力したらNGでした
private void solveB() {
int numN = nextInt();
int[] wk = IntStream.range(0, numN).map(i -> nextInt()).toArray();
Arrays.sort(wk);
long res = 0;
boolean isRed = true;
for (int i = 0; i < wk.length; i++) {
res += Math.pow(wk[numN - 1 - i], 2) * (isRed ? 1 : -1);
isRed = !isRed;
}
double mul = res * Math.PI;
out.println(mul);
}
C問題：class利用
-
上司が入力されている配列を渡される
-
社員番号が小さい上司がただ一人存在するとの記述から後ろから見ていけば、一番最後の人がわかる？ - 前から見ていくと自分の部下を探すことになるけど、後ろから見ていけば自分の上司を探すことになる
- 上司の給料は部下によって決まるので後ろからみていったほうがよさそう
-
-
冗長だけどclassを作成して自分の給料を表現した
- 給料表現しているのに
BOSSなのは。。。
- 給料表現しているのに
-
自分の給料を計算し、計算結果をもとにBOSSの給料を計算する
private void solveC() {
int numN = nextInt();
/*
* Index=0 -> B2
* Index=-1 -> B1
*/
int[] wk = IntStream.range(0, numN - 1).map(i -> nextInt()).toArray();
/*
* 部下リスト
*/
Boss[] wkList = new Boss[numN - 1];
/*
* 高橋専用
*/
Boss takahashi = new Boss();
/*
* 最後から実行すれば必ず上司がいる。よね？
* (高橋が上司を除く)
*/
for (int i = wk.length - 1; i >= 0; i--) {
/*
* 自分の給与を取得
*/
int salary = getSelfSalary(wkList, i);
/*
* bossの番号とindexを合わせる
* 高橋がbossの場合は-1になる
*/
int bossNum = wk[i] - 2;
/*
* 上司の部下リスト取得
* 上司のリストに自分の給与を登録（合算？）
*/
if (bossNum == -1) {
/*
* BOSSが高橋なのでサラリーを+
* 高橋であってもmaxとmin+1の制約が掛かるので
*/
takahashi.setMax(salary);
takahashi.setMin(salary);
takahashi.addMembers(1);
} else {
Boss boss = wkList[bossNum];
if (boss == null) {
/*
* 今まで部下がいなかった上司なので登録
*/
boss = new Boss();
wkList[bossNum] = boss;
}
boss.setMax(salary);
boss.setMin(salary);
boss.addMembers(1);
}
}
out.println(takahashi.getMax() + takahashi.getMin() + 1);
}
/**
* 自分の部下リスト取得して、
* 自分の給与計算
* @param wkList
* @param i
* @return
*/
private int getSelfSalary(Boss[] wkList, int i) {
int salary;
Boss self = wkList[i];
if (self != null) {
int min = self.getMin();
int max = self.getMax();
salary = max + min + 1;
} else {
salary = 1;
}
return salary;
}
/**
* 自分の部下の数と
* 自分の給与の最大と最小を保持する
* @author works
*
*/
private static class Boss {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
int members;
public int getMembers() {
return members;
}
public void addMembers(int member) {
this.members += member;
}
public int getMin() {
return min;
}
public int getMax() {
return max;
}
public void setMin(int min) {
this.min = Integer.min(this.min, min);
}
public void setMax(int max) {
this.max = Integer.max(this.max, max);
}
}
C問題：List
classを利用して計算したけど、コレListでもできるよね？？？
と思って、Listで表現してみました。
classより大分速かったです
private void solveC2() {
int numN = nextInt();
/*
* Index=0 -> B2
* Index=-1 -> B1
*/
int[] wk = new int[numN + 1];
List<List<Integer>> mems = new ArrayList<List<Integer>>();
wk[0] = 0;
wk[1] = 0;
mems.add(new ArrayList<Integer>());
mems.add(new ArrayList<Integer>());
for (int i = 0; i < numN - 1; i++) {
wk[i + 2] = nextInt();
mems.add(new ArrayList<Integer>());
}
for (int i = wk.length - 1; i >= 0; i--) {
List<Integer> tmp = mems.get(i);
int salary = 0;
if (tmp.size() != 0) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int j = 0; j < tmp.size(); j++) {
min = Integer.min(min, tmp.get(j));
max = Integer.max(max, tmp.get(j));
}
salary = min + max + 1;
} else {
salary = 1;
}
tmp = mems.get(wk[i]);
tmp.add(salary);
}
long salary = 0;
{
List<Integer> tmp = mems.get(1);
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int j = 0; j < tmp.size(); j++) {
min = Integer.min(min, tmp.get(j));
max = Integer.max(max, tmp.get(j));
}
salary = min + max + 1;
}
out.println(salary);
}