Last active
August 29, 2015 14:01
-
-
Save doraTeX/7138f8fb84dd65725ece to your computer and use it in GitHub Desktop.
結城浩さんの CodeIQ の アルゴリズム問題「チケットゴブル問題」( https://codeiq.jp/ace/yuki_hiroshi/q863 )をTeX言語(TeX on LaTeX)で解きました。TeX Liveなどで pdflatex ticketgobble とすればコンパイルできます。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
%% 【問題】 | |
%% 国名 出国日-帰国日 | |
%% の形で,旅行プランの一覧が与えられている。 | |
%% この中から,日程が重複しないように,できるだけ多くの国に訪れる旅行プランの列を作ること。 | |
%% ・「滞在期間が長いほどよい」など他の条件は課さない。訪れる国の数を最大化するだけでよい。 | |
%% ・帰国日と次の出発日が同一になるのは不可。 | |
%% ・最大化する方法が複数ある場合は,そのうち1つの方法を提示するだけでよい。 | |
%% ・解答は | |
%% 訪れることのできる国の数 訪れることのできる国の一覧(アルファベット順) | |
%% の形で提示すること。 | |
%% | |
%% 【TeXによる解答の方針】 | |
%% ・\C1,\C2,... : 都市名を保持する制御綴 | |
%% ・\S1,\S2,... : 出国日を保持する制御綴 | |
%% ・\E1,\E2,... : 出国日を保持する制御綴 | |
%% を用意し,\E* に対して昇順でアクセスするような添字へのアクセサ \A* をさらに定義するという形で,ソートを実現。 | |
%% ソートは挿入ソートで実装。 | |
%! pdflatex ticketgobble | |
\documentclass{article} | |
\usepackage{pgffor} | |
\usepackage{ifthen} | |
\parindent=0pt | |
\hyphenpenalty=10000 | |
\sloppy | |
\makeatletter | |
\newcount\ticketTotal | |
\newcount\ticketCount | |
\def\solve#1{% | |
\futurelet\@nexttoken\@inputTickets#1\relax | |
\sort{E}{\ticketTotal}{A}% 帰国日の順でソート | |
\selectTickets % 帰国日の早い順に貪欲法で選んでゆく | |
\sort{I}{\ticketCount}{B}% 結果をアルファベット順でソート | |
\outputResult | |
} | |
\def\@inputTickets{% | |
\ifx\@nexttoken\relax | |
\let\@next\relax | |
\else | |
\let\@next\@@inputTickets | |
\fi | |
\@next | |
} | |
\def\@@inputTickets#1 #2/#3-#4/#5 {% | |
\advance\ticketTotal by 1 | |
\@namedef{C\the\ticketTotal}{#1}% | |
\dayCount{#2}{#3}% | |
\expandafter\edef\csname S\the\ticketTotal\endcsname{\result}% | |
\dayCount{#4}{#5}% | |
\expandafter\edef\csname E\the\ticketTotal\endcsname{\result}% | |
\futurelet\@nexttoken\@inputTickets | |
} | |
%% 月,日のペアから,1/1から数えた通算日数(閏年)に変換して \result に格納 | |
\def\dayCount#1#2{% | |
\@tempcnta=#1 | |
\@tempcntb=#2 | |
\advance\@tempcntb by \ifcase#1\or0\or31\or60\or91\or121\or152\or182\or213\or244\or274\or305\or335\fi\relax | |
\edef\result{\the\@tempcntb}% | |
} | |
\newcount\cj | |
\newcount\ck | |
\newcount\cn | |
\newcount\cp | |
%% #1 をキーとして挿入ソートを行う。#2 はデータ総数。#3 という名前のソート結果へのアクセサを定義する。 | |
\def\sort#1#2#3{% | |
\def\sortKeyName{#1}% | |
\def\totalCount{#2}% | |
\def\accessorName{#3}% | |
\foreach \i in {1,...,\totalCount}{% | |
\expandafter\xdef\csname\accessorName\i\endcsname{\i}% | |
}% | |
\foreach \i in {2,...,\totalCount}{% | |
\edef\@temp{\csname\accessorName\i\endcsname}% | |
\cj=\i\relax | |
\ck=\cj\relax | |
\advance\ck by -1 | |
\cn=\csname\sortKeyName\csname\accessorName\i\endcsname\endcsname\relax | |
\cp=\csname\sortKeyName\csname\accessorName\the\ck\endcsname\endcsname\relax | |
\advance\cp by -\cn\relax | |
\whiledo{\cj>1\AND\cp>0}{% | |
\ck=\cj | |
\advance\ck by -1 | |
\expandafter\xdef\csname\accessorName\the\cj\endcsname{\csname\accessorName\the\ck\endcsname}% | |
\advance\cj by -1 | |
\ifnum\cj>1 | |
\ck=\cj | |
\advance\ck by -1 | |
\cp=\csname\sortKeyName\csname\accessorName\the\ck\endcsname\endcsname\relax | |
\advance\cp by -\cn\relax | |
\fi | |
}% | |
\expandafter\xdef\csname\accessorName\the\cj\endcsname{\@temp}% | |
}% | |
} | |
\newcount\prevEndDay | |
\newcount\currentStartDay | |
\def\selectTickets{% | |
\foreach \i in {1,...,\ticketTotal}{% | |
\edef\j{\csname A\i\endcsname}% | |
\currentStartDay=\csname S\j\endcsname\relax | |
\ifnum\currentStartDay>\prevEndDay\relax | |
\global\advance\ticketCount by 1 | |
\expandafter\xdef\csname I\the\ticketCount\endcsname{\j}% | |
\Output{Tikcet\the\ticketCount: \csname C\j\endcsname}% | |
\global\prevEndDay=\csname E\j\endcsname | |
\fi | |
}% | |
} | |
\def\outputResult{% | |
\def\result{\the\ticketCount}% | |
\foreach \i in {1,...,\ticketCount}{% | |
\xdef\result{\result\space\csname C\csname I\csname B\i\endcsname\endcsname\endcsname}% | |
}% | |
\Output{\result}% | |
} | |
\def\Output#1{\typeout{#1}#1\par} | |
\makeatother | |
\begin{document} | |
%% 与えられた旅行プラン一覧 | |
\solve{% | |
Afghanistan 4/17-4/18 | |
Albania 9/25-10/2 | |
Algeria 11/23-11/25 | |
Andorra 8/22-8/27 | |
Angola 5/18-5/19 | |
Anguilla 3/2-3/3 | |
Antarctica 6/3-6/5 | |
Argentina 2/2-2/7 | |
Armenia 5/18-5/21 | |
Aruba 1/1-1/8 | |
Australia 3/25-3/31 | |
Austria 2/7-2/8 | |
Azerbaijan 4/11-4/13 | |
Bahamas 8/20-8/24 | |
Bahrain 7/26-7/31 | |
Bangladesh 6/22-6/26 | |
Barbados 9/5-9/7 | |
Belarus 9/8-9/15 | |
Belgium 6/8-6/10 | |
Belize 7/6-7/10 | |
Benin 8/6-8/10 | |
Bermuda 9/3-9/6 | |
Bhutan 9/14-9/19 | |
Botswana 11/23-11/24 | |
Brazil 7/10-7/13 | |
Bulgaria 2/15-2/22 | |
Burundi 3/6-3/8 | |
Cambodia 3/16-3/22 | |
Cameroon 12/3-12/9 | |
Canada 9/26-9/27 | |
Chad 12/1-12/3 | |
Chile 5/7-5/13 | |
China 1/14-1/18 | |
Colombia 3/2-3/5 | |
Comoros 8/26-8/28 | |
Congo 4/2-4/9 | |
Cuba 1/10-1/17 | |
Cyprus 6/27-6/28 | |
Denmark 2/22-2/24 | |
Djibouti 5/19-5/24 | |
Dominica 12/19-12/24 | |
Ecuador 12/7-12/8 | |
Egypt 12/5-12/6 | |
Eritrea 10/15-10/17 | |
Estonia 11/4-11/11 | |
Ethiopia 8/1-8/6 | |
Fiji 11/19-11/20 | |
Finland 2/18-2/19 | |
France 6/29-7/3 | |
Gabon 3/27-4/3 | |
Gambia 9/25-9/28 | |
Georgia 2/29-3/2 | |
Germany 3/17-3/21 | |
Ghana 11/7-11/9 | |
Gibraltar 7/10-7/15 | |
Greece 11/27-11/28 | |
Greenland 5/3-5/6 | |
Grenada 10/11-10/18 | |
Guadeloupe 12/20-12/24 | |
Guam 4/11-4/16 | |
Guatemala 3/6-3/9 | |
Guernsey 9/13-9/16 | |
Guinea 6/4-6/8 | |
Guyana 10/26-10/30 | |
Haiti 1/20-1/24 | |
Hungary 1/20-1/24 | |
Iceland 7/25-8/1 | |
India 7/21-7/28 | |
Indonesia 8/20-8/27 | |
Iraq 9/12-9/18 | |
Ireland 10/25-10/28 | |
Israel 6/11-6/18 | |
Italy 2/6-2/12 | |
Jamaica 1/23-1/25 | |
Jersey 1/31-2/6 | |
Jordan 12/5-12/6 | |
Kazakhstan 4/2-4/8 | |
Kenya 7/29-8/4 | |
Kiribati 1/3-1/5 | |
Kuwait 7/14-7/18 | |
Kyrgyzstan 6/13-6/14 | |
Latvia 2/6-2/12 | |
Lebanon 1/10-1/14 | |
Lesotho 1/29-2/3 | |
Liberia 7/14-7/18 | |
Libya 4/19-4/21 | |
Liechtenstein 3/30-4/2 | |
Lithuania 5/2-5/8 | |
Luxembourg 8/28-8/31 | |
Macao 4/3-4/10 | |
Madagascar 11/15-11/22 | |
Malawi 9/20-9/21 | |
Malaysia 11/10-11/16 | |
Maldives 10/31-11/5 | |
Mali 9/17-9/24 | |
Malta 8/23-8/25 | |
Martinique 7/28-7/29 | |
Mauritania 10/13-10/20 | |
Mauritius 12/21-12/28 | |
Mayotte 10/24-10/29 | |
Mexico 2/24-3/2 | |
Monaco 12/4-12/7 | |
Mongolia 5/6-5/8 | |
Montenegro 8/9-8/11 | |
Montserrat 12/12-12/16 | |
Morocco 6/26-6/29 | |
Mozambique 2/18-2/21 | |
Myanmar 11/29-12/3 | |
Namibia 10/10-10/12 | |
Narnia 6/8-6/9 | |
Nauru 12/15-12/19 | |
Nepal 5/6-5/8 | |
Netherlands 12/8-12/12 | |
Nicaragua 9/29-10/2 | |
Niger 4/28-5/5 | |
Nigeria 7/23-7/25 | |
Niue 5/14-5/21 | |
Norway 5/8-5/9 | |
Oman 2/13-2/16 | |
Pakistan 6/11-6/16 | |
Palau 6/11-6/14 | |
Panama 7/18-7/20 | |
Paraguay 11/9-11/15 | |
Peru 12/5-12/7 | |
Philippines 4/6-4/11 | |
Pitcairn 6/24-6/29 | |
Poland 8/27-8/28 | |
Portugal 5/27-5/31 | |
Qatar 1/16-1/23 | |
Romania 7/5-7/7 | |
Rwanda 6/6-6/7 | |
Samoa 7/1-7/2 | |
Senegal 11/19-11/20 | |
Serbia 6/20-6/24 | |
Seychelles 8/12-8/17 | |
Singapore 7/23-7/25 | |
Slovakia 6/16-6/17 | |
Slovenia 9/17-9/19 | |
Somalia 10/22-10/27 | |
Spain 9/24-9/29 | |
Sudan 1/8-1/10 | |
Suriname 11/28-11/29 | |
Swaziland 6/10-6/16 | |
Sweden 8/23-8/24 | |
Switzerland 8/31-9/4 | |
Tajikistan 1/20-1/23 | |
Thailand 6/27-6/30 | |
Togo 11/16-11/17 | |
Tokelau 3/28-3/29 | |
Tonga 5/8-5/10 | |
Tunisia 11/16-11/23 | |
Turkey 7/11-7/12 | |
Turkmenistan 11/28-11/30 | |
Tuvalu 3/15-3/22 | |
Uganda 10/6-10/9 | |
Ukraine 9/28-9/29 | |
Uruguay 7/1-7/6 | |
Uzbekistan 2/26-3/4 | |
Vanuatu 8/15-8/21 | |
Yemen 6/24-6/29 | |
Zambia 1/27-2/3 | |
Zimbabwe 10/29-11/5 | |
} | |
\end{document} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment