問題概要
長さが n の細長いケーキがある。このケーキを予めいくつかの切片に切り分けておき、訪ねてきた友達に振る舞いたい。ケーキの分配は次のように行う
- ケーキの端から、連続する複数の切片を一人目の友達に振る舞う。以降全ての友人にも同じように処理する。
訪ねてくる友達の正確な人数は分からないが、n 未満かつ n を割り切る人数であることが分かっている。全ての友達に同じ量のケーキを分配できるようにしておきたいとき、最小でいくつの切片に分割しておけばよいか、求めよ。
解法
ある整数 x があって、x が n を割り切るとき、x は訪ねてくる友達の人数として有り得る数です。x 人の友達が訪ねてくるとき、一人あたりに分配されるケーキの量 y は n / x となり、分配の手順より、ky ( k = 0, 1, 2, ..., x - 1 ) の位置で分割されなければならないので、これらの位置には切れ込みが必要です。必要の無い位置は切らない方がよいので、n 未満且つ n を割り切る全ての x について上記の位置で分割するのが、最適な分配をするための必要十分条件です。n の約数の数はそんなに大きくならない*1ので、n の各約数について切れ込みを入れる位置を愚直に列挙して印を付けるような処理をしても間に合います。
コード
using VI = vector<int>; #define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #define ALL( c ) (c).begin(), (c).end() class MyLongCake { public: int cut( int n ) { VI cuts( n + 1, false ); REP( i, 1, n ) { if ( !( n % i ) ) { const int x = n / i; for ( int y = 1; x * y <= n; y++ ) { cuts[ x * y ] |= true; } } } return count( ALL( cuts ), true ); } };
