最終更新: 2021-12-21T16:21+0900
昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は５完６完を狙いたいところなんだけど、ABCD を 17 分４完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか？
こちらが先に解けた。やり方はすぐにわかる。１か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を１つ決めると木に深さという概念が生まれて、根の深さを０にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。
木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。
83 分間合わないサンプル２を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。
しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。３つくらい勘違いポイントがあった。組み合わせを半分(それとも２倍？)扱いしなければいけないのはどういうケースか(同じ深さの２頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。
余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。
愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点１つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。
E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。