SRM 653 Div I
SRM 653 Div I
http://community.topcoder.com/stat?c=round_overview&er=5&rd=16317
SRM 653 Div Iに参加。制限時間一杯Easyを考えるが、全く手が出ず。SRM後に幾つかの実装を読み、全く考えもしていなかった問題に還元できることを学んだ。
グラフの問題であると捉え作図を行ったため、メモの代わりとしてブログ記事として記載した。
CountryGroupHard
http://community.topcoder.com/stat?c=problem_statement&pm=13688&rd=16317
- 以下のような数の並びが与えられる
- 数値の周りには同じ数値が、数値分だけ集まる
- 0は数値が隠されていることを示す
- 1以上の数値は既知であることを示し、必ず正しい
- 全体が成立するように、数値を推定したい
- そのとき既知の数値から隠された数値を一意に推定できるかどうかを判断して回答する問題
- 例えばこの例は数値が一意に求まり、以下のようなものであったと推定できる
- 以下も数値が一意に求まる例だ
- 以下は数値が一意に求まらない例
- この数列を成立させる組み合わせは複数ある。書き出してみると5種類あった
- SRM終了後に幾つかの実装を読み、ようやく理解をすることができた
- 自分が理解する上で一番しっくりきたのが、経路の組み合わせを数え上げる問題に還元するものであった
- 先ほどの例で考えてみよう。数値の列として捉えるのではなく、
- 以下のように成立する経路を考え、その経路を数え上げる問題とするような感覚で捉えるのが自分には合っているらしい
- さて、実際には上記のように極度に抽象化したグラフではなく、数値群の間に頂点を配置して考えた
- 初期状態では左端の頂点にのみ経路が設定されていることに注意したい。またその数は1だ
- 一番左の数値に1を設定してみよう。結果、左端の頂点から次の頂点への経路が成立する。つまり、左端の頂点から次の頂点への経路は少なくとも1種類存在すると言える
- そのため、二つ右側への頂点へ左端の頂点に到達する経路の数、1を足し込む
- 一番左の数値に2を設定してみよう。このときは左端の頂点から二つ右側への頂点への経路が成立する。先ほどと同様に、左端の頂点から二つ右側への頂点への経路は1種類存在すると言える
- そのため、二つ右側への頂点へ左端の頂点に到達する経路の数、1を足し込む
- 一番左の数値に3を設定してみよう。3の周辺には3つの3が集まるはずだが、隣の数値は2で、条件が成立しない。そのため、経路も成立せず、この場合は左端の頂点から三つ右側への頂点への経路が存在しないことが分かる
- 左側の頂点からの経路をまとめてみよう。以下のようになる
- 二つ目の頂点から同様に考える。しかし、この頂点から成立する経路がない
- 三つ目の頂点からも考えてみよう。以下のように右側の数値群を3で埋めてやると経路が成立することが分かる
- 三つ目の頂点からの経路をまとめる
- 四つ目の頂点からの経路を考える。四つ目の頂点からの経路は成立するのだが、そもそも左端の頂点から四つ目の頂点に到達する経路がないため、最終的な経路の組み合わせ数に寄与しない
- 五つ目の頂点からの経路も同様に寄与しない
- 結果、左端の頂点から右端の頂点への経路は1種類しかないと言え、問題の答えも一意に推定できるものとすることができる。以下は左端から右端の頂点までの経路をまとめたものだ
- 以下は成立する例
- その経路をまとめたもの
- 以下は成立しない例
- 結果、左端の頂点から右端の頂点へ到達しうる経路は5種類であることが分かる
- 確かに書き下した組み合わせの数も5種類であった
おまけ
class CountryGroupHard {
public:
std::string solve(std::vector<int> a) {
int size = a.size();
long long dp[111] = {0};
dp[0] = 1;
For (int i = 0; i < size; i ++)
for (int j = 1; i + j <= size; j ++) {
bool valid = true;
for (int k = 0; k < j; k ++)
if (a[i + k] && a[i + k] != j)
valid = false;
if (valid)
dp[i + j] = (dp[i + j] + dp[i]) % MOD;
}
return dp[size] == 1 ? "Sufficient" : "Insufficient";
};
};
