AGC018

この1週間殆どプログラミングしてませんでした

(テスト早く滅んでくれ)。

そのせいか否か、今回のAGCは447位(700点)でした。

 

A問題:

え、無限に色んな場所作れるじゃん、え、どうすんの!?!?

Twitterのおかげで、最大公約数分かればいいのだと言われてやっと納得しました)

 

B問題:

一番集まる競技αにN人集まってるとする。 このとき、αを開催している限りは必ず答えがN以上になってしまう。 だから、N未満の答えを探そうとするとαを開催してはいけない。 後はこれを帰納的にこれをやって行けば良い。

こんな感じです

 

C問題:

何か見たことありますが難しです。

 

D問題:

最短辺の両端それぞれを初手として、木の最遠点に飛んでいくことをN-1回やってみました。

参考はAOJのプロコン本です。

サンプル2は正しかったのですが、サンプル1で1小さくでました。

小さく出たので、やはりより良い初手があるのだろうなぁと思いながら終わりました。

(なお、提出して見たらそもそもTLEでした)

 

レート変化がまだ出ないので、ここまでで終わります。

追記:1543→1558