TopCoder SRM582

今日は県内某所での聴講へ。
お昼はとんこつラーメンを食べる。

TopCoder SRM582_f0019846_22194625.jpg


夜は、この路線にも新しい車両ができていたんだなーと、試運転の表示を見て思った。

TopCoder SRM582_f0019846_22205030.jpg

I'm so happy 88.3% フルコン

TopCoder SRM582_f0019846_22212246.jpg

Broken 86.1%

帰宅後はTopCoder SRM582に参戦。

Easyは、数値が与えられているから、桁と桁を1箇所だけスワップして、
最小となるような数値を出力せよという問題。
単純に一番左の桁と、一番右にある一番小さい桁を交換する。
しかし注意すべきは、一番左の桁の場合、0の交換はダメだということ。
そこに気をつけて書きましょう。そして見つかるまでは全部やります。
11111とかであれば、結局見つからないので、元々の数値を出力することも。


public class SwappingDigits {

public String minNumber(String num) {
String min = num;
for(int i = 0 ; i < num.length() ; i++){
char a = num.charAt(i);
for(int j = 0 ; j < num.length(); j++){
char b = num.charAt(j);
String newsb = "";
for(int k = 0 ; k < num.length() ; k++){
if(k == i){
newsb += b;
}else if(k == j){
newsb += a;
}else{
newsb += num.charAt(k);
}
}
if(newsb.charAt(0) != '0'){
if(min.compareTo(newsb) > 0){
min = newsb;
}
}
}
}
return min;
}

}


Mediumは、IDとregion codeの配列が与えられるので、
そのIDがvalidかどうか判定せよという問題。

先頭6ケタをregion codesとマッチングさせ、
誕生日が有効であるかどうか判定(うるう年含めた奴)し、
最後の3ケタで男女どちらかを出力するだけ。
やるだけ問題でmediumにしてはつまらないものだった。


public class IDNumberVerification {

public String verify(String id, String[] regionCodes) {
if(id.length() != 18)return "Invalid";//iranaitoomoukedo
String region = id.substring(0,6);
int birthyear = Integer.parseInt(id.substring(6,10));
int birthmonth = Integer.parseInt(id.substring(10,12));
int birthday = Integer.parseInt(id.substring(12,14));
String code = id.substring(14,17);
String checksum = id.substring(17,18);

boolean checkRegion = false;

for(int i = 0 ; i < regionCodes.length ; i++){
if(regionCodes[i].equals(region)){
checkRegion = true;
break;
}
}
if(!checkRegion)return "Invalid";

if(!isvalid(birthyear,birthmonth,birthday,isleapyear(birthyear)))return "Invalid";

if(code.equals("000"))return "Invalid";

long csumnum = 0;
for(int i = 0 ; i < id.length()-1; i++){
csumnum += Character.digit(id.charAt(i),10)*Math.pow(2, 17-i);
}

if(checksum.equals("X")){
csumnum += 10;
}else{
csumnum += Integer.parseInt(checksum);
}

csumnum %= 11;

if(csumnum % 11 == 1){
if(ismale(code))return "Male";
return "Female";
}
return "Invalid";
}

public boolean isleapyear(int year){
if(year % 400 == 0){
return true;
}else if(year % 4 == 0){
if(year % 100 == 0){
return false;
}else{
return true;
}
}
return false;
}

public boolean isvalid(int year,int month,int day,boolean leapyear){
if(year < 1900 || 2012 <= year)return false;
if(month == 0 || 13 <= month)return false;
if(day == 0 || 32 <= day)return false;

int[] leapnum = {31,29,31,30,31,30,31,31,30,31,30,31};
int[] normalnum = {31,28,31,30,31,30,31,31,30,31,30,31};

if(leapyear){
if(leapnum[month-1] < day)return false;
return true;
}else{
if(normalnum[month-1] < day)return false;
return true;
}
}

public boolean ismale(String digit){
if(Integer.parseInt(digit.substring(digit.length()-1,digit.length())) % 2 == 1)return true;
return false;
}

}


Hardは最短経路が最長となるような値を出す問題で、
それほど難しい問題でもなかった。ダイクストラで十分可能なように思えるので、時間があったら。

  by ddrer-yossi | 2013-06-18 23:15 | TopCoder

<< 仕事とかクリスタルディフェンダ... 仕事後ゲーセン。リフレクLv9... >>

SEM SKIN - DESIGN by SEM EXE