今日は組み合わせを求めるプログラムを作成し、組み込ませていました。
組み合わせを求めるプログラムとは、1,2,3が与えられた時
1
2
3
12
13
23
123を出力するようなプログラムです。
この
URLを参考にしました。
jubeat plusも少しだけ。gymnopedieでフルコンしました。
その後は今年最後のTopCoder SRM528に参加。
easy問題はoのコストとxのコストがあって、?の部分をそれで埋めて回文を完成させる。
その時の最小コストを求める。
全探査はさすがにやってはいけません。最大2^50オーダとなってしまうので。
方針としては左側からと右側からで文字を見ていって、場合分けをする。
?と?の場合はコストの小さい方、片方がoかxならそれに合わせるといった具合。
ちなみにこれ、奇数の場合分けは必要なかったらしく、自分のプログラムは冗長です。
public class MinCostPalindrome {
public int getMinimum(String s, int oCost, int xCost) {
int st = 0;
int cost = 0;
int en = s.length()-1;
if(s.length() % 2 == 0){
while(st < en){
if(hantei(s.charAt(st),s.charAt(en)) == 0){
cost += Math.min(oCost, xCost)*2;
}else if(hantei(s.charAt(st),s.charAt(en)) == 1){
cost += oCost;
}else if(hantei(s.charAt(st),s.charAt(en)) == 2){
cost += xCost;
}else if(hantei(s.charAt(st),s.charAt(en)) == 4){
return -1;
}
st++;
en--;
}
return cost;
}else{
while(st < en){
if(hantei(s.charAt(st),s.charAt(en)) == 0){
cost += Math.min(oCost, xCost)*2;
}else if(hantei(s.charAt(st),s.charAt(en)) == 1){
cost += oCost;
}else if(hantei(s.charAt(st),s.charAt(en)) == 2){
cost += xCost;
}else if(hantei(s.charAt(st),s.charAt(en)) == 4){
return -1;
}
st++;
en--;
}
if(s.charAt(st) == '?'){
cost += Math.min(oCost, xCost);
}
return cost;
}
}
public int hantei(char a,char b){
if(a == '?' && b =='?'){
return 0;
}else if((a == '?' && b =='o') || a == 'o' && b =='?'){
return 1;
}else if((a == '?' && b =='x') || a == 'x' && b =='?'){
return 2;
}else if((a == 'o' && b =='o') || a == 'x' && b =='x'){
return 3;
}else{
return 4;
}
}
}
medium うなぎカットです。
うなぎの長さが整数の配列で与えられていて、カットできる回数が決められています。
そのカット回数を使って何匹長さ10のうなぎが作れるでしょうかという問題。
重要になってくるのは10の倍数のうなぎです。
この部分だけ別にソートしてあげる必要があります。
なぜなら20のうなぎは1回半分に切るだけで2匹分になるからです。
import java.util.Arrays;
public class Cut {
public int getMaximum(int[] eelLengths, int maxCuts) {
int[] neweels = new int[eelLengths.length];
int count = 0;
for(int i = 0 ; i < eelLengths.length ; i++){
if(eelLengths[i] % 10 == 0){
neweels[count] = eelLengths[i];
eelLengths[i] = -1;
count++;
}
}
int[] neweels2 = new int[count+1];
for(int i = 0 ; i < count ; i++){
neweels2[i] = neweels[i];
}
int unagicount = 0;
Arrays.sort(neweels2);
for(int i = 0 ; i < neweels2.length ; i++){
if(neweels2[i] == 0){
continue;
}else if(neweels2[i] == 10){
unagicount++;
}else{
if(maxCuts == 0){
return unagicount;
}else if(neweels2[i]/10-1 > maxCuts){
unagicount += maxCuts;
return unagicount;
}else{
maxCuts -= (neweels2[i]/10-1);
unagicount += neweels2[i]/10;
}
}
}
//System.out.println(unagicount+","+maxCuts);
for(int i = 0 ; i < eelLengths.length ; i++){
if(maxCuts == 0){
return unagicount;
}else if(eelLengths[i] == -1){//cooked
continue;
}else if(eelLengths[i]/10 > maxCuts){
unagicount += maxCuts;
return unagicount;
}else{
maxCuts -= (eelLengths[i]/10);
unagicount += eelLengths[i]/10;
}
}
return unagicount;
}
}
2完できたので、レーティングも100近く上昇しました。
チャレンジは二人落とせましたが、テストケースを投げれば後5人は落とせたようです。
来年もよろしくおねがいします。
