Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2308-72309979
この記事にトラックバックする(FC2ブログユーザー)

UVa 12474 - Draw and Score (この記事を編集する[管理者用])

Source

First Bangladeshi Contest of 2012-2013 Season (2012-07-07)
UVa 12474

問題概要

頂点を1個ずつ付け加えて頂点数Nの2分木を作る.Nは10^15以下.
その際,バランスされている頂点とは,
 その頂点の子供が1つ以上ある
 その頂点の左の部分木と右の部分木に含まれるノードの数が同じ
であること.
頂点を付け加えた際,
 バランスされてなかった頂点が,バランスされたら +1 点 (そのような頂点が複数あったらその数だけ加点)
される.
付け加える順番を最適化したとき,得られる最大点数を求める問題.

解法

Ad-hoc.
最大点数となる付け加える順番の規則を探す.
Nがなんでもこういう順番に付け加えれば良いという感じでもない.
詳しいことは忘れてしまった.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2308-72309979
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。