Indeedなう（オープンコンテストB）

A - Counting on a Triangle

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社の社員である A さんは無限に広がる正三角形状の座標系を眺めています。上から x 段目の左から y 番目の座標は (x,y) の形で表され、以下のように並んでいます。

			(1,	1)
		(2,	1)	(2,	2)
	(3,	1)	(3,	2)	(3,	3)
(4,	1)	(4,	2)	(4,	3)	(4,	4)
:	:	:	:	:	:	:	:

つまり、この座標系では、上から k 段目には k 個の座標が並んでいます。

この座標系の、ある座標 (x,y) に対する重みを x と y の積で定義します。

A さんは、以下の問題を規則性を見つけることによって手で解こうとしています。

2 つの正整数 A,B (1≦A≦B≦10^6) が与えられるので、上から A 段目と上から B 段目の間、つまり A≦x≦B を満たす全ての座標 (x,y) の重みの総和を答えてください。ただし、答えは非常に大きくなる可能性があるのでその総和を 1,000,000,007(10^9+7) で割った余りを答えてください。

あなたの仕事は、A さんが頑張って導き出した答えの正誤を確かめるために、コンピューターの力を使い予め答えを自動計算しておくプログラムをつくることです。

入力

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

A
B

1 行目には、正の整数 A (1≦A≦10^6) が与えられる。
2 行目には、正の整数 B (A≦B≦10^6) が与えられる。

部分点

この問題には部分点が設定されている。

1≦A≦B≦2000 を満たすデータセット 1 に正解した場合は、20 点が与えられる。
全てのテストケースに正解した場合は、上記とは別に 80 点が与えられる。

出力

1 行目に、問題文中の座標系における A≦x≦B を満たす全ての座標 (x,y) の重みの総和を 1,000,000,007 で割った余りを出力せよ。出力の末尾に改行を入れること。

入力例1

2
3

出力例1

2 段目から 3 段目の間に含まれる座標は以下の 5 つです。


	(2,	1)	(2,	2)
(3,	1)	(3,	2)	(3,	3)

したがって、答えは 24(=2×1+2×2+3×1+3×2+3×3) となります。

入力例2

1
100

出力例2

12920425

入力例3

999999
999999

出力例3

500507028

1,000,000,007 で割った余りを取るのを忘れないでください。

B - How are you?

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社には N 人の社員がいます。社員 i (1 ≦ i ≦ N) は時刻 S_i に出社し、時刻 T_i に退社します。各社員は、自分がオフィスにいる間に出社してきた社員に対して "How are you?" と聞きます。すなわち、S_i < S_j < T_i を満たすとき、社員 i は社員 j に対して "How are you?" と聞きます。

あなたは、それぞれの社員が何人に対して "How are you?" と聞くかを計算することにしました。

入力

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

N
S_1 T_1
S_2 T_2
:
S_N T_N

1 行目には、社員の人数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
2 行目からの N 行には、社員の出社時刻と退社時刻の情報が与えられる。このうち i 行目には、2 つの整数 S_i, T_i (1 ≦ S_i < T_i ≦ N*2) が空白区切りで与えられる。これは、社員 i が時刻 S_i に出社し、時刻 T_i に退社することを表す。~~ただし、S_i = S_j または S_i = T_j を満たすような i,j (1 ≦ i < j ≦ N) は存在しないことが保証される。~~(16:18削除)
与えられる出社時刻と退社時刻は全て相異なる。つまり、S_1,…,S_N,T_1,…,T_N は全て異なる。(16:18追加)

部分点

この問題には部分点が設定されている。

N ≦ 2000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。

出力

出力は N 行からなる。このうち i 行目には、社員 i が "How are you?" と聞く社員の人数を表す 1 つの整数を出力せよ。出力の末尾にも改行を入れること。

入力例1

出力例1

この入力例では、

社員 1 は、社員 2 と社員 3 と社員 4 に対して "How are you?" と聞きます。
社員 2 は、社員 3 に対して "How are you?" と聞きます。
社員 3 は、社員 4 に対して "How are you?" と聞きます。
社員 4 は、誰にも "How are you?" と聞きません。

入力例2

出力例2

C - Palindrome Concatenation

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社の社員である A さんは、文字列処理のスキルを磨いています。A さんが今取り組んでいる問題は以下のようなものです。

いくつかの回文を繋げて文字列を作りたい。長さ i の回文を使うとコストが C_i かかる。このとき、文字列 S を作るために必要なコストの和の最小値を求めよ。ただし、回文とは前から読んでも後ろから読んでも同じであるような文字列である。また、同じ回文を 2 回以上使う場合でも、使った回数分だけのコストがかかることに注意せよ。

