AOJ <JOI - Prelim 0590> 総当りではTLEになるがループ条件を変えるだけでACになる理由が分からない

状況説明

この問題を自力では解けなくてネットで検索したところサンプルコードの解答例を見つけました。
解法のヒントの数式の部分を読んで自力で実装（総当り？）して入力例で正解だったので提出したところ、
TLE(Time Limit Exceeded)になりました。

その後詳しく見比べるとforループ文の終了回数の部分（　i*i<=S　と　i<=s　）が違いました。
試しに自作のコードのそこだけを修正して提出したところAC(Accepted)となりました。
（９秒以上掛かったものが１秒以下になりました）

//AC(正解)
for(int i=1;i*i<=S;i++)

//TLE(時間切れ)
for(int i=1;i<=s;i++)

知りたいこと

結果と数式から計算量が大きく減ることは明らかなのですが、
何故forループ文の終了回数の部分（　i<=s　）を（　i*i<=S　）とするのかがよく分かりません。
数学的なことかアルゴリズム的な明快な理由があるはずだとは思うのですがアドバイス頂ければ助かります。

解答例

引用元：tobiasの日記

C++
1#include<iostream>
2#include<cmath>
3
4using namespace std;
5
6bool is_room(int S){
7
8  for(int i=1;i*i<=S;i++)
9    if((S-i)%(2*i+1)==0)return true;
10  return false;
11}
12
13int main(void){
14
15  int n,S,cnt=0;
16
17  cin >> n;
18  while(n--){
19    cin >> S;
20    if(!is_room(S))cnt++;
21  }
22  cout << cnt << endl;
23
24  return 0;
25}

補足情報（開発環境など）

Win10
VSC1.47.3
C++14
gcc version 8.2.0 (Rev3, Built by MSYS2 project)

行動規範の内容に同意します

回答1件

ベストアンサー

部屋の面積2xy+x+yは、xとyについて対称です。
よって、(x, y) = (a, b)の時に部屋の面積として成立するなら、
xとyを入れ替えた(x, y) = (b, a)の時も成立することになります。
実際、LDと洋室を90°回転し、キッチンと玄関の図形を入れ替えれば、
面積がそのままでxとyが入れ替わった部屋を作ることができます。

したがって、x <= yの場合に限定して考えてよいことになります。
そのxとyの大小関係がどこで入れ替わるか、ですが、
例えば部屋の面積がxyであれば、√Sを境にして大小が入れ替わることになります。
今回の場合、xyが部屋の面積のほぼ半分であることを考えれば、およそ√(S/2)あたりで入れ替わることが推測できます。この正確なところは私には詰め切れませんが（※追記で詰めました）、√Sより手前の時点で大小が入れ替わることは確実なので、i*i<=Sまでの範囲を調べれば十分という事になります。

数学的に詰めます。
2xy+x+y=Sという方程式を考えると、これは
(2x+1)(2y+1)=2S+1と同値になります。
2x+1<=2y+1で考えればよいので、
2x+1<=√(2S+1)、ということでやはり、おおよそ
x<=(√2/2)√Sくらいの範囲まで考えれば十分となります。

なお、2x+1,2y+1はともに3以上の奇数、2S+1は奇数なので、
「2S+1が9以上で、合成数である」と捉えることもできます。

投稿2020/08/09 18:31

編集2020/08/10 03:21