#759194 (Crystal) No.1288 yuki collection

• 問題: No.1288 yuki collection
• ユーザー: tamura2004
• 提出日時: 2022-05-08 11:09:03
• 言語: Crystal (1.11.2)
• 結果: WA
• 実行時間: -
• コード長: 6,499 bytes
• コンパイル時間: 15,031 ms
• コンパイル使用メモリ: 304,392 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-07 22:21:37
• 合計ジャッジ時間: 18,766 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	2 ms; 5,376 KB
testcase_11	AC	2 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	167 ms; 5,376 KB
testcase_14	AC	177 ms; 5,376 KB
testcase_15	AC	134 ms; 5,376 KB
testcase_16	AC	136 ms; 5,376 KB
testcase_17	AC	179 ms; 5,376 KB
testcase_18	WA	-
testcase_19	AC	175 ms; 5,376 KB
testcase_20	AC	193 ms; 5,376 KB
testcase_21	AC	225 ms; 5,376 KB
testcase_22	AC	228 ms; 5,376 KB
testcase_23	AC	226 ms; 5,376 KB
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	99 ms; 5,376 KB
testcase_28	AC	127 ms; 5,376 KB
testcase_29	WA	-
testcase_30	AC	9 ms; 5,376 KB
testcase_31	AC	13 ms; 5,376 KB
testcase_32	AC	12 ms; 5,376 KB
testcase_33	AC	222 ms; 5,376 KB
testcase_34	AC	240 ms; 5,376 KB
testcase_35	AC	238 ms; 5,376 KB
testcase_36	AC	159 ms; 5,376 KB
testcase_37	AC	158 ms; 5,376 KB
testcase_38	AC	54 ms; 5,376 KB
testcase_39	AC	55 ms; 5,376 KB
testcase_40	AC	3 ms; 5,376 KB
testcase_41	AC	2 ms; 5,376 KB
testcase_42	AC	1 ms; 5,376 KB

ソースコード

macro make_array(value, *dims)
  {% for dim in dims %} Array.new({{dim}}) { {% end %}
    {{ value }}
  {% for dim in dims %} } {% end %}
end


# require "crystal/weighted_flow_graph/min_cost_flow"

# require "crystal/weighted_flow_graph/graph"
module WeightedFlowGraph
  class Edge
    getter to : Int32
    property rev : Int32
    property cap : Int64
    property cost : Int64
  
    def initialize(@to, @rev, @cap, @cost)
    end
  
    def inspect(io)
      io << "{to: #{@to}, rev: #{@rev}, cap: #{@cap}, cost: #{@cost}}"
    end
  end
  
  class Graph
    getter n : Int32
    getter g : Array(Array(Edge))
    getter pos : Array(Tuple(Int32, Int32))
    delegate "[]", to: g
  
    
    def initialize(n)
      @n = n.to_i
      @pos = [] of Tuple(Int32, Int32)
      @g = Array(Array(Edge)).new(@n) { [] of Edge }
    end
    
    def add(v, nv, cap, cost, origin = 0) : Int32
      v = v.to_i - origin
      nv = nv.to_i - origin
      cap = cap.to_i64
      cost = cost.to_i64

      edge_number = pos.size
      pos << {v, g[v].size}
      
      rev_v = g[v].size
      rev_nv = g[nv].size
      rev_nv += 1 if v == nv

      g[v] << Edge.new(nv, rev_nv, cap, cost)
      g[nv] << Edge.new(v, rev_v, 0i64, -cost)
      
      edge_number
    end
    
    def get_edge(i)
      _e = g[pos[i][0]][pos[i][1]]
      _re = g[_e.to][_e.rev]
      {pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost}
    end
    
    def edges
      pos.map do |(from, id)|
        _e = g[from][id]
        _re = g[_e.to][_e.rev]
        {from, _e.to, _e.cap + _re.cap, _re.cap, _e.cost}
      end
    end

    def debug(origin = 0)
      File.open("debug.dot", "w") do |fh|
        fh.puts "digraph tree {"
        edges.each do |v, nv, cap, flow, cost|
          v += origin
          nv += origin
          fh.puts "#{v} -> #{nv} [label=\"#{cap}[#{flow}],#{cost}\"]"
        end
        fh.puts "}"
      end
      puts `cat debug.dot | graph-easy --from=dot --as_ascii`
    end
  end
end