しかしながら、A さんはこの問題を解くことができませんでした。A さんのかわりにこの問題を解くプログラムを書いてください。

入力

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

N
S
C_1 C_2 ... C_N

1 行目には、文字列 S の長さを表す整数 N (1 ≦ N ≦ 5000) が与えられる。
2 行目には、文字列 S が与えられる。S は小文字アルファベット (a-z) のみからなる長さ N の文字列である。
3 行目には、回文を使うためのコストを表す N 個の整数が空白区切りで与えられる。このうち i (1 ≦ i ≦ N) 番目の整数 C_i (1 ≦ C_i ≦ 10^5) は、長さ i の回文を使うためのコストを表す。

部分点

この問題には部分点が設定されている。

N ≦ 200 を満たすデータセット 1 に正解した場合は、40 点が与えられる。
全てのテストケースに正解した場合は、上記とは別に 60 点が与えられる。

出力

いくつかの回文を繋げて文字列 S を作るときに必要なコストの和の最小値を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

9
indeednow
1 1 1 1 1 1 1 1 1

出力例1

この入力例では、i + ndeedn + o + w のように繋ぐとコストが 4 となります。

入力例2

9
indeednow
10 4 1 99 99 99 99 99 99

出力例2

この入力例では、i + ndeedn + o + w のように繋ぐとコストが 129 となりますが、

i + n + d + ee + d + n + o + w のように繋ぐとコストが 74 となります。

入力例3

12
abcbaabcbcbc
20 13 15 29 38 43 76 58 23 128 99999 100000

出力例3

D - Game on a Grid

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed社の社員である A さんは、以下のようなゲームで遊んでいます。

縦の長さが H、横の長さが W であるような H×W 個のマスからなる二次元盤面があります。この盤面の左から x (1≦x≦W) 、上から y (1≦y≦H) 番目にあるマスを、マス (x,y) と表します。

各マスには、それぞれ非負整数が書かれており、マス (x,y) に書かれている数は P_{(x,y)} です。

どの時点でも、A さんはこの盤面上のどこかに居ます。そして、以下のようなルールに基づいて行動をします。

今いるマスから上下左右に隣り合うマスへ移動することができる。ただし、盤面から出てしまうような移動はできない。
あるマスに初めて訪れたとき、そのマスに書かれている数だけの得点を得る。
今いるマスからまだ訪れていないマスに移動するとき、移動ボーナスとして、(今いるマスに書かれている数)×(次に訪れるマスに書かれている数) だけの得点を得る。
既に訪れているマスへ移動するときには、得点は生じない。

最初、 A さんはスタート地点であるマス (S_x,S_y) に訪れます。A さんは、ルールに基づいて自由に行動し、最終的にゴール地点であるマス (G_x,G_y) に訪れ行動を終えたいと思っています。一度ゴール地点に訪れた後、行動を終了せず、再びゴール地点に戻ってきてもよいことに注意してください。

A さんがルールに基づいて行動し達成することのできる最大の合計得点を出力してください。

入力

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

[重要]先ほどまで以下の入力形式で P(x,y) の形で表記するところを誤って P(y,x) の形で記述していました。記述を修正致しました。ご迷惑をおかけして誠に申し訳ございません(16:01)。

H W
S_x S_y
G_x G_y
P_{(1,1)} P_{(2,1)} … P_{(W,1)}
P_{(1,2)} P_{(2,2)} … P_{(W,2)}
:
P_{(1,H)} P_{(2,H)} … P_{(W,H)}

1 行目には、盤面の縦の長さと横の長さを表す 2 つの整数 H,W (1≦H,W≦100) が空白区切りで与えられる。
2 行目には、スタート地点のマスの座標を表す 2 つの整数 S_x,S_y (1≦S_x≦W,1≦S_y≦H) が空白区切りで与えられる。
3 行目には、ゴール地点のマスの座標を表す 2 つの整数 G_x,G_y (1≦G_x≦W,1≦G_y≦H) が空白区切りで与えられる。
4 行目から H 行には、各マスに書かれている数の情報が与えられる。そのうち i(1≦i≦H) 行目には、マス (1,i),マス (2,i) ,…,マス (W,i) に書かれている数を表す W 個の整数 P_{(1,i)},P_{(2,i)},…,P_{(W,i)} が空白区切りで与えられる。
任意の x,y(1≦x≦W,1≦y≦H) について、0≦P_{(x,y)}≦100 を満たす。

