Single Round Match 452 @ TopCoderの参加記録です。今回のWriterの中の人はあのrng_58さんだったとの事です。
格子のセルを塗る。このとき塗られたセル同士のユークリッド距離が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; } };
'I'、'O'、'?'からなる文字列が与えられる。?にI又はOを入れたとき、I、O、Iの距離が等しいような配置が含まれる文字列が何通りあるか求めよ。
先頭から再帰で探索するもTLE。まったく歯が立ちませんでした。rng_58さんの話によると、IOIStringとならない文字列のパターンを考えると解けるそうです。
n桁の数字の中で、各桁の数字が非減少数列で、かつdivisorで割り切れる数の数を求めよ。
rng_58さんの話によると行列のN乗で解けるとの事なのですが、Twitterを見ているとTLEしている人が多いようです。なんということでしょう。
width=height=2で落ちる人を見つけようと頑張っていたのですが、そもそも自分と同じアルゴリズムの人がいなかったので、どうしようもありませんでした。
x x x
しばらくはrng_58さんはトラウマになりそうです。
Writer解では、IncreasingNumberは
a + 11b + 111c + 1111d + ... (a + b + ... <= 9)
と表せることを利用しています。
コメント有難うございます。今週末は忙しいのですが、時間を見つけてもう一度解法を考えてみたいと思います。