Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

2012-04-28Google Code Jam 2012 Round 1A

[]Google Code Jam 2012 Round 1A 13:36

1350位43pt2:00:03
問題SmallLarge
A32:07WA
B1:50:48 2WA1:52:03
C--

落ちると思っていなかったA-Largeで落ちてマジ人権無い.

A-Largeが通ってたら985位とかなんかで通過出来ていた.

以下ソースと考え方.

A

問題理解するのに超時間かかった.

Aまでの入力にはミスがあって, これからは常にミスなく入力出来るのね.

back spaceを何回押すか解れば, 式はぱっと立てられるのね.

良く見るとdp的に出来るような式なのね.

あとはdpに書き直すだけ.

void solve(){
    int a, b;
    cin >> a >> b;
    vector<double> ps;
    rep(i, a){
        double x;
        cin >> x;
        ps.pb(x);
    }
    double res = b+2;
    double prob = 1;
    rep(i, a + 1){
        int bs = a - i;
        double tmp = 2.0 * bs + b - a + 1;
        tmp += (1 - prob) * (b + 1);
        res = min(tmp, res);

        prob *= ps[i];
    }
    cout << res << endl;
}

え? これでLargeWAですよ.

おわかりの通り,

    printf("%.6f\n", res);

とかせねばならぬ.マジ人権ない.

なんでsmall通ったし.


B

こっちは問題を理解するのは結構簡単だった.

lv2のやつで行けるのがあるなら優先的に取る.

lv1のやつしか行けないなら, 行ける中で, 一気にlv2に行ける可能性が一番無いようなやつ(つまりlv2で必要なstarがでかいやつ)に行く.

貪欲でやって, 途中で行ける所が無くなればToo Badでおしまい.

void solve(){
    int n;
    cin >> n;
    N = n;
    ls.clear();
    f.clear();
    rep(i,n){
        int a,b;
        cin >> a >> b;
        ls.pb(vector<int>(2));
        f.pb(vector<bool>(2, false));
        ls[i][0] = a;
        ls[i][1] = b;
    }
    int res = 0;
    int star = 0;
    while(star != (N<<1)){
        pair<int, int> nx;
        bool flg = false;
        rep(i, N){
            rep(j, 2){
                if(!f[i][j] && ls[i][j] <= star){
                    if(flg && nx.second){
                    } else if(j){
                        nx = mp(i, j);
                        flg = true;
                    } else if(!flg){
                        nx = mp(i, j);
                        flg = true;
                    } else if(flg && !j && !nx.second && ls[i][1] >= ls[nx.first][1]){
                        nx = mp(i,j);
                        flg = true;
                    }
                }
            }
        }
        if(!flg){
            cout << "Too Bad" << endl;
            return;
        }
        int i = nx.first, j = nx.second;
        f[i][j] = true;
        if(j == 1){
            if(f[i][0]){
                star++;
            }
            else{
                f[i][0] = true;
                star += 2;
            }
        }
        else if(!f[i][1]) star++;
        ++res;
    }
    cout << res << endl;
}

Smallだけでも通そうと思ってDFS書いたら案の定遅くて1TLE,

一気にレベル2に行く所の調節をミスって, 1WA出した.

前置インクリメントと後置インクリメントがあって気持ち悪いけれど, star += 2と見た感じ対応付けたかっただけなので許して下さい.

2012-04-15Google Code Jam 2012 Qualification Round

[]Google Code Jam 2012 Qualification Round 11:13

6364位45pt6:35:52
問題SmallLarge
A5:15:48
B6:31:08 1WA6:31:52
C6:13:50TLE
D--

まぁ酷い.

通過出来たから良しという事にしてください・・・

A

これ写像与えられなきゃ学習するしかないじゃん, 頻度解析とかやるのか, めんどくせぇ・・・

あれ, 入力は最大書いてあるけど最小書いてないな. 超小さい入力来たら解析で詰むじゃん

あれ, まさかこれサンプルで学習していいの!? 質問するか.

Is small-cases mapping same as sample case?

Yes

余裕じゃん!

書く

smallをDLして実行してcatしてみる

出力ぁゃιぃ・・・

p map.size #=> 25

あれ, アルファベットって26文字だよな, 空白入れて27で, つまりサンプルに2つ出てきてないのか・・・

p map.to_a.sort

qとzがねえ・・・

p map.to_a.sort_by(&:last)

こっちもqとzか

どうせ逆にmapされるんだろう

実行してみたらそれっぽい

AC(残り30秒)

TLEしなかった自分を褒めたい.

しかし, 事前に全部mapされてるか確認しなかった自分がクズ.

