Hatena::Grouptopcoder

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

 | 

2012-11-24DigitalArts プログラミングコンテスト2012

[][]DigitalArts プログラミングコンテスト2012 21:23

http://digitalarts2012.contest.atcoder.jp/

15位75:23300pts(1)
問題時間得点(WA)
A03:59100
B33:34100(1)
C55:23100

以下ソースとか.

A問題

rubyで書いたのに間違ってCで提出するなどした.

なんか全部ちゃんとチェックした.

FA取れなかったけどSecond acceptedだった.

def match(s, ng)
  return false if s.length != ng.length
  for i in 0...s.length
    return false if s[i] != ng[i] && ng[i] != "*"
  end
  return true
end
ss = gets.split(" ")
n = geti
ngs = []
n.times do
  ngs << gets.chomp
end
for i in 0...ss.size
  ngs.each do |ng|
    if match(ss[i], ng)
      ss[i] = "*" * ss[i].size
    end
  end
end
puts ss * " "

B問題

鬼畜場合分け系問題.

String#predとかいうわけわからぬものを書いたのと, 入力がbの時b返したので1WA.

def num(a)
  return a.ord - 'a'.ord + 1
end

s = gets.chomp.split("")
if s.length == 20 && s.all?{|c| c == 'z'}
  puts "NO"
  exit
end
if s == ['a']
  puts "NO"
  exit
end
if !s.all?{|c| c == s[0]}
  t = []
  while s == (t = s.shuffle)
  end
  puts t * ""
  exit
end

if s.size == 1
  n = num(s[0])
  res = ""
  while n != 0
    if n >= 2
      res += "b"
      n -= 2
    else
      res += "a"
      n -= 1
    end
  end
  res = "aa" if s == ["b"]
  puts res
  exit
end

#size != 1, all same char
if s[0] == 'a'
  c = 'a'
  while num(c) != s.length
    c = c.succ
  end
  puts c
  exit
elsif s[0] == 'z'
  s[0] = 'y'
  s += 'a'
  puts s * ""
  exit
else
  s[0][0] = s[0][0].succ
  s[1][0] = (s[1][0].ord - 1).chr
  puts s * ""
  exit
end

C問題

フォローしてから外すまでのツイートを足したいので, フォローした時のツイート数引いておいて, フォロー外すor最後にツイート数足せばよい.

自分自身のツイートを数えるのと, Twitterと違ってフォローが勝手に双方向になるのに気をつける.

int n, m, k;

vi tweets;
vi tl;
vector<set<int> > follows;;

void tweet(int p){
    ++tweets[p];
  //cout << p << "tweets" << endl;
}
void follow(int p, int q){
    tl[p] -= tweets[q];
    follows[p].insert(q);
  //cout << p << "follow " << q << ": -" << tweets[q] << endl;
}
void unfollow(int p, int q){
    tl[p] += tweets[q];
    follows[p].erase(q);
  //cout << p << "unfollow " << q << ": +" << tweets[q] << endl;
}
void solve(){
    rep(i, n){
        foreach(it, follows[i]){
            tl[i] += tweets[*it];
        }
        tl[i] += tweets[i];
    }
    vector<pair<int, int> > a;
    rep(i, n){
  //    cout << i << ": " << tl[i] << endl;
        a.pb(mp(-tl[i], i));
    }
    sort(all(a));
    cout << -a[k-1].first << endl;
}
int main(){
    cin >> n >> m >> k;
    tweets.resize(n);
    tl.resize(n);
    follows.resize(n);
    rep(i, m){
        char c;
        cin >> c;
        int p, q;
        if(c == 't'){
            cin >> p;
            --p;
            tweet(p);
        }else if(c == 'f'){
            cin >> p >> q;
            --p; --q;
            follow(p, q);
            follow(q, p);
        }else{
            cin >> p >> q;
            --p; --q;
            unfollow(p, q);
            unfollow(q, p);
        }
    }
    solve();
    return 0;
}
/* vim:set foldmethod=marker commentstring=//%s : */

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/Mi_Sawa/20121124
 |