結果

問題 No.294 SuperFizzBuzz
ユーザー vain0vain0
提出日時 2015-10-24 01:22:49
言語 F#
(.NET 7)
結果
AC  
実行時間 2,011 ms / 5,000 ms
コード長 1,802 bytes
コンパイル時間 6,003 ms
コンパイル使用メモリ 170,676 KB
実行使用メモリ 153,172 KB
最終ジャッジ日時 2023-10-11 05:18:12
合計ジャッジ時間 20,671 ms
ジャッジサーバーID
(参考情報)
judge11 / judge14
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
22,816 KB
testcase_01 AC 97 ms
23,276 KB
testcase_02 AC 2,011 ms
149,116 KB
testcase_03 AC 94 ms
23,372 KB
testcase_04 AC 94 ms
21,308 KB
testcase_05 AC 95 ms
23,292 KB
testcase_06 AC 96 ms
25,428 KB
testcase_07 AC 95 ms
23,452 KB
testcase_08 AC 201 ms
41,112 KB
testcase_09 AC 1,008 ms
92,324 KB
testcase_10 AC 1,934 ms
149,124 KB
testcase_11 AC 1,972 ms
153,168 KB
testcase_12 AC 1,959 ms
153,172 KB
testcase_13 AC 1,965 ms
152,156 KB
testcase_14 AC 1,974 ms
151,128 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) F# Compiler version 11.0.0.0 for F# 5.0
Copyright (c) Microsoft Corporation. All Rights Reserved.

/home/judge/data/code/Main.fs(59,14): warning FS0044: This construct is deprecated. please use Seq.item

ソースコード

diff #

open System
open System.Collections.Generic

let combi =
  let M = 100
  let m = Array2D.zeroCreate M M: int64 [,]
  let rec loop n r =
    if r = 0 || r = n then
      1L
    else if 0 < r && r < n then
      if m.[n, r] = 0L then
        let v = loop (n - 1) (r - 1) + loop (n - 1) r
        m.[n, r] <- v
        v
      else
        m.[n, r]
    else
      0L
  loop

let enumCombi n k =
  let u = (1L <<< n) - 1L
  let s = (1L <<< k) - 1L
  let gen s =
    if s &&& ~~~u = 0L
    then
      let t = (s ||| (s - 1L)) + 1L
      Some (s, t ||| ((((t &&& -t) / (s &&& -s)) >>> 1) - 1L))
    else None
  Seq.unfold gen s

let bitsFromInt len n =
  List.init len (fun i -> (n >>> (len - i - 1)) &&& 1L <> 0L)

let superFizzBuzz i =
  if i = 0L
  then "555"
  else
    // n 桁以上の SFB 数の i 番目
    let rec loop i n =
      let k_max = n / 3
      let count =
        [ for k in 1..k_max do
            let countFives = k * 3
            let countThrees = n - countFives
            yield combi (n - 1) countThrees ]
        |> List.sum
      if i >= count then
          loop (i - count) (n + 1)
      else
          // 全列挙
          // リストでは間に合わない
          seq {
            for k in 1..k_max do
              let countFives = k * 3
              yield! enumCombi (n - 1) (countFives - 1)  // 1の位の 5 は除外
            }
          |> Seq.sort
          |> Seq.nth (int i)
          |> (fun bs ->
                bitsFromInt n ((bs <<< 1) ||| 1L)  // 1の位は 5
                |> List.map (function | true -> 5 | false -> 3)
                |> (fun ls -> String.Join("", ls))
                )
    loop (i - 1L) 4

[<EntryPoint>]
let main argv =
  let i = Console.ReadLine() |> int
  printfn "%s" (superFizzBuzz (i - 1 |> int64))

  //exit code
  0
0