nodchipのTopCoder日記

■ Single Round Match 452 @ TopCoder 23:58

Single Round Match 452 @ TopCoderの参加記録です。今回のWriterの中の人はあのrng_58さんだったとの事です。

Easy 250 NotTwo

格子のセルを塗る。このとき塗られたセル同士のユークリッド距離が2にならないようにする。塗ることが出来るセルの数の最大値を求めよ。

なぜか斜めに塗ればOKだと思い込み、しかも終了数分前にバグを見つけ、再提出するもSystem Testで落とされるという散々な一問でした。以下のソースは修正後のソースです。

class NotTwo {
public:
	int maxStones(int w, int h) {
		int answer = 0;
		for (int x = 0; x < w; ++x) {
			for (int y = 0; y < h; ++y) {
				if (x % 4 < 2 && y % 4 < 2 || x % 4 >= 2 && y % 4 >= 2) {
					++answer;
				}
			}
		}
		return answer;
	}
};

Middle 500 IOIString

'I'、'O'、'?'からなる文字列が与えられる。?にI又はOを入れたとき、I、O、Iの距離が等しいような配置が含まれる文字列が何通りあるか求めよ。

先頭から再帰で探索するもTLE。まったく歯が立ちませんでした。rng_58さんの話によると、IOIStringとならない文字列のパターンを考えると解けるそうです。

Hard 1000 IncreasingNumber

n桁の数字の中で、各桁の数字が非減少数列で、かつdivisorで割り切れる数の数を求めよ。

rng_58さんの話によると行列のN乗で解けるとの事なのですが、Twitterを見ているとTLEしている人が多いようです。なんということでしょう。

撃墜フェーズ

width=height=2で落ちる人を見つけようと頑張っていたのですが、そもそも自分と同じアルゴリズムの人がいなかったので、どうしようもありませんでした。

System Test

x x x

総評

しばらくはrng_58さんはトラウマになりそうです。

ツイートする