yukicoder No.944 煎っぞ! 解説

No.944 煎っぞ! - yukicoder

問題概要

をいくつかに区切ってすべての区間和を等しくするとき、区切った区間数の最大値を求めよ。

解法

Writer解とは違うアプローチをしたので軽く解説する。
まず、最も左の区間を決め打ちすると、その区間は全部で 個存在する。
最初の区間に選んだ区間の長さを とすると、区間和を等しくできるかどうかを左から順に試すのにかかる回数は であり、累積和と二分探索を用いれば一回あたり でできるから、調和級数になって全体で で求められる。

提出コード

感想

一瞬でこれを思いついたので簡単だった。