《チケットゴブル問題》をPerlで解いてみた(CodeIQ)

結城浩先生のチケットゴブル問題(https://codeiq.jp/ace/yuki_hiroshi/q863)を解いてみた。よく知られたアルゴリズム（貪欲法）に従えばもっと簡単に解けるとのことだけど、一応バッジ貰えたんでここに記録しておく。

1. アイディア

（証明に一部誤植がありました。すみません＞結城先生）

複数存在する解のうちの一つを求める手順として以下を考えた。

1) 出発日の早い順にチケットを並べなおす。
2) 二枚のチケットの日程が包含関係にあるとき、日程の長い方の航空券を取り除く（全く同じ日程の場合は一方を取り除く)。
3) こうして得られたチケットの組を{(L1,R1),(L2,R2),...,(LN,RN)}と表すことにする。
Lk, Rkはそれぞれk番目のチケットの出発日、帰還日である。
4) (l1,r1)=(L1,R1)とする。
5) (lk,rk)=(LK,RK)とする。ただしKは、LK-1<=rk-1<LKを満たすように選ぶ。
5.の手順を繰り返すことにより得られたチケットの組{(l1,r1),...,(ln,rn)}は解の一つである。

上の手順で解の一つが求められるためには、
a){(L1,R1),...,(LN,RN)}の要素のみからなる解が存在する。
b)(L1,R1)を要素とする解が存在する。
c)ある解{(l1,r1),...,(ln,rn)}に対して、{(l1,r1),...,(lk-1,rk-1)}を含み、かつLK-1<=rk-1<LKを満たすような(LK,RK)を要素とするような解が存在する。
を証明すればよい。

a)の証明
ある解{(l1,r1),...,(ln,rn)}のk枚目のチケット(lk,rk)に対し、lk<l,r<rkとなるようなチケット(r,k)が存在するとする。{(l1,r1),..,(lk-1,rk-1),(l,r),(lk+1,rk+1),...,(ln,rn)}は日程が重複しないn枚のチケットからなるのでこれも解である。日程が包含関係にあるすべてのチケットに対しこの置き換えを行って得られる解は{(L1,R1),...,(LN,RN)}の要素のみからなる。//
以下、b)c)の証明ではa)の条件を満たす解のみについて考える。

b)の証明
(L1,R1)を含まないある解{(l1,r1),...,(ln,rn)}が存在するとする。1)2)より、L1<l1かつR1<r1である。解に含まれるチケット同士では日程は重複しないのでr1<l2,したがってR1<l2。
{(L1,R1),(l2,r2),...,(ln,rn)}は日程が重複しないn枚のチケットからなるのでこれも解である。//

c)の証明
(lk,rk)=(LK,RK)ならば証明終了。そうでない場合1)2)およびLK-1<=rk-1<LKより、LK<lkかつRK<rkである。解に含まれるチケット同士では日程は重複しないのでrk<lk+1,従ってRK<lk+1である。
{(l1,r1),...,(lk-1,rk-1),(LK,RK),(lk+1,rk+1),...,(ln,rn)}は日程が重複しないn枚のチケットからなるのでこれも解である。//

2. コード

#!/usr/bin/perl -w
$infile = 'tickets.txt';
$ofilecsv = 'answer.csv';
$ofiletxt = 'answer.txt';

# $tk[$i][0] : 元データ
# $tk[$i][1] : 行先
# $tk[$i][2] : 出発日(Julian)
# $tk[$i][3] : 帰還日(Julian)
# $tk[$i][4] : 他の日程を包含する場合1, そうでない場合は0

open(INFILE, $infile) || die("# can not open $infile");
$i=0;
while(<INFILE>){
$tk[$i][0] = $_;
chomp($tk[$i][0]);
($tk[$i][1], $schedule) = split(/ /,$tk[$i][0]);
($date1, $date2) = split(/-/,$schedule);
($mm1, $dd1) = split(/\//, $date1);
($mm2, $dd2) = split(/\//, $date2);
$tk[$i][2]=jd($mm1, $dd1);
$tk[$i][3]=jd($mm2, $dd2);
$i++;
}
$nd = $i;
close(INFILE);

for ($i = 0; $i < $nd; $i++) {
$tk[$i][4] = 0;
for($j = 0; $j < $nd; $j++){
if($tk[$i][2] <= $tk[$j][2] &&
  $tk[$i][3] >= $tk[$j][3]){
if($tk[$i][2] != $tk[$j][2] ||
  $tk[$i][3] != $tk[$j][3] ||
  $i > $j){
$tk[$i][4] = 1;
}
}
}
}

@tk2 = sort {$a->[4]<=>$b->[4] or $a->[2] <=> $b->[2]} @tk;

$tk3[0] = $tk2[0];
for($i = 1; $i < $nd; $i++){
if($tk2[$i][4] == 0){
if($tk2[$i][2] > $tk3[$#tk3][3]){
$tk3[$#tk3 + 1] = $tk2[$i];
}
}
}

open(OFILECSV, ">$ofilecsv") || die("# can not open $ofilecsv\n");
printf(OFILECSV "dest,jd1,jd2, flag, str\n");
for($i = 0; $i <= $#tk3; $i++){
printf(OFILECSV "%s, %d, %d, %d, %s\n",
$tk3[$i][1], $tk3[$i][2], $tk3[$i][3], $tk3[$i][4], $tk3[$i][0]);
}

@tk4 = sort {$a->[1] cmp $b->[1]} @tk3;

open(OFILETXT, ">$ofiletxt") || die("# can not open $ofiletxt\n");
printf(OFILETXT "%d", $#tk4 + 1);
for($i = 0; $i <= $#tk4; $i++){
printf(OFILETXT " %s", $tk4[$i][1]);
}

sub jd {
my (@dm, $jd, $mm, $dd, $i);
@dm = (31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31);
$jd = 0;
($mm, $dd) = @_;
for ($i = 1; $i < $mm; $i ++){
$jd = $jd + $dm[$i-1];
}
$jd = $jd + $dd;
return $jd;
}