れんしゅうちょう。

■ [AtCoder][klabtenka1]天下一プログラマーコンテスト2012予選A 02:01

http://tenka1-2012-quala.contest.atcoder.jp/

4位	129:58	350pts(4)
問題	時間	得点(WA)
A	001:15	100
B	006:44	100(1)
C	078:27	100(2)
D	109:58	50(1)

なんか通ってしまった.

以下ソースとか. いつもの通り, テンプレは略.

A問題

Fibonacciである.

a = 1
b = 1
geti.times do
  a, b = b, a
  a += b
end
p b

AC一位取れたのはrubyのおかげ!!

何項目を出力とかは, 考えるよりサンプル見て適当にずらす方が速い. 最初aを出力していたけれど, サンプル入力してbに変えるの余裕でしたみたいな感じ.

B問題

問題文はちゃんと把握してから書きましょう. ざっと見て適当に書いて出したらWAった. 死. スペースを纏めてからカンマに変えるのね, カンマに変えてからカンマを纏めるんじゃないのね.

相変わらずのスクリプト言語強.

s = gets.chomp
puts s.gsub("  ", " ").split(" ") * ","

C問題

まず, ""のネストをバラして, 最初が誰に対する発言かと, それに対してディスりか肯定かの配列にする.

そこから, t番目の発言が可能なやつの集合を持ってdpすればよい.

適当に書いたら50点だった.

O(n^2)だとわりとnがでかい時に死ぬるので, O(mn*logなんとか)とかなんとかに落とす.

t-1番目の発言が可能なやつらの集合をdpとする.

iがt番目に発言出来るかを調べる.

t番目の発言がDISりの時は,｢iが嫌ってる奴に, dpに入ってるやつが存在するか｣を調べればよい.

t番目の発言がDISりじゃない時は,｢iが嫌ってない奴に, dpに入ってるやつが存在するか｣を調べればよいが, これは｢dpに入ってるやつで, ｢iが嫌っていて, かつdpに入ってるやつ｣でないやつ｣が存在するかを調べれば良い.

これは, ｢dpに入ってる｣人数から, ｢iが嫌ってるかつdpに入ってる｣人数を引いたのが1以上かを調べれば良いという事.

保険に50ptsだったコードを残してるというセコさ.

int n, m;
vector<set<int> > g;

void solve1(){
    rep(i, n) g.pb(set<int>());
    rep(i, m){
        int a, b;
        cin >> a >> b;
        g[b-1].insert(a-1);
    }
    string s;
    vector<bool> f;
    cin >> s;
    while(s[0] != 'g'){
        if(s[s.length()-1] == '"'){
            s = s.substr(1, s.length()-2);
            f.pb(true);
        }else{
            s = s.substr(1, s.length()-4);
            f.pb(false);
        }
    }
    set<int> a, b;

    if(s[s.length()-1] == 'w'){ f.pb(false); }
    else{ f.pb(true); }

    reverse(all(f));
    s = s.substr(5);
    int x;
    stringstream ss(s);
    ss >> x;
    a.insert(x-1);

    for(int i = 0; i < f.size(); ++i){
        b.clear();
        foreach(p, a){
            rep(j, n){
                bool hoge = g[*p].count(j) == 1;
                if(hoge != f[i]){
                    b.insert(j);
                }
            }
        }
        swap(a, b);
    }
    cout << a.size() << endl;
}
void solve2(){
    rep(i, n) g.pb(set<int>());
    rep(i, m){
        int a, b;
        cin >> a >> b;
        g[a-1].insert(b-1);
    }
    string s;
    vector<bool> f;
    cin >> s;
    while(s[0] != 'g'){
        if(s[s.length()-1] == '"'){
            s = s.substr(1, s.length()-2);
            f.pb(true);
        }else{
            s = s.substr(1, s.length()-4);
            f.pb(false);
        }
    }
    set<int> a, b;

    if(s[s.length()-1] == 'w'){ f.pb(false); }
    else{ f.pb(true); }

    reverse(all(f));
    s = s.substr(5);
    int x;
    stringstream ss(s);
    ss >> x;

    set<int> dp, nex;
    dp.insert(x-1);
    rep(i, f.size()){
        nex = set<int>();
        rep(j, n){
            int cnt = 0;
            foreach(p, g[j]) if(dp.count(*p)) ++cnt;
            if(f[i]){//exist? dp and !g[j]
                if(dp.size() - cnt > 0) nex.insert(j);
            }else{//exist? dp and g[j]
                if(cnt) nex.insert(j);
            }
        }
        swap(dp, nex);
    }
    cout << dp.size() << endl;

}
int main(){
    cin >> n >> m;
    if(n <= 100) solve1();
    else solve2();
    return 0;
}

D問題

計算量気にしないで普通に探索して投げたら, smallのほとんどをACした.

メモ化して投げたら50pts貰えた.

int n;
typedef vector<string> bord;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

bool validMove(int x, int y, bord &b){
    return 0 <= x && x < n && 0 <= y && y < n && b[x][y] != '#';
}
map<pair<pii, bord>, double> memo;
double solve(int x, int y, int d, bord &b){
    pair<pii, bord> IDX(pii(x, y), b);
    if(memo.count(IDX)) return memo[IDX];
    while(validMove(x+dx[d], y+dy[d], b)){
        x += dx[d];
        y += dy[d];
    }
    if(b[x][y] == 'G') return 0;
    d += 1;
    d %= 4;
    bool r, l;
    r = validMove(x+dx[d], y+dy[d], b);
    l = validMove(x-dx[d], y-dy[d], b);
    if(r && l){
        return (solve(x+dx[d], y+dy[d], d, b) + solve(x-dx[d], y-dy[d], (d+2)%4, b)) / 2;
    }else if(r){
        return memo[IDX] = solve(x+dx[d], y+dy[d], d, b);
    }else if(l){
        return memo[IDX] = solve(x-dx[d], y-dy[d], (d+2)%4, b);
    }else{
        b[x][y] = '#';
        double res = 1 + solve(0, 0, 3, b);
        b[x][y] = '.';
        return memo[IDX] = res;
    }
}
int main(){
    cin >> n;
    bord b;
    rep(i, n){
        string str;
        cin >> str;
        b.pb(str);
    }
    b[0][0] = '.';
    printf("%.7f\n", 1 + solve(0, 0, 3, b));
    return 0;
}

ツイートする