CodeIQ(チケットゴブル問題)
[CodeIQ]チケットゴブル問題
問題概要
国名と旅行日程が与えられる。
一年間でより多くの国へ行ける旅行プランをたてよ。
入力:国名 旅行期間(例:1/1-1/5)
出力:国名(アルファベット順にソート)
解法
この問題はスケジューリング問題に帰着する。
スケジューリング問題は本問題と本質的に同じ問題である。
方法は、旅行期間が早く終了するものから順に選択することで、
より多くの国へ渡航を可能とするプランを作るというもの。
提出コード(ruby)
require 'date' COUNTRY = 0 FRONT = 1 BACK = 2 question = [] days = [] t_question =[] answer = [] count = 0 f = open("tickets.txt"){|file| while l = file.gets #多次元配列宣言 t_question[count] = Array.new(3) question = l.split(" ") days = question[1].split("-") # スラッシュで分割 tmp1 = days[0].split("/") tmp2 = days[1].split("/") #探索用データ生成1 t_question[count][COUNTRY] = question[0] #チケットに必要な日数を算出 a = Date.new(2016,tmp1[0].to_i,tmp1[1].to_i) b = Date.new(2016,tmp2[0].to_i,tmp2[1].to_i) period = (b - a).to_i #探索用データ生成2 #日付を整数型へ if(tmp1[1].to_i < 10) t_question[count][FRONT] = (tmp1[0] + '0' + tmp1[1]).to_i else t_question[count][FRONT] = (tmp1[0] + tmp1[1]).to_i end if(tmp2[1].to_i < 10) t_question[count][BACK] = (tmp2[0] + '0' + tmp2[1]).to_i else t_question[count][BACK] = (tmp2[0] + tmp2[1]).to_i end count = count +1 end } #終了時間でソート t_question = t_question.sort{|a, b| a[BACK] <=> b[BACK] } #探索(すけじゅーりんぐ問題に帰着する) tmp = t_question[0][BACK] #ソートしたので最小 count = 0 answer[count] = t_question[0][COUNTRY] count = 1 t_question.each_index do |i| if t_question[i][FRONT] > tmp tmp = t_question[i][BACK] answer[count] = t_question[i][COUNTRY] count = count + 1 end end #回答フォーマット作成 str = count.to_s + ' ' answer = answer.sort answer.each_index do |i| str = str + answer[i] + ' ' end p str
解答
問題文は著作上の都合があり、提示できないが、
出力内容は正しいということで、満点をいただいた。