id:asi1024によるJOI予選予想問題

1〜3と同じようにScalaで書いてみました。

4.怪しい漸化式

関数型言語でメモ化ってどないするねん！とは以前から疑問に思っていましたが、ついに解かなければならない日がやって来ました。。。
結論から書くと、綺麗な方法はまだ理解できていません。

問題の要点

0≦N≦10^15 なので、配列で全部確保してメモ化すると足りない。

最初に書いたコード（長くなるのでソルバーの関数だけ）

def solve(num: Long) = {
	val hm = scala.collection.mutable.HashMap[Long, Long]()
	// hm += ((0L, 1L))
	hm += 0L -> 1L
	def inner(n: Long): Long = {
		if (hm.contains(n)) hm(n)
		else {
			val t = inner(n / 2L) + inner(n / 3L)
			hm += n -> t
			t
		}
	}
	
	inner(num)
}

要約

mutable.HashMapでメモ化

メモ

コメントアウトしてるところは(0L, 1L)のタプルを入れようとしたら、なぜか怒られたので、カッコで囲ってみたら、すげーダサくなりました。これからは素直に"->"メソッド使いますね。
あと、getOrElseUpdateというメソッドがあるらしく、それで短縮すればもうちょっと見た目がマシになりそう。

Map使わずに、1000000くらいまでの配列を作っておいて、その範囲だけメモ化する方法を教えてもらった。そっちのほうが頭良さそう。
Array使って書けばこんな感じ？（同じくソルバー関数だけ）

def solve(num: Long) = {
	val memo = new Array[Long](1000001)
	memo(0) = 1L
	for (t <- 1 to 1000000) {
		memo(t) = memo(t / 2) + memo(t / 3)
	}

	def inner(n: Long): Long = n match {
		case n: Long if (n <= 1000000) => memo(n.toInt)
		case n: Long => inner(n / 2) + inner(n / 3)
	}

	inner(num)
}

"Scala メモ化"でググると、引数をmutable.HashMapに保存して関数の名前渡しとか使うとメモ化らしきコードが楽に書けるよー、というのがあったのですが、遥かに楽ではあるけども。。。うーん。。。

あと、参考になるかなぁと思って"Haskell メモ化"でググったら謎の呪文で埋め尽くされていました。
Haskellちゃんとやってから出なおしてこい、ってことですかね。

5.短い問題文

~~問題文どころか、もはや問題の名前が手抜き~~
問題を読む。
→分からない。
→時間切れになる。
→id:asi1024 にSkypeで解法を聞く。
→二分探索すれば良いらしい。
→理解できない。。。

サンプルコードをもらって、やっと理解しました。
二分探索ってこういうことね。

import java.util.Scanner
import scala.annotation.tailrec

object Main {
	val sc = new Scanner(System.in)
	def main(args: Array[String]) {
		val sieve = (n: Int) => {
			@tailrec
			def inner(ls: List[Int], acc: List[Int], end: Int): List[Int] = {
				val x = ls.head
				val xs = ls.tail
				if (x * x <= end) {
					inner(xs.filter(_ % x != 0), x :: acc, end)
				} else acc.reverse ++ ls
			}
			inner((2 to n).toList, Nil, n)
		}

		val M, N = sc.nextInt
		val primev = sieve(M)
		
		@tailrec
		def solve(a: Int, b: Int): Int = {
			if (b <= a + 1) return a

			val t = (a + b) / 2

			@tailrec
			def inner(ls: List[Int], t: Int, prev: Int, acc: Int): Int = {
				if (ls.isEmpty) return acc
				else {
					if(ls.head - prev >= t)
						inner(ls.tail, t, ls.head, acc + 1)
					else
						inner(ls.tail, t, prev, acc)
				}
			}

			val cnt = inner(primev, t, -999999999, 0)
			if (cnt < N) solve(a, t)
			else solve(t, b)
		}

		println(solve(0, M))
	}
}