結果

問題 No.362 門松ナンバー
ユーザー siman
提出日時 2023-05-22 19:31:14
言語 Ruby
(3.4.1)
結果
AC  
実行時間 1,557 ms / 3,000 ms
コード長 1,593 bytes
コンパイル時間 518 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 12,544 KB
最終ジャッジ日時 2024-12-22 14:27:35
合計ジャッジ時間 24,552 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

T = gets.to_i
L = []

100.upto(999) do |v|
  vs = v.digits.reverse

  next if vs.uniq.size < 3

  if vs[0] < vs[1] && vs[1] > vs[2]
    L << vs
  elsif vs[0] > vs[1] && vs[1] < vs[2]
    L << vs
  end
end

def is_kadomatsu(v1, v2, v3)
  return false if v1 == v2
  return false if v1 == v3
  return false if v2 == v3
  return false if v1 > v2 && v2 > v3
  return false if v1 < v2 && v2 < v3

  true
end

def f(k)
  nums = k.digits.reverse
  v1 = nums[0..2].join.to_i
  len = nums.size
  dp2 = Array.new(len) { Array.new(10) { Array.new(10, 0) } }

  L.each do |vs|
    v2 = vs[0..2].join.to_i
    next if v1 <= v2

    dp2[2][vs[1]][vs[2]] += 1
  end

  valid = is_kadomatsu(nums[0], nums[1], nums[2])

  3.upto(len - 1) do |i|
    d = nums[i]

    if valid
      v1 = nums[i - 2]
      v2 = nums[i - 1]
      (d - 1).downto(0) do |v3|
        if is_kadomatsu(v1, v2, v3)
          dp2[i][v2][v3] += 1
        end
      end
    end

    valid &= is_kadomatsu(nums[i - 2], nums[i - 1], nums[i])

    L.each do |vs|
      dp2[i][vs[1]][vs[2]] += 1
    end

    0.upto(9) do |v|
      0.upto(9) do |u|
        next if v == u

        0.upto(9) do |z|
          next if z == v
          next if z == u
          next if z < u && u < v
          next if z > u && u > v

          dp2[i][u][v] += dp2[i - 1][z][u]
        end
      end
    end
  end

  (0..9).map { |x| dp2[len-1][x].sum }.sum + 1
end

T.times do
  k = gets.to_i

  ok = 102
  ng = 37294859064823 + 1

  while (ok - ng).abs >= 2
    x = (ok + ng) / 2

    if f(x) <= k
      ok = x
    else
      ng = x
    end
  end

  puts ok
end
0