コンテストページ
解法
✔A - Collecting Coins
最低いくつのコインを配る必要があるかを計算して、足りなければダメです。余っている場合も、それが 3 の倍数でなければダメです。
✔B - Collecting Packages
ソートをして、y 座標が等号付きで昇順になっていることが OK な条件です。 OK ならば、シュミレーションをすればよいです。
✔C - Product of Three Numbers
ちょっとむずかしいです。 素因数が 1 つしかない場合はそれで 6 回割れる必要があります。
そうでないときには、OK ならば相異なる 2 つの素因数と、それ以外に分けることが出来るので、それを試せばよいです。というのも、この分け方でダメならば、p * q2 型しかありえず、これはそもそもどう分けてもダメです。
✔D - MEX maximizing
入って行きたものに操作をして値を決めてあげましょう。重複しない中で最も小さいものにすればよいです。
今何が入っているのかをチェックリストで管理です。さらにあまりごとにいくつあるのかを管理して、また MEX も別で管理しましょう。気になるのはチェックリストのサイズと MEX の更新です。まず前者についてですが、クエリの個数以上のところはいりません。来たらなかったことにしましょう。次に後者ですが、MEX が MEX ではいられなくなった時、MEX さんは自分の居場所を求めて 1 ずつ正方向に移動していきます。これは償却定数時間です。
✔E - Obtain a Permutation
列ごとに独立に考えましょう。i 回シフトして m[i] 個の正解が踏めるとすると、このときのコストは回転、書き換え合わせて i + h - m[i] です。これらの最小を求めて足し合わせましょう。なお、m[i] は要素をすべて見て、そもそもこの列にいないものならばスルーをし、いるものなら何回シフトをすればもとのお家にたどり着けるのかを引き算などで計算です。
✖F - Three Paths on a Tree
コンテスト中に考えていたことは、正解なのですが、重実装です。 終わりに差し掛かるころに、簡単なやり方を思いつきました。
重実装パターン
次数 3 以上の頂点がない場合はパスグラフですから、特別処理です。 そうでない場合は、答えとなる 3 点のスパンをとると必ず足が 3 本ともある T 字グラフになります。 T 字グラフの中心を全探索です。
中心を決めると、そこから生えている部分木の高さベスト 3 の和が答えですから、部分木の高さの配列を作りましょう。そのためには、根を決めて DP をしてその頂点の部分木の高さを求めておく必要があります。さらに親側の高さも調べる必要があり、それは全方位木 DP で求めることが出来ます。
これによって最適な中心を選んだら、今度は探索をして各部分木の中で中心から最も遠い頂点を選び出せばよいです。
正気を取り戻した人の解き方
3 点のうち 2 点は必ず直径の両端点ですから、それを求めます。直径が複数あるのはウニグラフのときだけで、これも気にせず適当なものを選んでしまえばよいです。
3 点目を探しましょう。各頂点からこのパスに含まれる頂点までの距離を、パスに含まれる頂点からの DFS で計算をして、最も遠かった頂点の優勝です。これぞ DFS をして、距離の遠いほうが勝ちです。
結果
534 位です。異彩を放つ薄橙コーダーです。 これが Rated でしたら、Div. 2 降格は確実でした。難しいですね。
タイムラインのご様子
C
Codeforces 615 div3
— tarattata (@tarattata1) January 22, 2020
B: (x,y)のペアでソート
C: nを2,3,4,..で順に割れるか試す
D: 面白かった。xで割った余りの個数をカウントしながらsetを使う
E: 各列の各項について何個シフトすると目標に到達するかをチェックして計算
F: 直径を求めて、あと1つ足すものは全探索。計算はLCAを使った
そうでした。場合分けいらないじゃないですかー！！
distinctってわざわざ太字で書いてくれてるんだよな...
— てんぷら (@tempura_cpp) January 22, 2020
こちらは誤読被害者の会です。私は提出直前に気づきましたから、これはセーフと言ってもよいでしょう。（本当ですか？）
E
Eの制約が罠すぎると思ったら無限人引っかかってて笑った
— アルメリア (@armeria_betrue) January 22, 2020
これです。h * w よりも大きな要素を入れますか！？
F
直径なんとなく正しそうな気がしたけど、証明が思い浮かばなかったのでせつせこ全方位木DPを書き始めてしまった
— アルメリア (@armeria_betrue) January 22, 2020
すべてを貼ってしまうと煩雑になってしまうのですが、全方位木 DP だいすきクラブ活動をしていたのは私だけではなかったようです。アルメリアさん以外にもかなり見かけました。ちょっと安心（？）（はい！？）（実際気づいたときにはけっこう落ち込みました……）
{距離、頂点}をpairで持つと、pairのmaxをすることで復元が無い場合と同様に実装できます
— heno (@heno_code) January 22, 2020
知見です。
全方位解はかなりそのままで、3点の合流点を決め打つとその点を根として1番遠い3点(ただしどの2つも同じ部分木にない)を選べばいいので、直径を求める全方位を書いたことがあればそれと全く同様にできる
— てんぷら (@tempura_cpp) January 22, 2020
直径自体、全方位で求めることができるのですね。たしかにです。（書きたいかと言われるとノーなのですが……）
ながたかなさんのブログを見て、やっぱFはそれを考えちゃうよねって思った
— 31536000 (@CuriousFairy315) January 22, 2020
直径は気付けなかったなぁ
当ブログへの言及をペタリすることによって、循環参照を引き起こす一般的なテクです。一緒にデッドロックしましょうね。
裏事情
いつもより少々遅いくらいでしたら言語のせいなのですが、さすがに言い訳の出来ない結果です。悲しいですね。
