06 September 2009

Qualification Round 問題C (Welcome to Code Jam)を修正した

Qualification Round - Google Code Jam 2009 - フリーフォーム フリークアウト

この間のGoogle Code Jam、Qualification Round。問題C(Welcome to Code Jam)が、small inputは正しく解けていたんですが、large inputがincorrectとなっていた問題。laycrsさんにコメント欄にてアドバイスをいただき、無事解くことができました。

laycrsさんからいただいたコメントを引用。

たぶん,結果が大きくなるので,doubleだと高々10進数16桁ぐらいの精度しかないので,下4桁の値は丸め誤差でずれてしまってたのだと思います.
smallだとそんなに結果大きくならないので問題ないんですけど.
こういうときの定石は,取り敢えず毎回計算のたびにmod 10000しても大丈夫なので,そうするとint型で十分対応できます.

long longでもあふれることがわかっていたので、doubleを使ってみていたんですが、高々16桁ほどだと全然足りませんね。

大きい値を扱いつつ、最終的に下数桁のみが必要な場合毎回modを使えば良いという方法は、他の場面でも使える、まさに定石ですね。勉強になりました。

以下前のバージョンとのdiffです。

diff --git a/qualification/welcomeToCodeJam/a.out b/qualification/welcomeToCodeJam/a.out
index ad3607f..6b9ec55 100755
Binary files a/qualification/welcomeToCodeJam/a.out and b/qualification/welcomeToCodeJam/a.out differ
diff --git a/qualification/welcomeToCodeJam/welcomeToCodeJam.cpp b/qualification/welcomeToCodeJam/welcomeToCodeJam.cpp
index 1bef757..b9378bb 100644
--- a/qualification/welcomeToCodeJam/welcomeToCodeJam.cpp
+++ b/qualification/welcomeToCodeJam/welcomeToCodeJam.cpp
@@ -17,6 +17,7 @@
 using namespace std;

 Int Toint(string s) {int r = 0; istringstream ss(s); ss >> r; return r;}
+string toStr(int n) {ostringstream ss; ss << n; return ss.str();}

 vector  split(const string _s, const string del)
 {
@@ -39,11 +40,11 @@ vector  split(const string _s, const string del)

 string welcome = "welcome to code jam";
 string paragpeph;
-double memo[501][20];
+int memo[501][20];

-double r(int iParagraph, int iWelcome)
+int r(int iParagraph, int iWelcome)
 {
-  double ret = 0.0;
+  int ret = 0.0;

   if (memo[iParagraph][iWelcome] != -1.0)
     return memo[iParagraph][iWelcome];
@@ -55,30 +56,18 @@ double r(int iParagraph, int iWelcome)
       else
    ret += r(i+1, iWelcome+1);

+  ret = ret % 10000;
+
   memo[iParagraph][iWelcome] = ret;

   return ret;
 }

-string getResult(double d)
-{
-  string ret(4, '0');
-  char c[1000];
-  string cs;
-
-  sprintf(c, "%.0f", d);
-  cs = c;
-
-  for (int i=0; i4; i++)
-    ret[3-i] = cs[cs.size()-1-i];
-
-  return ret;
-}
-
 string getCount(string s)
 {
   string ret;
-  double count;
+  int count;
+  char c[10];
   paragpeph = s;
   for (int i=0; i<501; i++)
     for (int j=0; j<20; j++)
@@ -86,7 +75,8 @@ string getCount(string s)

   count = r(0, 0);

-  ret = getResult(count);
+  sprintf(c, "%04d", count);
+  ret = c;

   return ret;
 }

最後にあらためて、laycrsさんどうもありがとうございました!

メモ: yum関連

  • yumの設定ファイル: /etc/yum.conf
  • 各レポジトリの設定ファイル: /etc/yum.repos.d/*
  • proxyの設定: yum.confにproxy=
  • "Metadata file does not match checksum"というエラー:
    • 一度設定をクリーンしてみる: sudo yum clean; sudo yum update
    • 問題のありそうなレポジトリをdisableにしてみる