c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

結局注目する点は、隣り合う2数を足したときに、繰り上がって桁数が変化しない時は、全体の数の和が9減るということのみ。桁数が減る時は繰り上がりがないため、全体の和は変化しない。 なので求める回数は、全体の和を S, 桁数を T とすると、T-1 + (S-1)//…

stack, dict, set 全部使った。盛りだくさん。 まず、降順ソートしてｋ個選んだ時に、L 種類の寿司が含まれているとき、当然それはL 種類の寿司を選ぶ美味しさの中での最大値となる。同様にして、k > L なら種類が被っている寿司を食べているので、k =L にな…