# require "crystal/priority_queue"
# プライオリティキュー
class PriorityQueue(T)
  getter f : T, T -> Bool
  getter a : Array(T)

  delegate size, to: a
  delegate empty?, to: a
  delegate "[]", to: a
  # forward_missing_to a

  def self.lesser
    new { |a,b| a > b }
  end

  def self.greater
    new { |a,b| a < b }
  end

  def initialize(&block : T, T -> Bool)
    @f = block
    @a = Array(T).new
  end

  def initialize
    @f = ->(a : T, b : T) { a < b }
    @a = Array(T).new
  end

  def <<(v : T)
    @a << v
    fixup(a.size - 1)
  end

  def pop : T
    ret = a[0]
    last = a.pop
    if a.size > 0
      a[0] = last
      fixdown
    end
    ret
  end

  def fixup(i : Int32)
    j = up(i)
    while i > 0 && comp j, i
      a.swap i, j
      i, j = j, up(j)
    end
  end

  def fixdown
    i = 0
    while lo(i) < a.size
      if hi(i) < a.size && comp lo(i), hi(i)
        j = hi(i)
      else
        j = lo(i)
      end
      break if comp j, i
      a.swap i, j
      i = j
    end
  end

  @[AlwaysInline]
  def comp(i, j)
    f.call a[i], a[j]
  end
  
  @[AlwaysInline]
  def lo(i)
    i * 2 + 1
  end
  
  @[AlwaysInline]
  def hi(i)
    i * 2 + 2
  end
  
  @[AlwaysInline]
  def up(i)
    (i - 1) >> 1
  end
end

alias PQ = PriorityQueue

module WeightedFlowGraph
  class MinCostFlow
    getter g : Graph
    getter pv : Array(Int32)
    getter pe : Array(Int32)
    getter dual : Array(Int64)
    delegate :pos, :n, to: g
    
    def initialize(@g)
      @pv = Array(Int32).new(n, 0)
      @pe = Array(Int32).new(n, 0)
      @dual = Array(Int64).new(n, 0)
    end
  
    def solve(s, t, flow_limit = Int64::MAX)
      slope(s, t, flow_limit).last
    end
  
    def dual_ref(s, t)
      dist = Array.new(n, Int64::MAX)
      pv.fill(-1)
      pe.fill(-1)
      seen = Array(Bool).new(n, false)
  
      que = PriorityQueue(Tuple(Int64, Int32)).lesser
      dist[s] = 0_i64
      que << {0_i64, s}
  
      while que.size > 0
        d, v = que.pop
        next if seen[v]
  
        seen[v] = true
        break if v == t
  
        g[v].each_with_index do |e, i|
          nv, cap, cost = e.to, e.cap, e.cost
          next if seen[nv] || cap == 0
  
          n_cost = cost - dual[nv] + dual[v]
          next unless dist[nv] - dist[v] > n_cost
  
          dist[nv] = dist[v] + n_cost
          pv[nv] = v
          pe[nv] = i
          que << {dist[nv], nv}
        end
      end
  
      return false unless seen[t]
  
      n.times do |i|
        next unless seen[i]
  
        dual[i] -= dist[t] - dist[i]
      end
  
      true
    end
  
    def slope(s = 0, t = n - 1, flow_limit = Int64::MAX)
      s = s.to_i
      t = t.to_i

      flow = 0_i64
      cost = 0_i64
      prev_cost = -1
      result = [{flow, cost}]
  
      while flow < flow_limit
        break unless dual_ref(s, t)
  
        c = flow_limit - flow
        v = t
        while v != s
          c = g[pv[v]][pe[v]].cap if c > g[pv[v]][pe[v]].cap
          v = pv[v]
        end
  
        v = t
        while v != s
          e = g[pv[v]][pe[v]]
          e.cap -= c
          g[v][e.rev].cap += c
          v = pv[v]
        end
  
        d = -dual[s]
        flow += c
        cost += c * d
        result.pop if prev_cost == d
        result << {flow, cost}
        prev_cost = d
      end
  
      result
    end
  end
end

include WeightedFlowGraph

enum C
  Y
  U
  K
  I
end

n = gets.to_s.to_i
s = gets.to_s.chars.map do |c|
  case c
  when 'y' then C::Y
  when 'u' then C::U
  when 'k' then C::K
  when 'i' then C::I
  else          raise "bad"
  end
end
v = gets.to_s.split.map(&.to_i64)

g = Graph.new(n + 2)
root = n
goal = n + 1
INF = 1e5.to_i64
MAX = 1e9.to_i64

# 先頭のyにrootから辺を貼る
n.times do |i|
  if s[i].y?
    g.add root, i, INF, 0
    break
  end
end

# 次の出現位置を事前計算
nex = make_array(-1, n, 4)
nex[-1][s[-1].value] = n - 1
(0...n - 1).reverse_each do |i|
  4.times { |j| nex[i][j] = nex[i + 1][j] }
  nex[i][s[i].value] = i
end

# 隣接する同じ文字に辺を貼る
(0...n-1).each do |i|
  j = nex[i+1][s[i].value]
  next if j == -1
  g.add i, j, INF, 0
end

# y,u,kからu,k,iへ辺を貼る
(0...n-1).each do |i|
  j = s[i].value + 1
  next if j == 4
  if nex[i+1][j] != -1
    g.add i, nex[i+1][j], 1, MAX - v[i]
  end
end

# iからgoalへ辺を貼る
n.times do |i|
  next unless s[i].i?
  g.add i, goal, 1, MAX - v[i]
end

# g.debug
flow, cost = MinCostFlow.new(g).solve(root, goal, n)
ans = flow * MAX * 4 - cost
pp ans