1167→1172.青コーダーへの道は遠い…….
Easyを解いてMediumはシステムテストで落とされる.チャレンジ5つ成功1つ失敗.
Easy
文字列が回文にするための最小のコストを求める.
端っこから真ん中まで1つずつ確かめていくだけ.
public class MinCostPalindrome { public int getMinimum(String s, int oCost, int xCost) { int len = s.length(); int min = Math.min(oCost, xCost); int sum = 0; for(int i = 0; i < len / 2; i++) { if(s.charAt(i) == s.charAt(len - 1 - i) && s.charAt(i) == '?') { sum += min * 2; } if((s.charAt(i) == 'x' && s.charAt(len - 1 - i) == 'o') || (s.charAt(i) == 'o' && s.charAt(len - 1 - i) == 'x')) { return -1; } if((s.charAt(i) == 'x' && s.charAt(len - 1 - i) == '?') || (s.charAt(i) == '?' && s.charAt(len - 1 - i) == 'x')) { sum += xCost; } if((s.charAt(i) == 'o' && s.charAt(len - 1 - i) == '?') || (s.charAt(i) == '?' && s.charAt(len - 1 - i) == 'o')) { sum += oCost; } } return sum; } }
Medium
長さがちょうど10のうなぎしか食べられないので,与えられた切断回数で最も多く食べられるうなぎの数を答える.
最初に10で割り切れるうなぎをやらないとダメ.20は1回切ると10+10になる
5人撃墜したけど,自分もSystem Testで死亡.
import java.util.Arrays; public class Cut { public int getMaximum(int[] eelLengths, int maxCuts) { int len = eelLengths.length; int sum = 0; int count = 0; for(int i = 1; i < len; i++) { if((eelLengths[i] % 10 == 0)) { int temp = eelLengths[count]; eelLengths[count] = eelLengths[i]; eelLengths[i] = temp; count++; } } Arrays.sort(eelLengths, 0, count); for(int i = 0; i < len; i++) { if(eelLengths[i] == 10) { sum += 1; } else if(eelLengths[i] > 10 && maxCuts > 0) { while(eelLengths[i] > 10 && maxCuts > 0) { sum++; eelLengths[i] -= 10; maxCuts--; } if(eelLengths[i] == 10) { sum++; } } } return sum; } }
Hard
蚊の初期位置と移動速度が与えられ,半径Rの爆弾で殺せる最大の数を求める.
任意の2つの蚊を選べばその蚊の間の距離が2Rになる時間tが計算できる.
tがわかれば2Rの範囲内にある蚊の数を求めるのは簡単なので,すべての組み合わせに対して時間tを求めれば良い.
ちゃんと動かず.
import java.util.Arrays; public class Mosquitoes { public int getMaximum(int[] xInit, int[] v, int R) { int len = xInit.length; if(len == 1) { return 1; } double [] temp = new double[len]; int max = 1; for(int j = 0; j < len; j++) { for(int k = 0; k < len; k++) { if(j == k) { continue; } if(true) { double t = ((double)2*R + xInit[j] - xInit[k]) / (v[k] - v[j]); if(t >= 0) { System.out.println("j: " + j + ", k: " + k + ", t: " + t); for(int i = 0; i < len; i++) { temp[i] = xInit[i] + v[i] * t; } Arrays.sort(temp); int head = 0; int tail = 0; while(head < len && tail < len - 1) { if(Math.abs(temp[head] - temp[tail + 1]) <= 2*R) { tail++; max = Math.max(tail - head + 1, max); } else { head++; } } } t = ((double)-2*R + xInit[j] - xInit[k]) / (v[k] - v[j]); if(t >= 0) { System.out.println(t); for(int i = 0; i < len; i++) { temp[i] = xInit[i] + v[i] * t; } Arrays.sort(temp); int head = 0; int tail = 0; while(head < len && tail < len - 1) { if(Math.abs(temp[head] - temp[tail + 1]) <= 2*R) { tail++; max = Math.max(tail - head + 1, max); } else { head++; } } } } } } return max; } }