Topcoder SRM 517(Div.2) 参戦記

Intermissionで自分のミスに気づき、それを応用したため多く撃墜できました。

Easy: Javaは得意ではないので、時間がかかってしまいました。C++のstringとvectorをさっさと修得すればこんな事言わなくて済むので、修得したいところです。163.5点でした。

Medium: 400.26の時に提出したのですが、前述のとおり、ミスを発見してしまいました。 そのミスというのは、pを素数、kを2より大きい自然数とするとき、N=p^kかつtarget=p^2 であるようなケースを考慮に入れていなかったことです。システムテストを通るはずはありませんが、このケースを片端から試したので、撃墜ラウンド+3/-3でした。全部で75点！

Hard:Greedyと思ったんですが、違うようです。解けませんでした。

スコアは218.5で、順位(Div.2)は241/1462、Rateは823->900でした。ようやく緑に戻りました。はぁ。

[Easy (Java)]

public class MonochromaticBoard{
public static int theMin(String[] board){
int[][] state=new int[board.length][board[0].length()];
for(int i=0;i<board.length;i++){
for(int j=0;j<board[i].length();j++){
state[i][j]=board[i].charAt(j)=='B'?1:0;
}
}
int rowb=0,colb=0;
for(int i=0;i<board.length;i++){
int tmp=0;
for(int j=0;j<board[0].length();j++){
tmp+=state[i][j];
}
if(tmp==board[0].length()) rowb++;
}
for(int i=0;i<board[0].length();i++){
int tmp=0;
for(int j=0;j<board.length;j++){
tmp+=state[j][i];
}
if(tmp==board.length) colb++;
}
if(rowb==0 && colb==0) return 0;
if(rowb==board.length && colb==board[0].length()) return Math.min(rowb,colb);
return rowb+colb;
}
}


[Normal (C++　間違ったソースです)]

#include<iostream>

using namespace std;

class CompositeSmash{
public:
string thePossible(int N, int target){
if(target==N) return "Yes";
if(N%target!=0) return "No";
if(prime(target)==1) return "Yes";
int count=0;
for(int i=2;i*i<N;i++) if(N%i==0) count++;
if(count==1) return "Yes";
if(count==0 && target*target==N) return "Yes";
return "No";
}
int prime(int p){
int i;
if(p%2==0) return 0;
for(i=3;i*i<=p;i++) if(p%i==0) return 0;
return 1;
}
};


[Hard (C++　間違ったソースです)]

#include<iostream>
#include<vector>

using namespace std;

class CuttingGrass{
public:
int theMin(vector <int> init, vector <int> grow, int H){
int allgrow;
allgrow=sum(grow);
int count=0;
int nowsum;
nowsum=sum(init);
while(nowsum>H){
count++;
for(int i=0,n=init.size();i<n;i++) init[i]+=grow[i];
int num=maxsuf(init,grow);
nowsum+=allgrow-init[num];
if(allgrow-init[num]>0) return -1;
init[num]=0;
}
return count;

}
int sum(vector <int> vec){
int ret=0;
for(int i=0,n=vec.size();i<n;i++) ret+=vec[i];
return ret;
}
int maxsuf(vector <int> vec,vector <int> growth){
int ret=0;
for(int i=0,n=vec.size();i<n;i++){
if(vec[ret]<vec[i]) ret=i;
if(vec[ret]==vec[i] && growth[ret]<growth[i]) ret=i;
}
return ret;
}
};