Hatena::Grouptopcoder

agwの日記 RSSフィード

2012-03-03Single Round Match 535

Single Round Match 535 Round 1 - Division II:

01:12 |  Single Round Match 535 Round 1 - Division II: - agwの日記 を含むブックマーク はてなブックマーク -  Single Round Match 535 Round 1 - Division II: - agwの日記  Single Round Match 535 Round 1 - Division II: - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15037

TopCoderに初めて参加。0点という結果。レートは785。

Problem Status Points
250FoxAndIntegersFailed Challenge0.0
500FoxAndGCDLCM Failed Sys. Test0.0
1000FoxAndSorting Unopened 0.0

大変悔しい。SRM 536に向けて目標を立てる。

  • 確実に1問通す。2問通したいところ
  • 問題セットの用意で時間を消費しないようにする。プラグインを使ってみよう
  • 問題を理解してから実装を始める
  • 例に予め目を通す(例には様々なヒントが記載されている)
  • 紙と鉛筆を用意する
    • 簡単な例を紙と鉛筆でテストしてから実装を始めるようにする

FoxAndIntegers

13:11 |  FoxAndIntegers - agwの日記 を含むブックマーク はてなブックマーク -  FoxAndIntegers - agwの日記  FoxAndIntegers - agwの日記 のブックマークコメント

実装とテストで15分。チャレンジフェーズで撃沈した。

  • 総括
    • 問題セットを用意するだけで3分ほど消費した
    • 問題をほとんど把握していない状態で実装を始めてしまった
    • 例に後から目を通し、実装の変更をした。時間をかなり浪費
    • 紙と鉛筆を用意していないのがそもそもの間違い
    • 今だにどのようなケースで撃墜されたか理解に至っていないという分析能力が悲しい
  • コードリーディング
    • まずA、B、Cをintで算出してからA - B、B - C、A + B、B + Cを検算するやり方が多いようだ。頭いいなぁ

提出した実装は以下。撃沈された実装であるので注意。

class FoxAndIntegers {
public:
  std::vector<int> get(int AminusB, int BminusC, int AplusB, int BplusC);
};

std::vector<int> FoxAndIntegers::get(int AminusB, int BminusC, int AplusB, int BplusC)
{
  std::vector<int> r;

  if ((AminusB + AplusB) % 2)
    return r;

  if ((AplusB + AminusB) % 2)
    return r;

  if ((BplusC + BminusC) % 2)
    return r;

  r.push_back((AminusB + AplusB) / 2);
  r.push_back((AplusB - AminusB) / 2);
  r.push_back((BplusC - BminusC) / 2);

  return r;
}

FoxAndGCDLCM

13:11 |  FoxAndGCDLCM - agwの日記 を含むブックマーク はてなブックマーク -  FoxAndGCDLCM - agwの日記  FoxAndGCDLCM - agwの日記 のブックマークコメント

実装とテストで約55分。システムテストを通らなかった。0点。

  • 総括
    • システムテストを通らなかった
    • 例題が解ければまあ大丈夫なんだろうという甘い認識をしていたのが間違い
    • Level Iと同じく、問題セットを用意するだけで時間を浪費した
    • 問題をほとんど把握していない状態で実装を開始してしまった
    • 例に後から目を通し、実装の変更をした。時間をかなり浪費
  • 実装
    • 互いに素を判定するcoprimeメソッドがバグバグ
      • 例えばa = 3、b = 3のとき、GCDは3。つまり互いに素ではないが、coprimeメソッドはtrueを返す
      • ユークリッドの互除法に苦手意識を持っているのがそもそもの間違い。理解しろ
    • 無限大の扱い
      • 無限大を表す数値を用意したい
      • 合計の取りうる最大の値は1,000,000,000,000(10^12)。ならば2,000,000,000,000を用意しようと思った
      • しかし、long longが2,000,000,000,000を扱えるかどうか確認せずに使ってしまった
      • ざっくりとした求め方を考察しよう。long longは64ビット。符号ビットを除いて63ビット使えるだろう
      • 2^10は1024。大体1000
      • 1000は10^3。3桁
      • 1,000,000,000,000は10^12。12桁。10^3の4倍の桁数がある。したがって(10^3)^4
      • 2^10は10^3と大体一緒で少し大きい。同様に(2^10)^4も(10^3)^4と大体一緒で少し大きい。これを無限大として使えばよい
      • (2^10)^4は2^40。つまり40ビット使用する。これは63ビットに収まる
      • そのため、long long r = 1LL << (40-1)として初期化すればよい
    • 与えられたaについて、a = x * yを満たすxとyを探索したい
      • xを決めれた、yは求まる(y = a / x)
      • 例えば(3, 9)と(9, 3)は等価であると考えると、探索するxの範囲は[1, floor(√a)]である(inclusiveであることに注意)
      • 安全のため、四捨五入する
  long long xp = sqrt(a) + 0.5;

  for (long long x = 1; x <= xp; x ++) {
    long long y = a / x;
            :
  }

しかしx^2の範囲が[1, a]であると考えるとsqrtも四捨五入も消えてなくなってしまうのであった。

  for (long long x = 1; x * x <= a; x ++) {
    long long y = a / x;
            :
  }

提出した実装は以下。システムテストを通らない実装なので注意。

#define SUM_INF 2000000000000LL


class FoxAndGCDLCM {
public:
  long long get(long long G, long long L);

private:
  bool coprime(long long a, long long b) const;
};

long long FoxAndGCDLCM::get(long long G, long long L)
{
  if (L % G)
    return -1;

  ll r = SUM_INF, Q = L / G;

  ll ip = static_cast<ll>(sqrt(Q) + 0.5);

  for (ll i = 1; i <= ip; i ++)
    if (Q % i == 0 && coprime(i, Q / i))
      r = std::min(i * G + Q / i * G, r);

  return r != SUM_INF ? r : -1;
}

bool FoxAndGCDLCM::coprime(long long a, long long b) const
{
  if (a % 2 == 0 && b % 2 == 0)
    return false;

  if (a > b)
    std::swap(a, b);

  ll ip = std::min(a, static_cast<ll>(sqrt(b) + 0.5));

  for (ll i = 3; i <= ip; i += 2)
    if (a % i == 0 && b % i == 0)
      return false;

  return true;
}