ABC116の振り返り
どうもmmnkです．
昨日行われたABC116に参加したので復習していきたいと思います!
A
直角三角形の面積を求める問題です．
これはで終わりですね．
B
この問題はコラッツ予想というらしいです．
コラッツ予想とは... 偶数なら2で割る．奇数なら3倍して1を足すということを繰り返すと必ずいつかは1→4→2→1→4→2→1→4→2→...のループに入るという予想
コラッツ予想という知識があれば，最後は1,2,4のループになるので最初に1か2か4を見つけたところに3を足したものが答えになります．
僕はこの知識がなかったので集合を考えて，追加する値が集合の中にあったらそこで数列の計算を終了して，集合のサイズ+1(本来は集合にその追加する値が追加されるから)が条件を満たす最小の整数だとしました．
C
目標の花の高さから連続している0以上の部分をグリーディーに選択して，高さを1引き，すべての花の高さが0になるまで繰り返しました．
隣同士の花の高さの差分を求めて，とすれば最小手数で目標の高さにすることが出来るという解法もあります．
こっちのほうがシンプルにかけて，計算量も若干減って，配列も用意しなくていいのでメモリ使用量も減って良いですね!
D
異なる種類のネタに対して美味しさがベストのものを選択し，その中で美味しさに対してソートしたリストと，同じ種類のネタでソートしたリストを考えます．
それぞれのリストから上位個，
個を選択して部分和を求めて，
を足して最大になる値が最大の満足ポイントです．
