codeiq863チケットゴブル社の旅行プランを作れ！
キーワードは貪欲法，動的計画法，蟻本「プログラミングコンテストチャレンジブック」らしい．知らなかった．解法は下手だったが評価5．
リンク
提出コード
Gist codeiq863チケットゴブル社の旅行プランを作れ！
<?php /** * https://codeiq.jp/ace/yuki_hiroshi/q863 チケットゴブル社の旅行プランを作れ！ */ // ------------------------------------------------------- // 設定 // 入力データのエンコーディング define("INDATA_ENCODING", "SJIS"); // 内部データのエンコーディング define("INSIDEDATA_ENCODING", "UTF-8"); // 入力ファイル名 define("INFILENAME", "tickets.txt"); // 改行コード define("KAIGYO", "\r\n"); // 空白．出力整形に使う define("WHITESPACE", " "); // ------------------------------------------------------- // プロセス開始 // データ入力 $indata = mb_convert_encoding(file_get_contents(INFILENAME), INSIDEDATA_ENCODING, INDATA_ENCODING); $data = explode(KAIGYO, trim($indata)); foreach ($data as $d) { $tickets[] = new Ticket($d); } // 初期の並び順を後で使うかもしれないと思ったけれど，結局使わなかった．けどworkTicketsで作業する $workTickets = $tickets; // 同一日程チケットは1個に絞る $cut["sameTerm"] = cutSameTerm(); putCutSameTerm($cut["sameTerm"]); // 期間に収まるチケットがある場合，刈り取る．短期間チケットを優先し，余裕日数を増やす $cut["canContain"] = cutCanContain(); putCutCanContain($cut["canContain"]); // ソートする．添字の抜けを詰める usort($workTickets, "Ticket::compare"); // 期間が重なるチケットを抽出する $cut["crossGroup"] = getCrossGroup(); // 期間が重なるチケットについて，除去すべきチケットキー値を得る $cut["cross"] = optimizeCrossGroups($cut["crossGroup"]); putCrossGroup($cut["crossGroup"]); cutCross($cut["cross"]); // 結果表示 echo KAIGYO . "result" . KAIGYO; usort($workTickets, "Ticket::compareCountry"); putTickets(array_merge($workTickets)); // ------------------------------------------------------- // 以上が全プロセス // 以下クラス定義や関数 class Ticket { // 一月が持つ最大日数．month/dayを認識してのUnix時間でも良かった static $MAXDAYS = 31; // プロパティ private $properties = array(); /** * getter * http://qiita.com/mikakane/items/00c798964f7c2c122e7d#comment-0978375a35c172b48d29 PHPのGetter/Setterについて本気出して考えてみた - Qiita * @param string $name 連想配列識別子 * @return type 当該プロパティ．ない場合はnull */ public function property($name) {//, $value = null) { return isset($this->properties[$name]) ? $this->properties[$name] : null; } /** * @param type $line チケット情報文字列 */ function Ticket($line) { // $line = "Afghanistan 4/17-4/18" // 前後分割 $l = explode(" ", $line); $this->properties["country"] = $l[0]; // 始点終点分割．4/17-4/18 $days = explode("-", $l[1]); // 始点．4/17 $startday = explode("/", $days[0]); $this->properties["start"] = $startday[0] * Ticket::$MAXDAYS + $startday[1]; // 終点．4/18 $endday = explode("/", $days[1]); $this->properties["end"] = $endday[0] * Ticket::$MAXDAYS + $endday[1]; } /** * チケット期間に内包できるか * @param Ticket $ticket * @return bool 内包できる場合true */ function canContain($ticket) { $start = $ticket->property("start"); $end = $ticket->property("end"); return ($this->properties["start"] <= $start && $end <= $this->properties["end"]) ? true : false; } /** * 日程が重なるか * @param Ticket $ticket * @return bool 日程が重なる場合true */ function isCross($ticket) { $start = $ticket->properties["start"]; $end = $ticket->properties["end"]; return (($this->properties["start"] <= $start && $start <= $this->properties["end"]) || ($this->properties["start"] <= $end && $end <= $this->properties["end"])) ? true : false; } /** * 日程が同一であるか * @param Ticket $ticket * @return bool 日程が同一ならtrue */ function isSameTerm($ticket) { $isSameStart = $ticket->properties["start"] === $this->properties["start"]; $isSameEnd = $ticket->properties["end"] === $this->properties["end"]; return $isSameStart && $isSameEnd; } /** * チケット日程文字列 * @return string チケット日程文字列 */ function getTerm() { // 4/17-4/18 $startAmari = $this->properties["start"] % Ticket::$MAXDAYS; if ($startAmari === 0) { // 割り切れる場合，月は1を引く．日はMAXDAYS $term = (int) ($this->properties["start"] / Ticket::$MAXDAYS) - 1 . "/" . Ticket::$MAXDAYS . "-"; } else { $term = (int) ($this->properties["start"] / Ticket::$MAXDAYS) . "/" . $startAmari . "-"; } $endAmari = $this->properties["end"] % Ticket::$MAXDAYS; if ($endAmari === 0) { $term .= (int) ($this->properties["end"] / Ticket::$MAXDAYS) - 1 . "/" . Ticket::$MAXDAYS; } else { $term .= (int) ($this->properties["end"] / Ticket::$MAXDAYS) . "/" . $endAmari; } return $term; } /** * チケット情報文字列．Afghanistan 4/17-4/18 * @return string チケット情報文字列 */ function __toString() { // 確認 // Afghanistan 141-142 //return $this->properties["country"] . " " . $this->properties["start"] . "-" . $this->properties["end"]; // Afghanistan 4/17-4/18 return $this->properties["country"] . " " . $this->getTerm(); } /** * usort用関数 * http://www.php.net/manual/ja/function.usort.php usort — ユーザー定義の比較関数を使用して、配列を値でソートする * @param Ticket $a * @param Ticket $b */ static function compare($a, $b) { return ($a->property("start") > $b->property("start") ); } /** * usort用関数 * @param Ticket $a * @param Ticket $b * @return type */ static function compareCountry($a, $b){ return ($a->property("country") > $b->property("country") ); } /** * チケット期日を拡げる * @param Ticket $ticket */ function extendTerm($ticket) { $this->properties["start"] = min($this->properties["start"], $ticket->property("start")); $this->properties["end"] = max($this->properties["end"], $ticket->property("end")); } } /** * 同一期間チケット情報を出力する * @global Ticket $tickets * @param type $info 同一期間チケット情報 */ function putCutSameTerm($info) { $outdata = KAIGYO . __FUNCTION__ . KAIGYO; $outdata .= count($info) . "個" . KAIGYO; global $tickets; foreach ($info as $term => $i) { $outdata .= $term . KAIGYO; foreach ($i as $value) { $outdata .= WHITESPACE . $value . ":" . $tickets[$value]->property("country") . KAIGYO; } } $outdata .= KAIGYO; echo $outdata; } /** * 別チケットを包含できるために除去したチケット情報を出力する * @global Ticket $tickets * @param type $info */ function putCutCanContain($info) { $outdata = KAIGYO . __FUNCTION__ . KAIGYO; $outdata .=count($info) . "個" . KAIGYO; global $tickets; foreach ($info as $key => $i) { $outdata .= $key . ":" . $tickets[$key] . KAIGYO; foreach ($i as $value) { $outdata .=WHITESPACE . $value . ":" . $tickets[$value] . KAIGYO; } } $outdata .=KAIGYO; echo $outdata; } /** * チケット期間が同一である場合，1個だけにする * @global Ticket $workTickets */ function cutSameTerm() { global $workTickets; foreach ($workTickets as $key1 => $t1) { foreach ($workTickets as $key2 => $t2) { // 同じチケットならば比べない if ($key1 === $key2) { continue; } if ($t1->isSameTerm($t2)) { // 全パターン調べるため，ループ外側の$key1だけ登録する $cut[$t1->getTerm()][] = $key1; } } } foreach ($cut as $term) { $c = count($term); for ($i = 1; $i < $c; $i++) { unset($workTickets[$term[$i]]); } } return $cut; } /** * チケット期間中に別チケットが収まる場合，これを刈り取る * @global Ticket $workTickets */ function cutCanContain() { global $workTickets; foreach ($workTickets as $key1 => $t1) { foreach ($workTickets as $key2 => $t2) { // 同一チケットでは比べない if ($key1 === $key2) { continue; } if ($t1->canContain($t2) === true) { $cut[$key1][] = $key2; } } } foreach ($cut as $key => $value) { unset($workTickets[$key]); } return $cut; } /** * * @global Ticket $workTickets */ function getCrossGroup() { $crossGroup = array(); global $workTickets; $c = count($workTickets); for ($i = 0; $i < $c; $i++) { $tempTicket = clone $workTickets[$i]; // 重複するチケットキー値 $crossKeys = array($i); for ($j = 0; $j < $c; $j++) { if ($i === $j) { continue; } if ($tempTicket->isCross($workTickets[$j])) { // チケット期間拡張 $tempTicket->extendTerm($workTickets[$j]); $crossKeys[] = $j; } } // tempTicketが変化した場合，期間が異なる if ($tempTicket->getTerm() !== $workTickets[$i]->getTerm()) { $crossGroup[$tempTicket->getTerm()] = $crossKeys; // 重複部分をスキップする $i = end($crossKeys); } } return $crossGroup; } /** * * @global Ticaa $workTickets * @param type $info */ function putCrossGroup($info) { $outdata = __FUNCTION__ . KAIGYO; $outdata .= count($info) . "個" . KAIGYO; global $workTickets; foreach ($info as $term => $i) { $outdata.= $term . KAIGYO; foreach ($i as $value) { $outdata .= WHITESPACE . $workTickets[$value] . KAIGYO; } } $outdata.=KAIGYO; echo $outdata; } /** * 期間が重なるチケットについて，除去すべきチケットキー値を得る * @param type $info 除去すべきチケットキー値配列 */ function optimizeCrossGroups($info) { $cut = array(); foreach ($info as $i) { $cut = array_merge($cut, optimizeCrossGroup($i)); } return $cut; } /** * 一定期間内にある複数のチケットについて，重なりがなくなるような，除去すべきチケットキー値を得る * optimizeCrossGroupsから呼ばれる * @global Ticket $workTickets * @param type $info 重なりがあるチケットキー値配列 * @return type 除去すべきチケットキー値配列 */ function optimizeCrossGroup($info) { $c = count($info); if ($c < 2) { echo "error: " . __FUNCTION__ . KAIGYO; print_r($info); exit(1); } global $workTickets; $cut = array(); switch ($c) { case 2: $cut[] = $info[1]; break; case 3: $cut[] = $info[1]; if ($workTickets[$info[0]]->isCross($workTickets[$info[2]])) { $cut[] = $info[2]; } break; case 4: $cut[] = $info[1]; $cut[] = $info[2]; if ($workTickets[$info[0]]->isCross($workTickets[$info[3]])) { $cut[] = $info[2]; } break; case 5: $cut[] = $info[1]; $cut[] = $info[3]; unset($info[1]); unset($info[3]); if ($workTickets[$info[0]]->isCross($workTickets[$info[2]]) || $workTickets[$info[4]]->isCross($workTickets[$info[2]])) { $cut[] = $info[2]; if ($workTickets[$info[0]]->isCross($workTickets[$info[4]])) { $cut[] = $info[4]; } } break; default : echo "error: " . __FUNCTION__ . KAIGYO; echo '$info > 5のようです．プログラムを改善しましょう' . KAIGYO; print_r($info); exit(1); } return $cut; } /** * optimizeCrossGroupsが挙げたチケットを除去する * @global Ticket $workTickets * @param type $crossInfo */ function cutCross($crossInfo) { global $workTickets; foreach ($crossInfo as $i) { unset($workTickets[$i]); } } /** * 使用するチケット * @param Ticket $tickets */ function putTickets($tickets) { $outdata = __FUNCTION__ . KAIGYO; $outdata .= count($tickets) . " "; foreach ($tickets as $t) { $outdata .= $t->property("country") ." "; } $outdata .= KAIGYO; echo $outdata; } /** * 同一期間絞り込みと包含関係絞り込みが済んだデータと， * 期間が重なるチケットを手作業で除去したデータをつなげた． * optimizeCrossGroups()の結果と突き合わせるため，ソートする． * 一致した．2014年5月3日8時52分 */ function test() { $data = <<< EOT Kiribati 1/3-1/5 Oman 2/13-2/16 Finland 2/18-2/19 Denmark 2/22-2/24 Burundi 3/6-3/8 Germany 3/17-3/21 Tokelau 3/28-3/29 Afghanistan 4/17-4/18 Libya 4/19-4/21 Portugal 5/27-5/31 Antarctica 6/3-6/5 Rwanda 6/6-6/7 Narnia 6/8-6/9 Kyrgyzstan 6/13-6/14 Slovakia 6/16-6/17 Cyprus 6/27-6/28 Samoa 7/1-7/2 Turkey 7/11-7/12 Nigeria 7/23-7/25 Sweden 8/23-8/24 Slovenia 9/17-9/19 Malawi 9/20-9/21 Canada 9/26-9/27 Uganda 10/6-10/9 Namibia 10/10-10/12 Eritrea 10/15-10/17 Maldives 10/31-11/5 Fiji 11/19-11/20 Botswana 11/23-11/24 Chad 12/1-12/3 Egypt 12/5-12/6 Sudan 1/8-1/10 China 1/14-1/18 Tajikistan 1/20-1/23 Lesotho 1/29-2/3 Austria 2/7-2/8 Georgia 2/29-3/2 Liechtenstein 3/30-4/2 Macao 4/3-4/10 Azerbaijan 4/11-4/13 Niger 4/28-5/5 Norway 5/8-5/9 Angola 5/18-5/19 Serbia 6/20-6/24 Romania 7/5-7/7 Kuwait 7/14-7/18 Martinique 7/28-7/29 Ethiopia 8/1-8/6 Montenegro 8/9-8/11 Seychelles 8/12-8/17 Poland 8/27-8/28 Switzerland 8/31-9/4 Barbados 9/5-9/7 Belarus 9/8-9/15 Ukraine 9/28-9/29 Somalia 10/22-10/27 Ghana 11/7-11/9 Togo 11/16-11/17 Greece 11/27-11/28 Ecuador 12/7-12/8 Nauru 12/15-12/19 Guadeloupe 12/20-12/24 EOT; foreach (explode(KAIGYO, trim($data)) as $d) { $tickets[] = new Ticket($d); } usort($tickets, "Ticket::compare"); putTickets($tickets); }
