読者です 読者をやめる 読者になる 読者になる

simudaru's blog

Python, Rなどのメモを残していこうと思います。  よろしくお願いいたします。

【CodeIQ】チケットゴブル問題(結城 浩さんの問題)

数学ガールの作者である、結城 浩さんがCodeIQで出題していた
チケットゴブル問題が〆切を過ぎ、フィードバックも来ましたので、
自分の解答(python2.7.6)を晒してみます。
https://codeiq.jp/ace/yuki_hiroshi/q863


アルゴリズムとしては、「帰国日が早いものから順に選択していけばよい」ということになります。
数学的な証明は結城 浩さんからの回答にありますので、
自分の提出した回答をそのまま書きますと、

「ある日から帰国日までがn日のチケットとn+k日のチケットがあった場合、(n、kは自然数
n日のチケットを選択すれば、n+1日からn+k日までの間にどこかに行くことも可能であり、
n+k日までどこにも行かなければ、n+k日のチケットを選択したのと同じことになる。

つまり、n日のチケットを選択すれば、n+k日のチケットを選択した場合の選択肢を内包しているため、
n+k日のチケットを選択するよりも常に優位。
したがって、帰国日が早いものから順に選択していけばよい」

ということになります。

# -*- coding: utf-8 -*-
import datetime

input_file = "tickets.txt"
output_file = "answer_tickets.txt"

# ticketsにデータを格納
tickets = []
for line in open(input_file, 'r'):
    tmp = line.rstrip().split(' ')
    tmp[1] = (map(lambda x: datetime.datetime.strptime("2016/" + x, '%Y/%m/%d'), tmp[1].split('-')))
    ticket = []
    ticket.append(tmp[0])
    ticket.extend(tmp[1])
    tickets.append(ticket)

# 帰国日,出国日の昇順に並べる
tickets = sorted(tickets, key=lambda x: (x[2], x[1]))


# main
list_ans = []
while len(tickets) > 0: 
    # リストに残っている中で、帰国日が最も早いチケットを確保
    list_ans.append(tickets[0])
    return_date = tickets[0][2]
    # 確保したチケットの帰国日より入国日が早いか同じのチケットはリストから除く
    for x in tickets[:]:
        if(x[1] <= return_date):
            del tickets[0]
        else: break


# 国名の昇順に並べる
list_ans = sorted(list_ans, key=lambda x: x[0])

# 答えの出力
ans_txt = str(len(list_ans))
for x in list_ans:
    ans_txt = " ".join((ans_txt, x[0]))

f = open(output_file, 'w')
f.write(ans_txt) 
f.close() 


動的計画法で解かれている方も多いようでしたが、
単純なアルゴリズムで回答可能でした。
# アルゴリズムが単純なのにコードが単純に見えないのは、私の技術不足です。

前回は答えあわせをしておらず、罠にはまったので、
今回はちゃんとテストもし、手動で答えの確認もしました。

次回も楽しみにしております。