435.1

250

親へのポインタのリストから木構造が与えられるので、あるノードを除去したときに除去されずに残る元のリーフの数を答えよ、という問題。

再帰的に親が削除されていないかと、リーフかどうかの判定をするだけ。

500

ある文字列から任意個の文字を取り除いてできる空ではない文字列を、3文字ずつに区切る。各3文字から別の文字列への変換のパターンが与えられるので、変換後でユニークなものの数はいくつあるか答えよ、という問題。

既に変換済みの文字数を覚えておけば、そこ以降を変換して生成できるパターン数は1度計算するだけで決定できる。ある位置から特定の変換後のパターンが作成可能かどうかは、それを生成する3文字のパターンが以降に存在するかどうかであり、そのうち最初に見つかるものを作っていくのが最善である。実装すればおしまい。

1000

N人の集合を木構造になるように分割する。ある人が別の人を子要素にできるかどうかが与えられるが、自分を子要素にすることができる人を子要素にすることはできない。また、お互いに子要素にできる人を同時に子要素にすることはできない。なお、子要素にできるかどうかの関係は推移的である。このとき分割できる最小グループ数を答えよ、という問題。

親子関係が真に可能なものを探索していけば良さそう？同時に採用できない子供のところで分岐が必要。適当に組むと終わらない。