Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-03-30

Codeforces #65(Div2)

23:50

前回参加したCodeforces#62で青くなってしまったためRated。

ooo-- 2524pts / 131位(Div2だけだと54位)。

レーティングは1596→1627。青脱出ならず。

A Way Too Long Words

internationalization→i18nみたいな変換をする問題。やるだけ。

変換する条件がits length is strictly more than 10となっているのを長さ10以上と勘違いして1WA。もったいない。

gets
ARGF.read.each_line do |line|
    line.chomp!
    line = line[0] + (line.size-2).to_s + line[-1] if line.size > 10
    puts line
end

B Progress Bar

プログレスバーの表示を考える問題。

マスの数と1マスの重みが与えられて、t%完了時にプログレスバーがどんな状態になっているか出力する。やるだけ。

n,k,t = gets.split.map(&:to_i)
all = n*k
val = (t*n*k/100.0).to_i
arr = [0] * n
n.times do |i|
    arr[i] = [k, val].min
    val = [val-k, 0].max
end
puts arr.join(' ')

C Round Table Knights

円周上に等間隔で点がn個あって、この点を結んで正m角形(mは任意)ができるか判定する。ただし、使っちゃいけない点がいくつかある。

とりあえず一周して元に戻ってこないといけないので、nの約数を列挙してそれぞれ可能か試すだけ……のはずなんだけど、最初思い違いしてて、正三角形が作れないなら正六角形もだめ、正九角形もだめ……というのを使って枝刈りしていくコードを書いた。そして最大ケースを入れたらあえなくTLE

n = gets.to_i
knights = gets.split.map(&:to_i)
divs = (1..n).to_a.select{|v| n%v == 0}.select{|v| v <= n/3}

divs.each do |i|
    if n % i == 0
        (0..(i-1)).each do |start|
            ok = true
            pos = start
            (n/i).times do
                if knights[pos] == 0
                    ok = false
                    break
                end
                pos = (pos+i) % n
            end
            if ok
                puts "YES"
                exit
            end
        end
    end
end
puts "NO"

D Solitaire

n*mの四角形にトランプを敷き詰めて、ジョーカーを残ったカードのどれかと置換して、盤面上に3*3の矩形を二つ重ならないように取る。このとき、一つの矩形の中では

  • 全部のカードが同じスート
  • 全部のカードが違う数字

のどちらかを満たしている必要がある。

めんどいがやるだけの強実装。1時間くらいあったけどバグが出て時間内に終わらず。

以下、Practiceで通したコード。

class Card
    def initialize(card)
        @card = card
    end

    def suit
        @card[1]
    end

    def number
        @card[0]
    end

    def joker?
        @card == "J1" || @card == "J2"
    end

    def to_s
        @card
    end

    def ==(other)
        self.number == other.number && self.suit == other.suit
    end
end

def check(arr, row, col)
    return false if row < 0 || col < 0 || row+3 > arr.size || col+3 > arr[0].size

    numbers = []
    suits = []
    3.times do |r|
        3.times do |c|
            return false if arr[row+r][col+c].joker?
            numbers << arr[row+r][col+c].number
            suits << arr[row+r][col+c].suit
        end
    end

    numbers.uniq.size == 9 || suits.uniq.size == 1
end

def wrap(rect1, rect2)
    (rect1[0]-rect2[0]).abs < 3 && (rect1[1]-rect2[1]).abs < 3
end

cards = []
"A23456789TJQK".each_char do |num|
    "CDHS".each_char do |suit|
        cards << Card.new(num + suit)
    end
end

n,m = gets.split.map(&:to_i)
arr = []
joker = []
n.times do |row|
    a = gets.split.map{|cd| Card.new(cd)}
    a.each_with_index do |card,col|
        if card.number == "J" && (card.suit == "1" || card.suit == "2")
            joker << [row, col, card.suit]
        else
            cards.delete(card)
        end
    end
    arr << a
end

rects = []
(0..n-3).each do |row|
    (0..m-3).each do |col|
        rects << [row, col] if check(arr, row, col)
    end
end

ans = nil
rects.combination(2) do |cb|
    if !wrap(cb[0], cb[1])
        ans = cb
        joker.each_with_index do |jk,idx|
            arr[jk[0]][jk[1]] = cards[idx]
        end
        break
    end
end

if !ans && joker.size > 0
    catch(:check_loop) {
        cards.combination(joker.size).each do |cb|
            cb.permutation do |perm|
                joker.each_with_index do |jk,idx|
                    arr[jk[0]][jk[1]] = perm[idx]
                end
                nr = []
                joker.each_with_index do |jk|
                    (-2..0).each do |dr|
                        row = jk[0]+dr
                        (-2..0).each do |dc|
                            col = jk[1]+dc
                            if check(arr, row, col)
                                nr << [row, col]
                            end
                        end
                    end
                end
                (nr+rects).each do |r1|
                    nr.each do |r2|
                        if !wrap(r1, r2)
                            ans = [r1, r2]
                            throw :check_loop
                        end
                    end
                end
            end
        end
    }
end

if !ans
    puts "No solution."
else
    puts "Solution exists."
    joker.sort_by!{|a| a[2]}
    if joker.size == 0
        puts "There are no jokers."
    elsif joker.size == 1
        puts "Replace J#{joker[0][2]} with #{arr[joker[0][0]][joker[0][1]]}."
    else
        puts "Replace J1 with #{arr[joker[0][0]][joker[0][1]]} and J2 with #{arr[joker[1][0]][joker[1][1]]}."
    end
    puts "Put the first square to (#{ans[0][0]+1}, #{ans[0][1]+1})."
    puts "Put the second square to (#{ans[1][0]+1}, #{ans[1][1]+1})."
end
 |