AtCoder Beginner Contest 173 [ D - Chat in a Circle ]をPythonで解く(400点、🟫茶diff)
問題
解法
おそらく、大きい数から追加していくのが正解ではないかと思われる。
その前提で、数列A 8, 7, 6, 5, 4, 3, 2, 1
を円に追加してみる。
円に両隣を参照しながら追加していくと、2番目以降が二分木で追加され、数字が足されていく構造になる。
足される回数はN-1回。
1番大きい数が1回、それ以降が大きい順に2回ずつ。
ということが、わかる。
その構造を素直に実装していく。
実装
参考
いつもながらの公式放送