WUPC 2012

A - 招待状

Time Limit: 2 sec / Memory Limit: 64 MB

　　「WUPCへようこそ」

　ある日，僕のもとに一通のメールが届いた．誰からは不明だが，プログラミングコンテストへの招待状であることはすぐに分かった．2012年現在，プログラミングコンテストは学生有志によって頻繁に開催されており，そのようなコンテストには日本中から競技プログラマが集まってくる．腕試しのため，僕も参加することにしよう．

　とりあえず肩慣らしとして，現在の日付と開催予定日から，今日から数えて開催日まであと何日あるかを求めるプログラムを作ってみよう．

問題文

　メールを受け取った日付と，コンテスト開催日の日付が標準入力から与えられる．両者はどちらも2012年の日付である．メールを受け取った日付から数えて，コンテスト開催日まであと何日あるかを標準出力に出力するプログラムを作成せよ．

入力

入力は以下の形式で標準入力から与えられる．

M_{a}　D_{a}
M_{b}　D_{b}

1行目はメールを受け取った日付の月 M_{a}(1 ≦ M_{a} ≦ 12) と日 D_{a}(1 ≦ D_{a} ≦ 31)が半角スペース区切りで与えられる．
2行目はコンテスト開催日の月 M_{b}(1 ≦ M_{b} ≦ 12) と日 D_{b}(1 ≦ D_{b} ≦ 31)が半角スペース区切りで与えられる．
M_{b} 月 D_{b} 日がM_{a} 月 D_{a} 日と同じか，それより前の日付になることはない．
13 月 10 日や 2 月 30 日などの無効な日付が与えられることはない．

出力

メールを受け取った日付から数えて，コンテスト開催日まであと何日あるかを標準出力に 1 行で出力せよ．
なお，最後には改行を出力せよ．

補足

2012 年における 1 月〜 12 月までの最大日数は 1 月から順番に，

31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31

である．

入力例 1

3 1
3 10

出力例 1

開催日 3/10 までは 3/1，3/2，3/3，3/4，3/5，3/6，3/7，3/8，3/9 の 9 日ある．よって，9 を出力する．開催日である 3/10 を含めてはならないことに注意せよ．

入力例 2

2 10
3 10

出力例 2

2012 年はうるう年のため，2 月は 29 日ある．
2 月が終わるまで 20 日，3/10 までは 3/1 から 9日あるため，それらの合計である 29 を出力する．

Source Name

WUPC 2012

B - パスワード

Time Limit: 2 sec / Memory Limit: 64 MB

　メールにはプログラミングコンテストへの参加チケットと，圧縮ファイルが添付されていた．参加するには添付ファイルに含まれるパズルを解く必要があるようだ．しかし，圧縮ファイルにはパスワードが掛かっていた．しかも，正しいパスワードを入力しないと自動で消滅する仕組みだ！ファイルの消滅は，参加資格の剥奪を示す．招待しておきながら参加者を篩に掛ける気なのか．意外と厄介だぞ…

　メール本文には招待状の後に，アルファベットからなる複数の文字列が羅列してあった．どうやら，2つ以上の文字列を任意の順番でつなげてできた文字列のうち，辞書順最小となるものが添付ファイルのパスワードのようだ．

問題文

　文字列が N 個与えられる．N 個の文字列の中から 2 つ以上を選んで，任意の順番で繋げてできる文字列のうち，辞書順で最小なものを出力せよ．

　ここで文字列 A が文字列 B より辞書順で小さいとは，A と B を最初の文字から比べていったとき，異なる最初の文字がアルファベット順で小さいか，または A が B の接頭辞である (B = A + ... という形になっている) ことを言う．例えば， abcd は abdc より辞書順で小さく，abcd は abcdef より辞書順で小さい．

入力

入力は以下の形式で標準入力から与えられる．

N
S_{1}
S_{2}
...
S_{i}
...
S_{N}

1 行目には文字列の数 N(2 ≦ N ≦ 50) が与えられる．
2 行目～ N+1 行目にはアルファベットの小文字のみを含む文字列が与えられる．
各文字列の長さは 50 を超えない．

出力

与えられた文字列の中から 2 つ以上を選んで，任意の順番で繋げてできる文字列のうち，辞書順で最小なものを標準出力に 1 行で出力せよ．

入力例 1

2
abcd
efgh

出力例 1

abcdefgh

この場合，abcdefgh とefghabcd の 2 種類の文字列を作ることができる．abcdefgh の方が辞書順で前に来るため，ここは abcdefgh を出力する．

