Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2012-10-12

Codeforces Round #144 (Div.2)

00:38 | Codeforces Round #144 (Div.2) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces Round #144 (Div.2) - capythm@TopCoder Codeforces Round #144 (Div.2) - capythm@TopCoder のブックマークコメント

参戦しました。

今日は解法というか、競技中に考えたことをメモっておきます。

A. Perfect Permutation

問題文

順列p_1,p_2,...,p_nがある。

それぞれの値は異なっており、正の整数で最大値はnである(つまり、1~nが任意の順序で並んでいる)。

"perfect permutation"を以下のように定義する。

  • p_{p_i} = i
  • p_i \neq i

nが与えられたとき、"perfect permutation"の条件を満たす順列を出力せよ。

ただし、条件を満たす順列がない場合は"-1"を出力せよ。

考えたこと
  • サンプルを見る。
    • n=1だと"-1", n=4だと"2 1 4 3"
  • もしかして、奇数だと常に-1では?
    • n=3の場合、"1"を2つめに置くと"2 1 3", 3つめに置くと"3 2 1"で、余った要素がp_i=iになって条件を満たさない。
  • 偶数の時は二個ずつひっくり返せばいいだけ
    • n=6でも"2 1 4 3 6 5"
  • コーディングして提出→Accepted
ソースコード
#include <iostream>
using namespace std;
int main( void )
{
  int n;
  cin >> n;
  if( n % 2 == 1 ){
    cout << -1 << endl;
    return 0;
  }
  for( int i=1; i<=n; i++ ){
    int a = (i+1)/2;
    int b = i%2;
    cout << a*2-(1-b) << ' ';
  }
  cout << endl;
  return 0;
}

B. Non-square Equation

問題文

数式 x^2+s(x)x-n=0を考える。ただし、n,x は正整数であり、s(x)はxを十進表記したときの各桁の数の総和と定義する。

nが与えられたとき、数式を満たす最小のxを出力せよ。解がない場合は-1を出力せよ。

ただし、 n\leq 10^{18}とする。

考えたこと
  • 式を変形すると s(x) = \frac{n}{x}-x
    • s(x)も整数なので、xはnを割り切る必要がある。
      • ということは、xの最大値は\sqrt{n}程度か・・・
  • s(x)の最大値はx=99999999999999999の時で9×17。←後から考えると9×8でよかったorz
  • n=1から一つずつ探索すると、nの条件からループ回数がワーストケースで10^9回。これはTLEする。
    • 逆に、xの取り得る最大値sqrt{n}から減らしていって探索すればいいのでは。
    • s(x)の最大値もわかっているので、n/x-xが9×17を超えてれば探索を打ち切ればいいでしょう。
      • ちょっと不安なので多めに探索しておこう・・・
    • コーディング→Accepted
競技後思ったこと

「最小のxを出力せよ」という問題だったが、よく考えると、最大のxを出力するコードになっている。

Acceptedということは、「最小のx」=「最大のx」、つまり、解が一意に決まるらしいが、証明がよくわからない。。。

複数の解がある可能性もあったのでもうちょっと慎重にコーディングすべきだった。

ソースコード
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int main( void )
{
  ll n;
  cin >> n;
  double ds = sqrt( (double) n + 0.1 );
  ll s = (ll)ds+1LL;
  for( ll i=s; i>0; i-- ){
    double dn=n,di=i;
    if( n/i-i > 9*18+5 ) break;
    if( n % i != 0 ) continue;
    ll a = i;
    ll b = i;
    while( b > 0 ){ a += b%10; b/=10; }
    if( a == n / i ){
      cout << i << endl; return 0;
    }
  }
  cout << -1 << endl; return 0;
}