結果

問題 No.362 門松ナンバー
ユーザー simansiman
提出日時 2023-05-22 19:31:14
言語 Ruby
(3.3.0)
結果
AC  
実行時間 1,355 ms / 3,000 ms
コード長 1,593 bytes
コンパイル時間 421 ms
コンパイル使用メモリ 11,376 KB
実行使用メモリ 15,456 KB
最終ジャッジ日時 2023-08-24 02:02:31
合計ジャッジ時間 22,507 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 427 ms
15,400 KB
testcase_01 AC 356 ms
15,312 KB
testcase_02 AC 352 ms
15,400 KB
testcase_03 AC 222 ms
15,332 KB
testcase_04 AC 155 ms
15,204 KB
testcase_05 AC 541 ms
15,328 KB
testcase_06 AC 918 ms
15,304 KB
testcase_07 AC 539 ms
15,316 KB
testcase_08 AC 698 ms
15,436 KB
testcase_09 AC 1,072 ms
15,340 KB
testcase_10 AC 1,340 ms
15,456 KB
testcase_11 AC 1,283 ms
15,424 KB
testcase_12 AC 1,298 ms
15,196 KB
testcase_13 AC 1,335 ms
15,400 KB
testcase_14 AC 1,296 ms
15,412 KB
testcase_15 AC 1,314 ms
15,328 KB
testcase_16 AC 1,254 ms
15,284 KB
testcase_17 AC 1,170 ms
15,304 KB
testcase_18 AC 1,342 ms
15,344 KB
testcase_19 AC 773 ms
15,216 KB
testcase_20 AC 1,355 ms
15,440 KB
testcase_21 AC 209 ms
15,420 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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