競技プログラミング用 知識集積所
ARC202A - Merge and Increment
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
考え方
問題では全部挿入して数列を作ってからマージするようになっているが、挿入しながらマージしても特に問題ない。
そう考えると、以下を可能なところからどんどん実行する貪欲法（未作成）でよい。
そう考えると、以下を可能なところからどんどん実行する貪欲法（未作成）でよい。
- 両隣（端の場合は存在する側）がともに自分より大きい場合は、同じ数を隣に入れてマージする。
- 片隣が自分と同じで片隣が自分より大きい（または端である）場合、同じである方とマージする。
「同じ数を隣に入れて合体させる」を繰り返す数は計算でパッと出せるので、そこだけ高速化すれば十分。
解答例
注意点
両隣ともに自分と同じ場合に注意
{1,1,1,1}のときに、うっかり真ん中の2つをマージするとおかしなことになる。
これをきちんと回避できるコードにすること。
これをきちんと回避できるコードにすること。
