torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 655, Division 2, Level 2 : FoldingPaper2

問題概要

 大きさが H \times W の長方形の紙がある.この紙を辺に平行かつ,操作後の紙の辺の長さが共に整数となるような線で折りたたむ操作ができる.
 面積が A となるように折りたたむとき,少なくとも何回折りたたむ必要があるか? 不可能な場合は -1 で示せ.
 H, W \leq 10^9
 A \leq 10^5

解法

 辺の長さが整数となる折り方しかできないので,最終的に作られる面積 A の長方形の種類は O( A ) 通りしかありません.また,片方の辺の長さ x を決めたとき,他方の辺の長さは y = \frac A x と定まります(ただし x \mid A である (xA を割り切る)場合に限る).この x, y に関して,折りたたむ回数の最小値をそれなりに高速に求められれば,問題を解くことができます.x, y のどちらを縦にするかで自由度がありますが,両方試しても定数倍の差なので計算時間的な問題にはなりません.
 さて,操作完了後の紙の大きさを h \times w と仮定したとします(向きも含めて).このとき必要な操作の回数はどのように求まるでしょうか? まず,縦方向の線で折ったときには高さが不変で,横方向の線で折ったときには幅が不変であることが分かります.従って,高さと幅はそれぞれ独立であり,別々に求めてから足し合わせても大丈夫なことが分かります.高さと幅で本質的な違いは無いので,ここでは高さについてだけ書きます.ここでおもむろに,操作の逆順を考えてみます.すなわち,高さ h に折りたたまれた状態から紙を広げていって,高さ H: にするための操作回数を考えます.高さが h である状態から紙を開いたとして,達成できる最大の高さは,対応する折りたたみが丁度真ん中で折られていたことにした場合で,2h が最大となります(折りたたみで考えると,折りたたみで分割された辺の内,長い方が折りたたみ後の長さとなることから).h をどんどん倍にしていって,H 以上になるまでにかかる回数が,高さに関する最適な操作回数です(Hh の 2 の冪乗倍でない場合でも最後の操作で適当に調整できる).その回数を整数で求めるとすると,\frac H h の切り上げ除算の(2 を底とする)対数を切り上げた値,\lceil \log_2 \lceil \frac H h \rceil \rceil となります.幅に関しても同様に求め,足し合わせたのが,仮定した x, y に対する最適値です.
 x, y の取り方が O( A ) 通りあり,対数の切り上げを整数で求めるのにビットシフト等を使ったとすると 1 回あたり O( \log( \max( H, W ) ) ) 時間なので,全体では O( A \log( \max( H, W ) ) ) 時間となります.
 以下コードですが,部分問題を解くための関数をメイン部分と同じにしていたことに今気付きました.偶然シグネチャが違っていていい感じにオーバーロードされてる…….

コード

using LL = long long;
template < typename T = int > using LIM = numeric_limits< T >;

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )

constexpr int INF = LIM<>::max();

int log2ceil( const LL n )
{
	return 63 - __builtin_clzll( n ) + ( 1 < __builtin_popcountll( n ) );
}

class FoldingPaper2
{
public:
	int solve( int W, int H, int A )
	{
		int res = INF;
		REP( i, 1, A + 1 )
		{
			if ( A % i )
			{
				continue;
			}
			res = min( res, solve( W, H, i, A / i ) );
			res = min( res, solve( W, H, A / i, i ) );
		}
		return res == INF ? -1 : res;
	}

	int solve( const int W, const int H, const int w, const int h )
	{
		if ( W < w || H < h )
		{
			return INF;
		}
		return log2ceil( ( W + w - 1 ) / w ) + log2ceil( ( H + h - 1 ) / h );
	}
};