脳log[20220620]

2022年06月20日 (月) [AtCoder] 精進。昨日あった ARC142-C「Tree Queries」(水 diff)。昨日は 1 を含む辺からの距離一覧を取得したらどうだろうかとか、1 と 2 をどちらも含まない辺からの距離一覧を取得してみたらどうだろうかとか考えていた。どちらの場合でもうまくいかない木の形がある。そのうちに提出できないまま時間が終了していた。今日になってお風呂に入るや思いついたのは、(仮に 3 を根として) 1 と 2 のうち深い方の親を押さえてしまえばどうだろうかということ。親を特定することはできる。それで 1 と 2 の距離を求めることができる。クエリ回数は 2N-3 回で足りる。このツイートのケースも大丈夫。■提出 #32630348 (AC / 447 Byte / 66 ms)。これを思いつきでなく見つけられる脳みその構造が理解できない。■Ruby によるすべての提出をちらちら見てるけど、1 からの距離一覧と 2 からの距離一覧を取得する提出が複数(というかほとんど？全部？)目についた。えっどういう解き方？■解説を読んだら書いてあった。コンテストが終了してから今日までのあいだに 1 からの距離と 2 からの距離を見比べる方法を自分でも考えてはいた。1 と 2 のパス上にある頂点なら和が答えだし、パスから外れている頂点なら対称差(XOR)にあたる部分が求められたら……とか。解説にいわく「Di​ の最小値は多くの場合 d1,2​ に一致します。」 和の「最小値」が「多くの場合」答えに一致するとか、そんなざっくりした掴まえ方は出て来んで。結果として自分と同じ考え方の提出が全然見つからないのはとても嬉しい(そういうタイプの人間)。