読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 483 DIV 2

DIV2においては500点問題が無茶苦茶落ちる回で、うっかりDIV2の1位の人と同じ部屋になったりと個人的にも踏んだり蹴ったりだったが、DIV1においてはtargetのPetrが全問System Test Failedしたり酷い事になっていて話題だったらしい。

自分のレートは一応ちょっと上がったけども、その前に0点2回連続で出してるのがやっぱりまだひびいてる。

250 Digit Holes

数字の"穴"の数を数える問題。穴、というのは数字を手で書いた場合に、文字の上において閉じている部分の事である。

#include <cstdio>
using namespace std;
class DigitHoles {
public:
	int numHoles(int number) {
		int dst = 0;
		char c[5];
		sprintf(c, "%d", number);
		for(int i = 0, l = strlen(c); i < l; i++){
			switch(c[i]){
			case '0':
			case '4':
			case '6':
			case '9':
				dst += 1;
				break;
			case '8':
				dst += 2;
				break;
			}
		}
		return dst;
	}
};

228.65点サブミット。まあそこそこ素早かったほうだと思うけども、もう一段早く題意の「穴」とは何か、及びswitchを使うか否か、で一瞬の迷いが生じなかったら早くなったかなあという感じ。

500 Movie Seating(Challenge Succeeded, 修正版)

hallに示されているように席が予約されている中で、numFriends人の人がいかに縦ないしは横に一列で並んで座る事ができるか、その場合の数を求めよという問題。

#include <string>
#include <vector>
using namespace std;

class MovieSeating {
public:
	long long nPr(long long n, long long r){
		long long dst = n;
		for(long long i = 1; i < r; i++){
			n--;
			dst *= n;
		}
		return dst;
	}
	long long getSeatings(int numFriends, vector <string> hall) {
		long long dst = 0;
		/* col */
		if(numFriends != 1){
			for(int i = 0; i  < hall.size(); i++){
				int available = 0; 
				for(int j = 0; j < hall[i].size(); j++)
					available += hall[i][j] == '.' ? 1 : 0;
				if(numFriends <= available){
					dst += nPr(available, numFriends);
				}
			}
		}
		/* row */
		for(int i = 0; i < hall[0].size(); i++){
			int available = 0;
			for(int j = 0; j < hall.size(); j++)
				available += hall[j][i] == '.' ? 1 : 0;
			if(numFriends <= available){
				dst += nPr(available, numFriends);
			}
		}
		return dst;
	}
};

Challengeされた。上のコードはその修正版。
落ちた理由としては、numFriendsが1の場合について考えていなかったから。
そうするとどうなるかというと、上のコードでは縦と横を完全に分離して考えているので、numFriendsが1の場合に同じ物を2回数える事になってしまう。
よって上のコードにおいてはnumFriendsが1の場合には下のforループしか回らないように修正を加えた。

1000

問題文もろくに読んでいないというか読めなかったしなんとなく意味が分かっても解けそうになかった。自分の英語力の無さとか諸々を実感。

感想

事ある毎に感じてきた事ではあるが、全体として、自分の圧倒的な経験不足を新ためて実感する事になった。
少しはTCの過去問を解くとかもしたほうがいいと思った。