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