入力例 2

3
caa
abb
ab

出力例 2

ababb

全部で 12 種類の文字列を作成でき，その中で最も辞書順で小さいのは ababb である．

Source Name

WUPC 2012

C - 自宅からの脱出

Time Limit: 2 sec / Memory Limit: 64 MB

　僕が入力したパスワードは正しかったようだ．とりあえず，参加資格は剥奪されずに済んだ．しかし，圧縮ファイルを解凍するにはまだしばらく時間が掛かるようだった．

　ふと，僕はここ数日家から一歩も外に出ていないことに気づいた．そして，当日，時間通りに家から出られるだろうか……と不安になってきた．というのも，僕の家は迷路のように複雑な入り組んだ構造をしており，適切な移動経路を選択しないと時間がかかりすぎてしまうからだ．コンテスト当日までに，家から出るために必要な時間を見積もっておきたい．

　さらに，僕の家にはコンテストで使うノートブック型計算機がある．家を出るのは，もちろんそれを回収した後でなければならない．つまり，僕の部屋を出て，計算機を回収し，家を出るまでの最短時間を求めておく必要がある．

問題文

　家の見取り図のデータが文字列で与えられる．見取り図のデータは二次元の座標平面上に表すことができる．見取り図は北を上にして書かれており，北西端の座標を (1,1) とすると，北東端の座標は (M,1)，南東端の座標は (M,N) となる．
座標 (x,y) の情報は y 行目の x 文字目に書かれており，

 . : 部屋
 # : 壁
 C : 計算機がある場所
 S : 「僕」の部屋
 G : 家の玄関

をそれぞれ表している．「僕」は 1 単位時間をかけて現在位置 (x,y) から東西南北のいずれかの方向に 1 進むことができる．
すなわち，(x+1,y),(x-1,y),(x,y+1),(x,y-1) のいずれかに進むことができる．ただし，移動先の座標が

　# : 壁 である場合には移動できない．
　C : 計算機がある場所 である場合はそこへ移動した後，計算機を回収したことになる．このとき，回収にかかる時間は無視できる．
　G : 家の玄関である場合は，もしその時点で計算機を回収していたならゴールとなる．そうでない場合は何も起こらない．

　「僕」が僕の部屋から出てゴールするまで(＝計算機を回収した状態で家の玄関にたどり着くまで)の最短時間を出力するプログラムを作成せよ．ただし，玄関までたどり着くことが不可能であったり，計算機を回収できない時は -1 を出力してほしい．
なお，見取り図は壁で囲われていることが保証される．

図1：入力例 1の解答

入力

入力は以下の形式で標準入力から与えられる．

N　M
S_{1}
S_{2}
...
S_{N}

1 行目に自宅のサイズを表す N(5 ≦ N ≦ 500) と M(5 ≦ M ≦ 500) が半角スペース区切りで与えられる．
2 行目から N+1 行目には，M 文字の文字列が与えられる．これらは家の見取り図のデータである．
文字列中に出現する文字列は '.', '#', 'C', 'S', 'G' のいずれかであり，意味は上に記した通りである．
S_{1}とS_{N}は '#' 以外の文字は含まず，またN行の各文字列の最初と最後の文字は必ず '#' である．
'C', 'S', 'G'の各文字は，それぞれ必ず 1 つだけ出現する．

出力

「僕」の部屋からスタートし，計算機を回収した状態で玄関へたどり着くまでの最短時間を一行に出力せよ．
ただし，そのような移動が不可能である場合は -1 を出力せよ．

入力例 1

5 5
#####
#S..#
#.C.#
#..G#
#####

出力例 1

入力例 2

7 7
#######
#S....#
#...#.#
#...#C#
#...###
#G....#
#######

出力例 2

入力例 3

7 7
#######
#S....#
#.###.#
#.#C#.#
#.###.#
#....G#
#######

出力例 3

-1

計算機を回収できないので，ゴールできない．よって，-1を出力する．

Source Name

WUPC 2012

D - 三角パズル

Time Limit: 2 sec / Memory Limit: 64 MB

　そうこうしているうちに，圧縮ファイルの解凍が終わったようだ．中を見ると，今度は直角三角形状に並んだ数列を含むテキストファイルを見つけた．

7
2 3
1 5 4

　どうやら，一番上の頂点からはじめて，一段下の直下か右下かを選び底辺まで下っていったとき，その経路中の数値の合計の最大値を求める問題のようだ．それなら簡単．上の例の場合，7 -> 3 -> 5 と選ぶのが最適で，合計は 15 となる．しかし，このようなファイルはたくさんあり，中には100段に及ぶデータもあった．これを解かなきゃ参加資格はないってことか…？
　いやまて，これはプログラミングコンテストへの招待状だ．数列を入力として与えた時，最大値を求めるプログラムを作ってしまえばいい．おそらく，招待状を送った人物はそれを期待している．

問題文

　以下のように直角三角形上に並んだ数列が与えられる．頂点から初めて一段下の直下か右下を選び，底辺まで下ったときの経路中の数値の合計の最大値を求めよ．
　例えば，以下のような数列が与えられたとすると，

3
7 4
2 4 6
8 5 9 3

正しく選択した場合，

3
7 4
2 4 6
8 5 9 3

であり，合計値は 3 + 7 + 4 + 9 = 23 となる．

入力

入力は以下の形式で標準入力から与えられる．

N
a_{1,1}
a_{2,1}　a_{2,2}
a_{3,1}　a_{3,2}　a_{3,3}
...
a_{i,1}　a_{i,2}　...　a_{i,i}
...
a_{N,1}　a_{N,2}　...　a_{N,N}

1 行目には直角三角形の高さ N(1 ≦ N ≦ 100) が与えられる．
i 行目(2 ≦ i ≦ N+1)には数字が半角スペース区切りで i-1 個与えられる．
数列に含まれる数は 0 ≦ a_{i,j} ≦ 100(1 ≦ j ≦ i ≦ N) を満たす．

出力

数値の合計の最大値を標準出力に 1 行で出力せよ．

部分点

100点満点中，50点分については，N ≦ 20 を満たす．

入力例 1

1
3

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

1 -> 2 -> 9 -> 4 と選ぶのが最適となる．

Source Name

WUPC 2012

E - 会場への道

Time Limit: 2 sec / Memory Limit: 256 MB

　いよいよコンテスト前日になった．当日に備えて会場への経路を確認しておこう！会場まで徒歩で移動するつもりだ．僕が住む街から会場がある街（早稲田）まで，いくつかの街を経由して行く．街同士は道でつながっており，街から街へは道を経由しないと移動できない．

　コンテストで絶対に勝ちたい．だから満を持すために験を担ごう．僕は4か7で割り切れる数は縁起の良い数だと信じている．出発時間を0としたときに，会場へ到達した時間が4か7で割り切れると良い気分になれそうだ．だけど，4でも7でも割り切れない時間に到達した時は，コンテストで負けてしまう気がする．コンテストで勝つためには，多少遠回りでも4か7で割り切れる時間に到着するように移動したい．

　会場までの移動方法は自由だ．一度通った道を引き返しても，既に通った街や僕が住む街に戻っても良い．ただし，道の途中で引き返したり，一度会場に着いてから引き返すようなことはできない．

　さぁ，この条件を満たすように移動した時，会場に到着するまでにかかる最短時間を求めてみよう！

問題文

　N個の街を繋ぐM個の道路の情報が与えられる．各道路は異なる2つの街を繋いでおり，指定された時間をかけて双方向に移動することができる．道路の情報は2つの異なる街の番号(0～N-1)と時間で与えられる．「僕」のいる街の番号を0，会場のある街の番号をN-1，そして出発の時間を0とする．会場のある街への到達時間が4か7で割り切れるような方法で移動した時，その最短の到達時間を出力するプログラムを作成せよ．ただし，一度会場に着いたらそれ以上移動することはできない．また，道の途中で引き返したり，街や道の途中で休憩を取ることはできない．

図1：入力例 3の街と道の様子

入力

入力は以下の形式で標準入力から与えられる．

N　M
f_{1}　t_{1}　c_{1}
...
f_{m}　t_{m}　c_{m}

1 行目に街の数を表す N(2 ≦ N ≦ 1000) と道路の数 M(1 ≦ M ≦ min(10000, N*(N-1)/2)) が半角スペース区切りで与えられる．
2 行目～ M+1 行目にはそれぞれ道路の情報，つまり，道路が結ぶ二つの街の番号 f_{i} と t_{i}，および移動にかかる時間 c_{i} が半角スペース区切りで与えられる．
各 i について 0 ≦ f_{i} ≦ N-1 かつ 0 ≦ t_{i} ≦ N-1 ， f_{i} ≠ t_{i} ， 1 ≦ c_{i} ≦ 100000 を満たす．
二つの街を結ぶ道路の数は高々 1 つである．街から一本も道路が出ていないこともある．

