ARC028/

README

ARC028 過去問感想

Last Change: 2020-04-27 01:27:12.

A問題（@2020-04-27）

無限whileループでシミュレーションやった。

O(1) でやる方法もあるとは思う。

B問題（@2020-03-09）

BITSetの練習問題に良い。

。。と思ったら、解説スライドによるとpriority queueでもできるとのこと。 K番目までをキューに突っ込み、現在キューに入っているものの一番うしろのものを答える、というもの。

priority queueを使ったやり方もやっておくべきな気がする。

C問題（@2020-04-19）

旧青Diffだが、だいぶシンプルだったように思える。

まずは根付き木として考えて、子方向の部分木のサイズを計算する（木DPっぽくやる、簡単）。

そのあと、根から再び再帰して、「自身の子部分木のサイズ、自身を含む部分木を全体から引いたもの」を比較して、 それの最大をすべてのノードについて計算してやればOK。

解説スライドより

詳細については省きますが、 「部分木のサイズの最大値を求める問題は、木の分割統治を行うときに使ったりします」

らしい。覚えておくといつかいいことがあるかも。