問題 n頂点の木を自由に作る 次数がiの頂点1つにつきスコアにa[i]が加算される(1 スコアの最大値を求めよ2 0 解法 木だから次数1の頂点が2個は絶対に出来る 残りn-2個の頂点の次数は、各次数が1以上n-1以下 かつ 次数の総和が2n-4であれば任意の組み合わせが…

問題 n頂点の完全無向グラフがあり、そこからアリスはm本の辺を取り、残りの辺はボブに渡した 二人が持っているグラフそれぞれにおける長さ3の閉路(=triangleと呼ぶ)の個数の和を求めよ1 0 解法 各頂点を1個ずつ見ていき、その頂点に繋がっているn-1本の辺か…

問題 n人が順番に座布団を積んでいく i人目は自分の番が回ってきた時に既に積まれた座布団がa[i]枚以下である場合はちょうどb[i]枚の座布団を積む n人の並び順を工夫することによって最大で何人が座布団を積むことができるか1 0 1 解法 「うまく並べればn人…

問題 家が燃えている！ 家には品物がn個あり、i個目の品物は、運び出すのにはt[i]秒かかり、燃え始めてからd[i]秒後には完全に燃え尽きてしまい、価値はp[i]である 品物は1個ずつしか運べず、完全に燃え尽きた瞬間に品物の価値は無くなる (t[i]>=d[i]の品物…