出力

会場まで条件を満たすように移動するとき，その最小時間を標準出力に 1 行で出力せよ．
なお，会場までは必ず条件を満たすように移動できることが保証されている．

部分点

100点満点中，30点分については，上記条件に加え，会場まで 500 単位時間以内に移動できることが保証される．

入力例 1

2 1
0 1 4

出力例 1

スタートの街0からゴールの街1へ時間4をかけて移動できる．合計時間4は4の倍数であるので条件を満たす．したがって，答えは4である．

入力例 2

3 2
0 1 15
1 2 5

出力例 2

スタートの街0から街1へ時間15，街1からゴールの街2へ時間5をかけて移動できる．合計時間20は4の倍数であるので条件を満たす．したがって，答えは20である．

入力例 3

出力例 3

スタートの街0から街1へ時間1，街1から街2へ時間1，街2からゴールの街3へ時間1をかけて移動できる．スタートからゴールへ最短経路をたどって行くと合計時間3がかかるが，4でも7の倍数でもない．街1と街2の間を2往復すると合計時間7となり，7の倍数であるので条件を満たす．したがって，答えは7である．

Source Name

WUPC 2012

F - 最後の問題

Time Limit: 5 sec / Memory Limit: 256 MB

　いよいよコンテスト当日，僕は早稲田大学・西早稲田キャンパスに到着した．しかも，到達時間は4でも7でも割り切れる数字であった．とても縁起がいい．今ならどんな問題だって解ける気がする．
　会場の教室には既に数十名の学生が集まっていた．運営チームがジャッジシステム，AtCoderの説明を終え，もうあと数分でコンテストが始まろうとしているところだった．僕は持ってきたノートブック型計算機を広げ，高鳴る心臓を抑えつつコンテストに備える．

　(それでは，始めてください！)

　そして，コンテストが始まった．

　挑戦はどんな結果だったのか，そして，コンテストを通じて僕は何を得たのだろうか…　しかし，これはまた別の話．機会があれば語ることにしよう．ところで，このコンテストに出題された最後の問題は，次のようなものであった．

問題文

　二次元の座標平面上に格子点が N 個与えられる．それらの点の中から 4 点を選んで長方形を作る時，その最大面積を求めるプログラムを作成せよ．ただし，長方形は以下の条件を満たす必要がある．

長方形の各辺は x 軸または y 軸と並行になっていなければならない．
長方形の内部(辺は含まない)に他の点を含んではならない．

長方形を構成する4点以外の点が辺の上にある時は，内部にはないと考えるものとする．また，条件を満たす長方形が一つも作れない時は，0 を出力してほしい．

図1：条件を満たす長方形の例

図2：条件を満たさない長方形の例．長方形の辺は軸に並行でなければならない．

図3：条件を満たさない長方形の例．長方形の内部に他の点を含んではならない．

入力

入力は以下の形式で標準入力から与えられる．

N
x_{1}　y_{1}
x_{2}　y_{2}
...
x_{i}　y_{i}
...
x_{N}　y_{N}

1 行目に点の数を表す N(4 ≦ N ≦ 10000)が与えられる．
2 行目〜N+1行目にはそれぞれの点の x 座標と y 座標が半角スペース区切りで与えられる．
各 i について 0 ≦ x_{i} ≦ 999 かつ 0 ≦ y_{i} ≦ 999 を満たす．
N 点の座標はすべて異なる．

出力

与えられた点を使って条件を満たすような長方形を作る時，その最大面積を一行に出力せよ．もし，条件を満たす長方形が一つも作れない場合は，0 を出力せよ．
なお，最後には改行を出力せよ．

部分点

100点満点中，10点分については，N ≦ 100 を満たす．
また，別の20点分については，N ≦ 1000 を満たす．

入力例 1

出力例 1

4 点を選んで長方形を作ることができ，その面積は 1 である．

入力例 2

出力例 2

(0,0),(0,2),(2,2),(2,0) の 4 点を選び長方形を作ることができるが，この長方形は内部に (1,1) を含んでいるため，条件を満たさない．与えられた 5 点だけでは条件を満たす長方形を作れないため，0 を出力する．

入力例 3

出力例 3

(0,0),(0,2),(2,2),(2,0) の 4 点を選び長方形を作ることができる．辺上には他の点が重なっていても良いことに注意せよ．