最終更新: 2021-11-04T10:11+0900
精進ですよ。おとといあった ABC の F 問題。
コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの２のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。
木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので１本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。
たとえば直径が偶数の時、直径の中心には頂点が１つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に２つあるなら、２つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、２つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は１つ。
たとえば直径が奇数の時。直径の中心には１本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が２つあるなら、２つの辺の中点が本来の……(略)。だから中心は１つ。
色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ２つの頂点を考える)。同じ頂点の先にぶら下がっている２点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ？という話になる。そんなものはない。
ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。
配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が１度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。
８問目の黄 diff AC。これより上は橙が１問だけだから、かなりのレア度なんだ。
ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。
さっき書いた。
木の直径については知っている。(中略)。証明は知らない。
木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の１点を始点に選んで最も遠い頂点を求める１回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。２回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。２回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。
さっき書いた。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。
エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい！(嘘です。調子乗りました)