AtCoder ABC152 F - Tree and Constraints
https://atcoder.jp/contests/abc152/tasks/abc152_f
解けなくて悔しい。まだ解説に目を通していない。
解けるまで考えるか、解説を見てしまうか悩む。
おそらく言い換えることで簡単な問題になると思うけど、言い換え方がわからない。
とりあえず、問題を解く際に何を考えたかを書き残す。
- 制約が小さい
- けど辺の色を全探索は250で間に合わない
M <= 20なので、条件のほうを全探索すればいいのではないか- しかしその方法がわからない
- そもそも木の問題をほとんど解いたことがないので、思いついた解法が計算量的に間に合うかや、実装できるかなどがすぐに判断つかない
- 問題を解くことは一旦諦めて、思いついたものを実装しよう
- 「ある色の塗り方が制約を満たすかどうか」をまずは実装する
- 「ある辺を黒く塗ったときにどの制約を満たすか」を判定したい
- パスの2つの端点からDFSをする。そして、それぞれの頂点までの距離を求める
- 次に2つの距離を足した木を作る
- このとき、パスの長さと同じ値を持つ頂点が、パス上の頂点である。そして、パス上の頂点同士を結ぶ辺がパス上の辺である
- これで、辺から制約を取得するためのデータ構造を構築できる
- このときにどのデータ構造を選ぶか。配列を選べば辺から辺のIDを取得できるようにしないといけない。mapを選べばキーが
pair<int, int>になって「pair同士の比較ってきちんと行われるのかな」という気持ちになる - あとで上位者のコードを見る
- 全探索するのであれば、辺にIDを持たせたほうが実装しやすい。なぜなら、250通りを試すときにbitを使うことになるが、このとき、立っているビットの場所から制約を取得したくなるから
- 実装して提出すると案の定TLEだった。さてここからどうしよう
ここまでが問題を解くときの流れ。
途中で解くことを諦めている。木に関する感覚を掴めば、本来の問題に集中できると思うので、今はとりあえず思いついたことを実装していく。
