AtCoder ABC 025 A&B&C
A問題
- 入力の文字列が昇順に並んでいるのでそのまま文字を組んでみる
- [a,b,c,d,e] が入力値なら
- [a,a][a,b][a,c]・・・[b,a][b,b][b,c]・・・[e,a][e,b]・・・[e,e]
- 昇順の為、そのままループを回しても辞書順になってくれる
- [a,b,c,d,e] が入力値なら
private void solveA() {
char[] wk = next().toCharArray();
int n = nextInt();
int cnt = 0;
for (int i = 0; i < wk.length; i++) {
for (int j = 0; j < wk.length; j++) {
cnt++;
if (n == cnt) {
out.println((char) wk[i] + "" + (char) wk[j]);
return;
}
}
}
}
B問題
- 以下のように決め打ち
- 東にいるときは+座標
- 西にいるときは-座標
- 決め打ちの状態で、入力値を単純に$\pm$すると、最後に東にいるのか西にいるのかわかる
うーーん。Stream、こんなところで使ってもメリットなさそうな感じがする。
private void solveB() {
int n = nextInt();
int a = nextInt();
int b = nextInt();
long res = 0;
res = IntStream.range(0, n).reduce(0, (sum, i) -> {
String direction = next();
int meter = nextInt();
long move = meter < a ? a : meter > b ? b : meter;
switch (direction) {
case "East":
sum -= move;
break;
case "West":
sum += move;
break;
default:
throw new IllegalArgumentException();
}
return sum;
});
//--------------------------------------------------------
// String[] direction = new String[n];
// int[] meter = new int[n];
//
// for (int i = 0; i < n; i++) {
// direction[i] = next();
// meter[i] = nextInt();
// long move = meter[i] < a ? a : meter[i] > b ? b : meter[i];
// switch (direction[i]) {
// case "East":
// res -= move;
// break;
// case "West":
// res += move;
// break;
// default:
// throw new IllegalArgumentException();
// }
// }
//--------------------------------------------------------
out.println(res == 0 ? 0 : res > 0 ? "West " + res : "East " + res * -1);
}
C問題
-
解説だと手番=9からスタートしているけどいまいち理解が追い付かない部分があったので、手番=1から順に石を置いて行っておいたときの点数を全て比較することにした（結果として623530回再帰関数呼ばれるが）
- どちらも最善の場所に置きたいので、その手番での最大点数を採用する
-
memo化で早くできそうではあるが、上手くメモ化できなかったので今度対応してみる
private void solveC() {
int[][] b = new int[2][3];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 3; j++) {
b[i][j] = nextInt();
}
}
int[][] c = new int[3][2];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = nextInt();
}
}
/*
* 既にどちらかの石が置いてある、まだ誰も置いていない
* を表現するため、boardはint[][]を利用
* 0ならだれも置いていない
* boolean[][]でもできるけど、デバッグのために1/-1をみたかった
*/
int[] res = calcPointC(b, c, new int[3][3], 0, true);
out.println(res[0]);
out.println(res[1]);
}
// int cnt = 1;
/**
* 再帰で調査
* @param b
* @param c
* @param board
* @param turn
* @param who
* @return
*/
private int[] calcPointC(int[][] b, int[][] c, int[][] board, int turn, boolean who) {
if (turn == 9) {
int chokudai = 0;
int chokuko = 0;
/*
* 全て置き終わったので計算開始
*/
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i < 2) {
if (board[i][j] == board[i + 1][j]) {
chokudai += b[i][j];
} else {
chokuko += b[i][j];
}
}
if (j < 2) {
if (board[i][j] == board[i][j + 1]) {
chokudai += c[i][j];
} else {
chokuko += c[i][j];
}
}
}
}
return new int[] { chokudai, chokuko };
}
List<int[]> resList = new ArrayList<int[]>();
/*
* whoの手番における最大の点数を調べる
* whoの最大の点数が最善を尽くした場合の点数
*/
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
// if (i == 0 && j == 0) {
// out.println(cnt++);
// }
/*
* 既に置いてある
*/
if (board[i][j] != 0) {
continue;
}
if (who) {
board[i][j] = 1;
} else {
board[i][j] = -1;
}
/*
* whoの手番
* とりあえずおいてみて、この位置に置いたら何点になるのかを記録
* 最終的には、whoの手番で最大の点数を調べるためここではしらみつぶし
*/
resList.add(calcPointC(b, c, board, turn + 1, !who));
/*
* 置く位置を変更するため、この位置に置いた石をリセットする
*/
board[i][j] = 0;
}
}
/*
* 交互に最大点数を返すのは、それぞれが最善を尽くす前提の為
* 交互に最大点数を返した結果の値がresult
*/
if (who) {
//chokudaiの手番なので、chokudaiの最大値が入っているarrayをreturn
return resList.stream().max(Comparator.comparing(x -> x[0])).get();
} else {
//chokukoの手番なので、chokukoの最大値が入っているarrayをreturn
return resList.stream().max(Comparator.comparing(x -> x[1])).get();
}
}