2022-06-21 ARC142 の C を解いた
ARC142 : AtCoder Regular Contest 142 の C を解いた。
- C - Tree Queries
https://atcoder.jp/contests/arc142/tasks/arc142_c
- 提出: https://atcoder.jp/contests/arc142/submissions/32641571
- 回数的に d_1x と d_x2 を主に使うと推測した
- 2 の位置ごとに場合分けすると 1 の子である場合・ x_1 の子孫である場合・ x_1 以外の子孫である場合になった
- わりと惜しいところまで行けたと思うのだけど分岐が多く微妙な WA を消すのが面倒そうなので断念
- 解説 AC
- 1 から x と x から 2 を主に使うところまでは正解
- d_1x + d_x2 の最小値がほとんどの場合に答えになる
- d_1x + d_x2 が 3 のとき「 1 の子である場合」の分岐がある
- d_1x + d_x2 が 3 のものが 2 個以外のときは 1 (x の子孫であることがない)
- d_1x + d_x2 が 3 のものが 2 個のときはその 2 個の距離が 1 なら 3 そうでないときは 1
- ここまで整理できる気がしない
- インタラクティブな問題はサンプルもなくてイライラする
JUnit5 ではテスト名は @DisplayName を使うと良い。以前はメソッド名を日本語で……といった方法が広められていたものの IDE の既定の設定で警告が出たり空白が使えなかったりとつらいので。
今日のコミット。