結果

問題 No.572 妖精の演奏
コンテスト
ユーザー siman
提出日時 2022-11-24 18:49:37
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,862 bytes
コンパイル時間 97 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 13,568 KB
最終ジャッジ日時 2024-10-01 08:21:17
合計ジャッジ時間 5,061 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:91: warning: assigned but unused variable - np
Main.rb:56: warning: assigned but unused variable - start_pos
Syntax OK

ソースコード

diff # 

N = gets.to_i
M = gets.to_i
A = M.times.map { gets.split.map(&:to_i) }

def f(start_pos, len = M)
  dp = Array.new(len + 1) { Array.new(M, 0) }

  len.times do |i|
    M.times do |from|
      next if i == 0 && start_pos != from

      a = dp[i][from]

      M.times do |to|
        na = a + A[from][to]

        if dp[i + 1][to] < na
          dp[i + 1][to] = na
        end
      end
    end
  end

  max_a = -1
  best_i = -1

  dp[len].each_with_index do |a, i|
    if max_a < a
      max_a = a
      best_i = i
    end
  end

  [best_i, max_a]
end

def find_first_step
  max_a = -1
  first_step = -1

  M.times do |i|
    _, a = f(i, M - 1)

    if max_a < a
      max_a = a
      first_step = i
    end
  end

  first_step
end

remain = N - 1

cur_pos = find_first_step
start_pos = cur_pos
pos = cur_pos
graph = Hash.new

M.times do
  next_pos, cost = f(pos, M)

  graph[pos] = [next_pos, cost]
  pos = next_pos
end

if remain > M * M
  visited = Hash.new(false)
  positions = []
  loop_cost = 0

  while !visited[cur_pos]
    positions << cur_pos
    visited[cur_pos] = true
    cur_pos, _ = graph[cur_pos]
  end

  ans = 0
  rindex = positions.rindex(cur_pos)
  head, main = positions[0...rindex], positions[rindex..]

  head.each_cons(2) do |from, to|
    _, cost = graph[from]
    ans += cost
    remain -= M
  end

  # pp [:remain, remain]
  loop_cost = 0
  main.each do |from|
    np, cost = graph[from]
    loop_cost += cost
  end

  loop_size = main.size
  loop_cnt = remain / (M * loop_size)
  remain -= M * loop_cnt * loop_size
  # pp [:remain, remain, :loop_size, loop_size, :loop_cnt, loop_cnt, :loop_cost, loop_cost]
  ans += loop_cnt * loop_cost
  cur_pos = main[0]

  _, last_cost = f(cur_pos, remain)
  ans += last_cost

  puts ans
else
  max_a = -1

  M.times do |i|
    _, a = f(i, N - 1)
    max_a = a if max_a < a
  end

  puts max_a
end
0