読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 585 Div2 MediumTrafficCongestionDivTwo

SRM 探索
問題

完全2分木がある。すべての頂点を一度だけ通るような最小パス被覆のサイズを求めよ。木の高さは60以下

やりかた

f:id:Area1:20130720025707p:plain
という感じで3つのノードでひとつのパスというふうにした時パス数は最小となる。
なのでceil(頂点数/3)。

以下ソース。

class TrafficCongestionDivTwo {
public:
  ll powll(int a, int n){
    ll ret = 1;
    for(int i = 0; i < n; i++) ret *= a;
    return ret;
  }
  long long theMinCars(int treeHeight) {
    return (ll)((powll(2, treeHeight + 1) + 1) / 3);
  }
};
しょげないでよBaby 眠れば治る