Hatena::Grouptopcoder

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

 | 

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じゃないっぽくて, 明らかにめんどくさそうな図が載っていたので, 読む事を放棄した.

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/Mi_Sawa/20120415
 |