珍しくCodeIQの問題をやってみたので回答期限と同時にここでも発表。コードは以下。
見積もり
ダブりを考慮しない場合、ありうるプランの総数は、
2^162 ≒ 5.8 * 10^48
もある。いくらダブりを省けるといっても、可能なプランを全て作って互いに比較していくようなやり方で正解を見つけるのは難しそう。
下準備
まず計算しやすいように日付を整数に変換しておく。とりあえず1/1からの経過日数で表すことにする。2/29日はデータ中に存在するようなので、うるう年が存在する366日基準で。
1/1 => 0
12/31 => 365
名前・出国日・帰国日を保持する国クラスを作っておこう。
case class Country(name:String, start:Int, end:Int)
考え方
可能なチケットが有限である以上、ある日xまでに行ける国の数には上限がある。それを
mc(x)
と書くことにする。
問題の条件は12/31までに多くの国に行かせることだから、最終的に求めたいのは、
mc(365)
であり、1/1の時点ではまだどこにも行ってないので
mc(0) = 0
である。
一般のmc(x)を求めたい。帰国日がxの国がA, Bの2国あるとしよう、xの日に起こることは、以下の3パターンがありうる。
1.前日からすでに日本にいる
2.A国から帰国する
3.B国から帰国する
1.前日からすでに日本にいる場合
今日はどこからも帰国していないので「今日までに行ける数」は「昨日までに行けた数」と同じ。
mc(x) = mc(x-1)
2.A国から帰国する場合
A国に出国する前日（出国日と帰国日が同日になれない条件のため）までに行けた国の数は、
mc(A.start-1)
と書ける。それにA国に行ってきたので1を足す。
mc(x) = mc(A.start-1) + 1
3.B国から帰国する場合
2.と同様に、
mc(x) = mc(B.start-1) + 1
となる。以下同一の帰国日が3ヶ国以上あっても同じ。
実際のmc(x)はこれらのうち最大の場合の結果なので、擬似コードで書けばこうなる。
mc(x) = max(
mc(x-1),
(mc(A.start-1) + 1),
(mc(B.start-1) + 1)
)
再帰的なパターンに何か見覚えがある。動的計画法のメモ化再帰にできそうだ。これで最大国数が計算できる。しかも数字の1ではなく国名をリストに追加する計算をすれば、国数だけでなく直接旅程リストが出る。
コード
本質的な部分は、こうなる。
package com.tkido.ticketgobble
object main extends App {
import scala.collection.mutable.{Map => MMap}
val countries = Parser("data/tickets.txt")
val emap = countries.groupBy(_.end)
val memo = MMap[Int, List[Country]]()
def mc(day:Int) :List[Country] = {
if(memo.contains(day)){
memo(day)
}else{
val rst =
if(day < 0)
List()
else if(emap.contains(day))
( mc(day-1) :: emap(day).map(c => c :: mc(c.start - 1)) ).maxBy(_.size)
else
mc(day-1)
memo(day) = rst
rst
}
}
val list = mc(365)
println("%d %s".format(list.size, list.map(_.name).sorted.mkString(" ")))
}
中でも最も重要なのはこの行
( mc(day-1) :: emap(day).map(c => c :: mc(c.start - 1)) ).maxBy(_.size)
その日が帰国日の国ごとに「その国の出国日の前日の最高のリストにその国を付け加えたリスト」を作成し、さらに前日の最高のリストをそれに追加し、そこからサイズ最大のリストを選択する。
ちなみにemapは帰国日からその帰国日を持つ国のリストを引けるようにするマップ。
これで可能な最大の国に行けるリストが出る。最大の国数になるリストは複数ありそうだが、少なくともそのうちどれかになるはず。もう少しいじれば最大の国に行けるリストを全て出すようにもできそうだが、
あなた「もしも、枚数が同じ複数のプランがあった場合にはどうしましょうか」
依頼者「プランはひとつだけ作っていただければ結構です」
という問題の条件なので、ここまでで十分のはず。
コメント