2016-10-02から1日間の記事一覧
問題 TopCoder Statistics - Problem Statement 考えた解法 普通にdfsで探索すると計算量がやばい。 特に下図のような構成となっているグラフで、赤い頂点から探索を進めた日にゃあスタート頂点1つにつき計算量がO(M^2)になる。やばい。 あれ待てよ・・・赤…
問題 TopCoder Statistics - Problem Statement Editorial https://apps.topcoder.com/wiki/display/tc/SRM+683 訳 まずは簡単に考えて、石の山が円状に並んでいないものとしよう。ちょうど、類題であるDiv2 Mediumでは石の山は直線状になっており、最後と最…
問題 TopCoder Statistics - Problem Statement 解法 配列を昇順にソートしておいて、サブセットに含める最小値a[L]と最大値a[R]の2つを決め打ちする。 すると、Dの最大値は「a[R] - a[L]」に固定される。Dの最小値も「Dの最大値 / k」に固定される。 あと…