出力

1 行目に、 A さんがルールに基づいて行動し達成することのできる最大の合計得点を出力せよ。出力の末尾に改行を入れること。

入力例1

1 6
2 1
2 1
0 1 2 3 4 0

出力例1

スタート地点もゴール地点も左端から 2 番目のマスである盤面です。この盤面で得られる最大得点は 30 点であり、それを達成する行動の一例を示します。

スタート地点であるマス (2,1) に訪れる。このマスに書かれている数は 1 である。この時点での合計得点は 1 点である。
マス (3,1) に訪れる。このマスに書かれている数は 2 であり、移動ボーナスは 1×2 点である。したがって、この時点での合計得点は 5 点である。
マス (4,1) に訪れる。このマスに書かれている数は 3 であり、移動ボーナスは 2×3 点である。したがって、この時点での合計得点は 14 点である。
マス (5,1) に訪れる。この時点での合計得点は 30 点である。
マス (4,1) に訪れる。既に訪れたマス同士の移動なので得点の変化はない。
マス (3,1) に訪れる。同様に得点の変化はない。
マス (2,1) に訪れ、行動を終える。得点の変化はない。最終的な合計得点は 30 点である。

入力例2

出力例2

入力例3

10 10
5 2
6 2
31 0 60 19 87 98 35 68 21 41
21 46 85 72 51 13 0 49 19 25
79 82 46 65 30 99 29 44 99 8
39 48 70 99 82 32 25 49 32 54
81 20 57 70 5 40 88 97 56 17
69 54 35 98 7 38 59 91 80 34
28 13 14 28 60 26 82 10 17 100
29 0 27 43 45 88 88 92 21 67
62 33 35 22 26 68 74 95 86 79
68 18 83 72 85 21 72 34 57 77

出力例3

E - Line up!

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社の N 人の社員が左から右に向かって一列に並んでいます。各社員には身長が定まっており、自分より左に並んでいる全ての社員よりも身長が高い場合に限り、列の左側から見たときに顔が見えます。

社員達は既に並んでいますが、左右に隣接する 2 人の社員どうしは、それらの位置を入れ替わるという行動を自由な順番で何度でも行うことができます。位置を入れ替わるときは、2 者の身長が低い方の身長の値だけのコストがかかります。

合計コストは各入れ替わりにかかるコストの総和として定義されます。

今、A さんは、列の左側から見たときに N 人の社員全員の顔が見えるように並んで欲しいと思っており、それを達成するように並んだときにのみ A さんは満足します。

あなたの仕事は、列における社員の身長が与えられるので、A さんが満足するために必要な最小の合計コストを答えることです。ただし、どのように並んでも A さんが満足しない場合もあります。その場合はその旨を報告してください。

入力

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

N
H_1 H_2 … H_N

1 行目には、並んでいる社員の人数を表す整数 N (1≦N≦10^5) が与えられる。
2 行目には、列に並んでいる社員の身長を表す N 個の整数が空白区切りで与えられる。そのうち i(1≦i≦N) 番目には、列において左から i 番目の位置にいる社員の身長を表す整数 H_i (1≦H_i≦10^8) が与えられる。

部分点

この問題には部分点が設定されている。

1≦N≦1000 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。

出力

1 行目に、A さんが満足するために必要な最小の合計コストを出力せよ。ただし、どのように並んでも A さんが満足しない場合は -1 を出力せよ。出力の末尾に改行を入れること。

入力例1

4
4 1 3 2

出力例1

左から順番に身長が 1,2,3,4 となるように並ぶことで、列の左側から見たときに全員の顔を見ることができ、A さんは満足します。この並びを達成するために必要な最小の合計コストは 8 で、以下のように入れ替わることによって達成できます。

最初に、身長 4 の人と身長 1 の人が入れ替わります。この行動にかかるコストは 1 で、直後の並びは 1,4,3,2 です。
次に、身長 4 の人と身長 3 の人が入れ替わります。この行動にかかるコストは 3 で、直後の並びは 1,3,4,2 です。
次に、身長 4 の人と身長 2 の人が入れ替わります。この行動にかかるコストは 2 で、直後の並びは 1,3,2,4 です。
最後に、身長 3 の人と身長 2 の人が入れ替わります。この行動にかかるコストは 2 で、直後の並びは 1,2,3,4 です。

入力例2

5
1 1 2 2 3

出力例2

-1

どのように並んだとしても、同じ身長の人同士の顔を同時に見ることはできません。したがって -1 を出力しなければなりません。