ARC022

README

ARC022 過去問感想

Last Change: 2020-04-11 12:34:00.

A問題（@2020-02-07）

やり方は色々あると思うけど、なんかいい方法が思い浮かばなくて、かなり汚い実装をしてしまった。 気持ちとしては、もっと素早い、安心して書ける方法が良い。

最初の提出ではバグらせてしまっていた。やはりもっと簡潔な実装を目指したい。

解説スライドで紹介されていた方法

• 3文字全通り試す: O(n^3)
• c を決めてその左右に i, t があるか判定: O(n^2)
• 最初の i と最後の t の間に c があるかどうか判定: O(n)

2番目などは「真ん中固定」という典型になるかと思うが、正直今回は実装が楽にはならないと思う。

1番目の全探索が一番簡単でバグらせにくそう。 制約の小ささにちゃんと目をつけたい。

C問題（@2020-04-11）

木の直径を求めるだけなので手持ちのライブラリを貼った。

が、解説スライドでは別の木DPによる直径の求め方も紹介されている。 こちらのほうが汎用的なので、「書けるようになっておいたほうが良い」とのこと。

ポイントとしては、LCAを利用して子孫間で最も遠いものを葉からボトムアップに考えるもの、とのこと。

解説へのリンク

解説スライドだけだと簡潔すぎて書けないかも。。 木DPに慣れる意味でもどこかの解説ページを読むのもありかもしれない。

探したらけんちょん氏の解説がすぐ見つかった。