221th, +1/-1 challenge
250
配列中の任意の2箇所を入れ替えた時にできる配列の異なり数。
文字列化してsetに入れて数えただけ。
import java.util.HashSet; public class TheSwapsDivTwo { public int find(int[] sequence) { HashSet<String> set = new HashSet<String>(); int L = sequence.length; for(int i = 0; i < L; i++) { for(int j = i + 1; j < L; j++) { String temp = ""; for(int k = 0; k < L; k++) { int cand = -1; if(k == i) { cand = sequence[j]; } else if (k == j) { cand = sequence[i]; } else { cand = sequence[k]; } if(cand < 10) { temp += "0"; } temp += Integer.toString(cand); } set.add(temp); } } return set.size(); } }
500
二人のプレイヤーが交互に、現在の数nからnの約数を引いていった時の勝者を答える。
蟻本でコインを取っていく話とかNimとかGrundy数とかを読んでいたのでそれ系かなーと思ったけどすぐには書けず。
結局DPで簡単に書けました
入力が1だと間違った答えを返す人がいたのでchallengeして成功。
import java.util.ArrayList; public class TheNumberGameDivTwo { public String find(int n) { ArrayList<ArrayList<Integer>> divs = new ArrayList<ArrayList<Integer>>(); for(int i = 0; i < 1001; i++) { divs.add(new ArrayList<Integer>()); } for(int i = 2; i < 1001; i++) { for(int j = 2; j < 1001; j++) { if(i == j) { continue; } if(i % j == 0) { divs.get(i).add(j); } } } boolean win[] = new boolean[1001]; win[0] = false; win[1] = false; for(int i = 2; i < 1001; i++) { win[i] = false; for(int x : divs.get(i)) { win[i] |= x <= i && !win[i - x]; } } if(win[n]) { return "John"; } else { return "Brus"; } } }
1000
チェス盤の駒が置かれていない部分にL字型のブロックを置いていく時に、置ける最大の個数を求める。
ただしL字ブロックの角の部分が黒いマス(i + jが偶数)になるようにする。
残り20分ぐらいしかなかったので、とりあえず左上から貪欲においていったら、案の定サンプルすら通らず。
public class TheTilesDivTwo { public int find(String[] board) { int L = board.length; int L2 = board[0].length(); int state[][] = new int[L + 2][L2 + 2]; for(int i = 0; i < L ; i++) { for(int j = 0; j < L2; j++) { if(board[i].charAt(j) == '.') { state[i + 1][j + 1] = 1; } else { state[i + 1][j + 1] = 0; } } } int count = 0; for(int i = 0; i < L ; i++) { for(int j = 0; j < L2; j++) { if((state[i + 1][j + 1] == 1) && (i + j) % 2 == 0) { if((state[i][j + 1] == 1) && (state[i + 1][j] == 1)) { state[i + 1][j + 1] = 2; state[i][j + 1] = 2; state[i + 1][j] = 2; count++; } else if((state[i][j + 1] == 1) && (state[i + 1][j + 2] == 1)) { state[i + 1][j + 1] = 2; state[i][j + 1] = 2; state[i + 1][j + 2] = 2; count++; } else if((state[i + 2][j + 1] == 1) && (state[i + 1][j] == 1)) { state[i + 1][j + 1] = 2; state[i + 2][j + 1] = 2; state[i + 1][j] = 2; count++; } else if((state[i + 2][j + 1] == 1) && (state[i + 1][j + 2] == 1)) { state[i + 1][j + 1] = 2; state[i + 2][j + 1] = 2; state[i + 1][j + 2] = 2; count++; } } } } return count; } }