Codeforces Round #332 DIV2 D問題 - Spongebob and Squares

Source

Codeforces Round #332 DIV2 D問題 (2000pt)
Problem description

問題概要

縦横に $1$ ずつの間隔で線が引いてあるような,高さ $n$,幅 $m$ の方眼紙を考える.
その方眼紙に含まれる正方形の数を $f(n,m)$ と書く.
正整数 $X$ が与えられるので $f(n,m) = X$ となるような正整数の組 $(n,m)$ を列挙する問題.

解法

$n \leq m$ の場合のみを考え,$n,m$ を反転したものも答えに加えれば良い.
大きさ $k$ の正方形の数は $(n-k+1)(m-k+1)$ 個作れるから
\begin{align*}
f(n,m) &= nm + (n-1)(m-1) + (n-2)(m-2) + \cdots + 1 \times (m-n+1) \\
&= \sum_{k=1}^n k (m-n+k) \\
&= \sum_{k=1}^n k^2 + k(m-n) \\
&= \frac{n(n+1)(2n+1)}{6} + \frac{n(n+1)(m-n)}{2} \\
&= \frac{n(n+1)(2n+1 + 3(m-n))}{6} \\
&= \frac{n(n+1)(3m - n + 1)}{6}
\end{align*}となる.
よって,$n$ を全探索して,$m$ が $n$ 以上の整数になる場合を探せば良い.
上の式から $n \leq (6X)^{1/3}$ にならなければならないから,$n$ のパターンの数は十分小さく間に合う.
時間計算量は $O(X^{1/3})$ 程度.

C++のスパゲッティなコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar()
#define mypc(c) putchar(c)

#define ll long long

void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T1, class T2> void sort(int N, T1 a[], T2 b[], void *mem){int i;pair<T1,T2> *r=(pair<T1, T2>*)mem;rep(i,N)r[i].first=a[i],r[i].second=b[i];sort(r,r+N);rep(i,N)a[i]=r[i].first,b[i]=r[i].second;}

char memarr[17000000]; void *mem = memarr;

ll X;
ll res1[3000000], res2[3000000]; int ress;

int main(){
  ll i, k;

  reader(&X);

  X *= 6;

  for(k=1;k*k*k<=X;k++){
    i = X;
    if(i % k) continue;
    i /= k;
    if(i % (k+1)) continue;
    i /= k+1;

    i += k - 1;
    if(i % 3) continue;
    i /= 3;

    if(i < k) continue;

    res1[ress] = k;
    res2[ress++] = i;

    if(k!=i){
      res1[ress] = i;
      res2[ress++] = k;
    }
  }

  sort(ress, res1, res2, mem);

  writerLn(ress);
  rep(i,ress) writerLn(res1[i], res2[i]);

  return 0;
}

Current time: 2017年07月23日15時43分20秒
Last modified: 2015年11月21日16時08分08秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF332 CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: