SRM 576 Div2 Med

問題

マリオのような2D横スクロールゲームの画面level(2次元配列)と、1枚のコインの座標が与えられる。(スクロールしない。)

マップの上から下に重力が働いていて、level[y][x]が'X'ならMonaoはその上に立つことができる。また、繋がっている足場へ歩いて移動することができ、長さLのはしごを使って真上、真下にある距離L以内の足場へ移動できる。 つまり、Monaoが(x,y)の位置にいるとき、(x±1,y),(x,y±l)(0<=l<=L)へ移動できる。 最も下の足場は地面であり、level.back()の行は全てXである。

初め、Monaoは最も下の足場に立っている。 コインがある場所まで行くために必要なはしごの長さの最小値を求めなさい。はしごが必要ないときは0を返しなさい。

解法

コインの場所までたどり着けるかどうかを、BFSをする関数ableでL=0の場合から順に判定し、たどり着けるようになった時のLを返しました。上位の人は2分探索していましたが、Lは高々50なのでこれで間に合いました。

実装

#include <algorithm>
#include <array>
#include <queue>
#include <stack>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

typedef pair<char,char> P;
bool ok[50][50]={};
queue<P> q;

bool able(int len, const vector<string>& floor,
          int r, int c, int w, int h){
    rep(i,h) ok[i].fill(false);
    q = queue<P>();
    q.push(P(0,h-1));
    while(q.size()){
        P p=q.front();
        vector<P> next;
        q.pop();
        const int qx=p.first, qy=p.second;
        if(qy==r&&qx==c) return true;
        ok[qy][qx]=true;
        int lx=qx-1;
        if(lx>=0 && !ok[qy][lx] && floor[qy][lx]=='X'){
            next.push_back(P(lx,qy));
        }
        int rx=qx+1;
        if(rx<w && !ok[qy][rx] && floor[qy][rx]=='X'){
            next.push_back(P(rx,qy));
        }
        loop(i,1,len+1){
            int uy=qy-i;
            if(uy>=0 && !ok[uy][qx] && floor[uy][qx] =='X'){
                next.push_back(P(qx,uy));
            }
            int dy=qy+i;
            if(dy<h && !ok[dy][qx] && floor[dy][qx] =='X'){
                next.push_back(P(qx,dy));
            }
        }
        random_shuffle(all(next));
        rep(i,next.size()){q.push(next[i]);}
    }
    return false;
}

class ArcadeManao {
public:
    int shortestLadder(const vector <string> floor,
                       int r, int c) {
        r--;c--;
        int w=floor[0].size();
        int h=floor.size();
        rep(i,50) if(able(i,floor,r,c,w,h)) return i;
    }
};

感想

次に訪れる点をキューに入れる前にrandom_shuffle(all(next))でシャッフルしています。システムテストのケースに、levelの全ての要素がXかつコインの位置が(0,0)であるようなケースがあり、WPFで(0,0)から探索し始めるのが最後になってしまって落ちたのですが、こうすると通りました。あとで再帰で書いたらそんなことしなくても余裕でしたが...

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;
    }
};

AOJ 1244 Molecular Formula

AOJ 構文解析

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1244
元素記号と原子量の対応表と化学式が与えられる．化学式が何molか求める．
未知の元素が含まれていたら "UNKNOWN" と出力する．

続きを読む

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でもあまり変わらないと思います．
別にπじゃなくてもネイピア数や般若心経でもほぼ一緒です．

続きを読む