a = [
  "ejp mysljylc kd kxveddknmc re jsicpdrysi",
  "rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd",
  "de kr kd eoya kw aej tysr re ujdr lkgc jv"
]
b = [
  "our language is impossible to understand",
  "there are twenty six factorial possibilities",
  "so it is okay if you want to just give up"
]
map = {}
a.zip(b) do |x,y|
  x.each_char.zip(y.each_char) do |s,t|
    map[s] = t
  end
end
map["z"] = "q"
map["q"] = "z"
T = gets.to_i
T.times do |cas|
  s = gets
  print "Case ##{cas+1}: "
  s.each_char do |c|
    print map[c]
  end
  puts
end

B

問題文がひたすら読みにくい.

文中のサンプルに, ちゃんと変数Sが2で, pがなんとかのパターンだと,...みたいな事を書いてくれと.

Sが2固定だと思って, 入力で取った事すら忘れて1WAした.

T = gets.to_i
T.times do |cas|
  t = gets.split(" ").map(&:to_i)
  n = t.shift
  s = t.shift
  q = t.shift
  t.sort!.reverse!
  sap = 0
  res = 0
  t.each do |points|
    x, y, z = q, q-1, q-1
    if points >= 3*q - 2
      res += 1
    elsif points >= 3*q - 4 && q>=2 && sap < s
      res += 1
      sap += 1
    end
  end
  puts "Case ##{cas+1}: #{q.zero? ? n : res}"
end

C

rubyC++で計3つ書いた.

C++二つがなぜか違う答えを返しやがる事があって不安になりつつ, あってそうな方でsmallやる. AC.

1 2000000を50回でもなんとかTLEしない事を確認してLargeやったらなんかsubstrの所でrangeに入ってないよエラーみたいなの吹いて修正出来なかった.

よくわからぬ.

#include <iostream>
#include <set>
#include <sstream>

using namespace std;
typedef long long ll;

set<int> memo;
stringstream ss;
int mn, mx;
int getcnt(int n){
    ss.clear();
    ss << n;
    string s, t;
    ss >> s;
    t = s;
    int c = 0;
    int k;
    do{
        ss.clear();
        t = t.substr(1) + t[0];
        ss << t;
        ss >> k;
        if(mn <= k && k <= mx){
            ++c;
            memo.insert(k);
        }
    }while(t != s);
    return c;
}
void solve(){
    memo.clear();
    int a,b;
    ll res = 0;
    cin >> mn >> mx;
    for(int i=mn; i<=mx; ++i){
        if(!memo.count(i)){
            int c = getcnt(i);
            res += c * (c - 1) / 2;
        }
    }
    cout << res << endl;
}
int main(){
    int T;
    cin >> T;
    for(int cas=1; cas<=T; ++cas){
        cout << "Case #" << cas << ": ";
        solve();
    }
    return 0;
}

D

CのLargeをTLEってやる気無くした.

問題見たらいつもみたいにbitじゃないっぽくて, 明らかにめんどくさそうな図が載っていたので, 読む事を放棄した.

2011-06-05Google Code Jam 2011 Round 2

[]総評 20:33

OO|--|OX|--

1:39:26で31pts、925位。

Tシャツゲットしたのは嬉しい。

Bは問題把握出来たのが終了20分前で、segtreeでも使うのかなと思いつつ書ききれなかった。

Dは未だに理解していない。

以下A,Cのソースとか。

2011-05-21Google Code Jam 2011 Round 1A

[]総評 22:53

2:27:09で30pts、504位通過。

OO|O-|--

AもBも最初にぱっと思い付いたのを書いて、バグらせて、修正して提出しただけ。

Cは問題読んで「tのあるカードは全部速攻で使う」の以外はDFSするしか思い付かなかった。

N+M<=80では無理ゲーっぽいので、諦めて他に時間を使った。

以下ABを詳しく。

2011-05-09Google Code Jam 2011 Qualification Round

[]全体として 23:31

全完で通過。

しかしAとBのsmallを1ミスするというふがいなさ。

以下、各問題での思考の推移と駄コード。

コード類はテンプレ除いてあります。

各ケースについての処理を書いてる感じです。

kerlonkerlon2011/05/09 23:43まずAのときに、何これークリックしてみよー^q^ → 1 wrong try
次にBに、「出来た(キリッ」 → アウトプット作り忘れてて 1 wrong try

Mi_SawaMi_Sawa2011/05/09 23:45>kerlonさん
まぁ慣れる意味も含めてのQRだろうし、この先やらかさなきゃいいんじゃないかなw