Hatena::Grouptopcoder

agwの日記 RSSフィード

 | 

2013-01-21SRM 567 Div I

SRM 567 Div I

04:45 |  SRM 567 Div I - agwの日記 を含むブックマーク はてなブックマーク -  SRM 567 Div I - agwの日記  SRM 567 Div I - agwの日記 のブックマークコメント

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

250に47分。点数は低かったがレートは1245から1271に上がった。青コーダー。Room 25

Problem Status Points
250TheSquareRootDilemmaSystem Test Passed109.60
500StringGame Opened 0.00
1000Mountains Unopened
  • 250が難しかった
    • 47分かけて実装し、提出
    • 提出後も再提出すべきか否かの検証に時間を割いてしまった
  • 「Div I Easyを奇麗な実装で通す」という目標が未達成となってしまった
  • 次回の目標
    • Div I Easyを奇麗な実装で通す!

TheSquareRootDilemma

04:45 |  TheSquareRootDilemma - agwの日記 を含むブックマーク はてなブックマーク -  TheSquareRootDilemma - agwの日記  TheSquareRootDilemma - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=problem_statement&pm=12377&rd=15487

47分。109.60点。

  • 以下の式の結果が整数となる(A, B)の組を数える問題

f:id:agw:20130121105243p:image

  • 難しかった
    • どう反復させればよいかかなかなか思い当たらなかった
  • ノートで色々と試し、次の式に行き当たった

f:id:agw:20130121213948p:image

  • この式を用いて先ほどの式を展開すると以下の式を導くことができる。

f:id:agw:20130121110020p:image

  • i、jおよびkを反復させ、(ij2, ik2)を数え上げる問題に帰結した
    • std::setを用いているのは、異なる(i, j)の組でij^2が同じ値になる場合があるからだ((i, j)が(1, 3)である場合と(9, 1)である場合を考えよう)
  • 反復の条件は以下だ

f:id:agw:20130121110021p:image

以下は提出した実装(システムテストをパス)。

class TheSquareRootDilemma {
public:
  int countPairs(int N, int M) {
    std::set<std::pair<int, int> > set;

    for (int i = 1; i <= 1000000; i ++)
      for (int j = 1; i * j * j <= N; j ++)
        for (int k = 1; i * k * k <= M; k ++)
          set.insert(std::make_pair(i * j * j, i * k * k));

    return set.size();
  };
};
  • あ、しまった
    • iの反復の条件を考察せず提出してしまった!
  • 後で見直そうと考えていたことを失念することが多い...
  • 懸念点は2つあった
    • iの反復の範囲は十分か
    • 範囲が大き過ぎてTLEしないか
  • iの反復の範囲は以下が最適(jが1であるとき、ij2はどのような範囲を取るかを考えるとよい)。制約より、min(N, M)の最大値は77,777であるから範囲は十分だろう

f:id:agw:20130121105248p:image

  • 逆に範囲が大き過ぎてシステムテストでTLEするかもしれない
  • 直感ではjとkの反復の回数は意外と少ないと考えていた
    • N、Mが77,777を取ったとしても√77,777は278.88。最大でも300回弱ほどの反復しかしない
    • iが大きくなればなるほどこの数は減るはずだ
  • しかし単純に1,000,000 × 300 × 300を計算すると、90 × 109
    • ここまでの反復数にはならないとは思うが如何せん大きすぎる
  • いきなり不安になってきた
    • どうしよう。再提出しようか...
    • 77,777 × 300 × 300は7 × 109。これでも大きいが、先ほどの数字よりはマシだ
  • 自端末では一番時間がかかるであろうテストケース、(N, M) = (77,777, 77,777)を試していた
    • 計測し直してみる。0.70秒ほどであった
  • 何か間に合いそうな気もする
  • とりあえずリファクタリングして計測し、比較検討しようと考えた

リファクタリングした実装(後にシステムテストを試し、パスした)

class TheSquareRootDilemma {
public:
  int countPairs(int N, int M) {
    std::set<std::pair<int, int> > set;

    if (N > M)
      std::swap(N, M);

    for (int i = 1; i <= N; i ++)
      for (int j = 1; i * j * j <= N; j ++)
        for (int k = 1; i * k * k <= M; k ++)
          set.insert(std::make_pair(i * j * j, i * k * k));

    return set.size();
  };
};
  • 結果、0.71秒であった
    • 何かあんまり変わらないというか、少し遅いくらいだ
  • うーん
    • 再投稿をする確固たる理由がない
  • 結局初めに投稿した実装のまま行くことを選択
  • システムテストを無事パスした
  • よかったよかった
  • ?
    • 知らない間にチャレンジされていたようだ
    • (N, M) = (77,777, 77,777)でチャレンジされていた
    • 黄色コーダーの人だった。やっぱりTLEすると思ったのだろう
  • 実際、計算量は如何ほどなんだろう...?
    • 考えてみれば外側二つの反復ですら計算量が分からない...
  for (int i = 1; i <= N; i ++)
    for (int j = 1; i * j * j <= N; j ++)
      ...;
};
  • うーん、分からん
    • 今後の課題としよう(ご存知の方、ご教授ください)
  • !
    • まず初めに式を展開していた

f:id:agw:20130121110655p:image

  • なるほど、これは頭がいい
  • 何らかの値の二乗となるA、Bの組を探索すればよいのか
  • 今度実装してみよう
  • 再提出を検討するだけあって、奇麗な実装ではなかった
  • 次回こそ奇麗な実装で通したい
  • hotpepsiさん(id:firewoodさん)の実装がすごい
    • 無駄がない
    • さすが師匠

Aha! Tips on TopCoder(1)

04:45 |  Aha! Tips on TopCoder(1) - agwの日記 を含むブックマーク はてなブックマーク -  Aha! Tips on TopCoder(1) - agwの日記  Aha! Tips on TopCoder(1) - agwの日記 のブックマークコメント

SRMに参加したり練習をしていると様々なことに気付く。何故今まで気付かなかったのだろう、ということがたくさんある。少しだけまとめてメモしてみる。

  • 自端末ではTLEしないのにシステムテストでTLEすることを何回か経験していた
  • 恐らくサーバーは自端末より遅い。そのため自端末では最適化オプションを適用しないようにしている
  • TheSquareRootDilemmaではSRM開催中に2種類の実装を行った
    • 提出した実装とリファクタリングを行った実装だ
  • 今回の問題で最も時間がかかる(N, M) = (77,777, 77,777)の計測を比較した
    • 自端末では双方とも0.70秒ほどであった
  • 再提出をしなかったのは、計測に差がないのであれば再提出をしても仕方がない、といったような比較的消極的な理由であった
  • しかし、繰り返しになるが、システムテストと自端末では予想できないことが起こることがあるので、確実ではないとの考えが頭にあった
  • SRM終了後にふと気付いた
    • 「予想出来ないのであれば、アリーナで計ってしまえばよいのではないか」
  • 自分としては目から鱗であった
    • やり方は簡単。提出した実装に対してテストを行えばよい

f:id:agw:20130121112432p:image

  • 結果は0.34秒であった。提出した実装は予想よりも速く処理をしていた

f:id:agw:20130121112433p:image

  • 最も負荷の高いケースをアリーナで計測してTLEしない
    • 再提出する理由がなくなってしまった!
  • 意外と最も負荷の高いテストケースはSRM中に思いつくものだ
  • これまでは自端末でテストケースを追加し、極端に遅くなければよしとしていた
  • 今後TLEが問題になりそうな実装はアリーナで計測を行い、自信を持って提出しようと思う
 |