AOJ 0041 Expression

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0041

計算量的にも余裕があるし割り算も無いので総当りする。 なんとなく関数オブジェクトを使ってみたかったので、関数オブジェクトplus<int>(),minus<int>(),multiplies<int>()への参照の配列fsを作る。 数字の順列のループの中で、 インデックスの組(i,j,k) in {0,1,2}^3 (全部で27要素)のループを回してfsへアクセスすることで、ありうる演算子の組を全て試す。

実装

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=840592

SRM591 div2 hard(1000) YetAnotherTwoTeamsProblem

DP SRM

問題

あるサッカークラブに属するn人のメンバー全員の能力 s[0], s[1],...,s[n-1] が与えられる．メンバーをA，Bの2チームに分けて練習したい．次の条件を満たす分け方は何通りあるか．

  • 全てのチームメイトは必ずいずれか一方のチームに属する．
  • チームAの強さ > チームBの強さ
    ただしチームの強さは，そのチームに属するメンバーの能力の総和である．
  • チームAに属する任意のメンバーを1人チームBに移すと
    チームAの強さ < チームBの強さ となる
  • 2 <= n <= 50
  • 1 <= s[i] <= 60000

解法

全てのメンバーの能力の総和をS，チームAの強さをta，チームBの強さをtb，チームAでもっとも能力が低いメンバーをmとおくと次の式を満たします．

ta + tb = S
ta > tb
ta - s[m] < tb + s[m]

ここから次の不等式を導けます．

S/2 < ta < s[m] + S/2

これを満たす全てのtaとmの組み合わせについて，場合の数を数え上げます．

実装

コンテスト中は何を思ったかメモ化再帰でのためにdp[51][60001*51]という配列を確保しようとしていました．その後，ループに修正しているうちに時間切れに．

int n;
int sum;
// {s(i), s(i+1),..} から和がTになるような部分集合の数
ll dp[2][60001*51];
ll & dparr(int i, int j){
    return dp[i%2][j];
}

ll solve(const vector<int> & skill){
    ll ans = 0;
    for(int t=0; t<60001*50; t++){
        if(t == skill[n-1] || t == 0)
            dparr(n-1, t) = 1;
        else
            dparr(n-1, t) = 0;
    }
    if(skill[n-1] > sum - skill[n-1]) ans++;
    for(int i=n-2; i>=0; i--){
        for(int t=0; t<60001*50; t++){
            // 漸化式
            if(t - skill[i] >= 0){
                dparr(i, t) = dparr(i+1, t) + dparr(i+1, t-skill[i]);
            } else {
                dparr(i, t) = dparr(i+1, t);
            }
        }
        for (int t1 = sum/2+1; t1 < skill[i] + sum/2.0; ++t1){
            //ans += g(i+1, t1-skill[i], skill);
            ans += dparr(i+1, t1-skill[i]);
        }
    }
    pr(ans);
    return ans;
}

class YetAnotherTwoTeamsProblem {
public:
    long long count(vector<int> skill) {
//        memset(dpg,-1,sizeof(dpg));
        memset(dp,0,sizeof(dp));
        sort(skill.begin(), skill.end());
        n = skill.size();
        sum = accumulate(skill.begin(), skill.end(), 0);
        ll ans = solve(skill);
        return ans;
    }
};

RubyのCairoで円周率の壁紙を作った

Ruby

どしたの

こういうのを作りました．
https://raw.github.com/tubo028/pi_wallpaper/origin/pi_bl.png

f:id:tubo28:20130818222550p:plain

ただ円周率を10進数で一の位のから41364桁列挙した壁紙です． githubに上げてあります．
https://github.com/tubo028/pi_wallpaper
僕はWindowsで実行しましたが，フォント以外はMacでもLinuxでもあまり変わらないと思います．
別にπじゃなくてもネイピア数や般若心経でもほぼ一緒です．

続きを読む

Apacheの起動に失敗する

VPS

最近さくらのVPSを借りた。
で、ここを参考にVirtualHostの設定をした。
#14 VirtualHostの設定をしよう (2) 

<VirtualHost *:80>
  ServerName xxx.yyy.zzz
  DocumentRoot "/var/www/xxx.yyy.zzz/"
  DirectoryIndex index.html index.php
  ErrorLog /var/log/httpd/xxx.yyy.zzz_error_log
  CustomLog /var/log/httpd/xxx.yyy.zzz_access_log combined
  AddDefaultCharset UTF-8
  <Directory "/var/www/xxx.yyy.zzz/public_html">
    AllowOverride All
  </Directory>
</VirtualHost>

ただし xxx.yyy.zzz はダミー。
何度やってもエラーが出て失敗する。

# service httpd start
httpd を起動中:                                            [失敗]

特にメッセージもなく、ただ[失敗]したと言われる。
しばらく調べて、こういうのは普通ログを取っているものだと知り、見てみる。

# cat /var/log/httpd/error_log
(略)
[Tue May 14 05:26:23 2013] [notice] caught SIGTERM, shutting down
(2)No such file or directory: httpd: could not open error log file /var/log/httpd/var/www/xxx.yyy.zzz_error_log.

ErrorLog で設定した /var/log/httpd/xxx.yyy.zzz_error_log が開けないと言っている。
設定したときは恐らく自動で作ってくれるだろうと思い無視していた。いやパーミッションの問題か？
よく分からないがとりあえず空のファイルを作ってみる。xxx.yyy.zzz_access_log も無いはずなので一応一緒に。

# mkdir -p /var/log/httpd/var/www/
# touch /var/log/httpd/var/www/xxx.yyy.zzz_error_log
# touch /var/log/httpd/var/www/xxx.yyy.zzz_access_log

解決した。

# service httpd start
httpd を起動中:                                            [  OK  ]