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

A - Table Tennis

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社のオフィスには卓球台がある。
n 人の社員が卓球のダブルスで試合をすることにした。
2 人ずつのペアを作ることにしたが、みんなが楽しめるようにできるだけ各ペアの強さを均等にしたいと考えている。
i 番目の人の卓球の強さは a_i で表され、ペアの強さは 2 人の強さの和で決まる。
一番強いペアと一番弱いペアの強さの差が最小になるようにペアを作ったときに、その差はいくつになるだろうか。

入力

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

n
a_1 a_2 ... a_n

1 行目には、社員の数を表す整数 n (4 \leq n \leq 100, n は偶数) が与えられる。
2 行目には、社員の卓球の強さを表す整数 a_i (1 \leq a_i \leq 1{,}000) がスペース区切りで n 個与えられる。

出力

求める値を一行で出力せよ。

入力例1

4
1 3 4 10

出力例1

{(1,3), (4,10)}, {(1,4), (3, 10)}, {(1,10), (3,4)} の 3 通りのチーム分けが考えられる。
このうち、もっともペアの強さの差が小さいものは {(1,10), (3,4)} であり、その差は 4 である

入力例2

4
1 3 4 4

出力例2

B - Office Ninja

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社のオフィスは正六角形を組み合わせることによって構成されている。
新入社員の A 君は運動が得意なため、正六角形を区切っている仕切りを飛び越えて移動することが可能である。
いま、A 君は地点 s から地点 t へと急いで移動する必要がある。
しかし、s から t へ移動するために、正六角形のスペースに入った場合、そこにいる人に "How are you?" と聞かれるため、時間がかかってしまう。
しかも、一つの正六角形のスペースに n 人の人がいた場合、A 君は n 回 "How are you?" と聞かれてしまう。
A 君が s から t へ移動する際、最低で何回 "How are you?" と聞かれるだろうか。
ただし、地点 s と t では、"How are you?" と聞かれることがないものとする。

入力

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

R C
a_{11} a_{12} ... a_{1C}
a_{21} a_{22} ... a_{2C}
...
a_{R1} a_{R2} ... a_{RC}

1 行目には、オフィスを構成する正六角形のスペースの行数 R と列数 C ( 1 \leq R,C \leq 100, R \times C \geq 2) が与えられる。
2 行目から続く R 行には、オフィスのそれぞれの正六角形にいる人の数の情報 a_{ij} が与えられる。
a_{ij} は s, t, 0 から 9 のいずれかからなる。
全ての a_{ij} のうち、ちょうど 1 つが s であり、ちょうど 1 つが t であることが保証される。
a_{ij} と実際に与えられる値の対応は下図を参考にせよ。

出力

求める値を一行で出力せよ。

入力例1

出力例1

入力例2

出力例2

C - Optimal Recommendations

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

求職者と求人会社のマッチングを手助けしている Indeed 社は、求職者に最適な求人を提示するサービスを開発することにした。
Indeed 社のデータベースには、独自テストで得られた、各求職者の技術力、語学力、コミュニケーション力が保存されている。
またそのデータベースには、各求人会社が応募条件として要求した、それら 3 つの力の最低限必要な値とその会社の年収も保存されている。
データベースのデータがすべて与えられるので、各求職者ごとに、その人が応募可能な会社の中で一番高い年収を示しなさい。

入力

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

N M
a_1 b_1 c_1 w_1
...
a_N b_N c_N w_N
x_1 y_1 z_1
...
x_M y_M z_M

1 行目には、求人会社数を表す整数 N (1 \leq N \leq 50{,}000)、求職者数を表す整数 M (1 \leq M \leq 50{,}000) が与えられる。
2 行目から続く N 行には、i 番目の求人会社が最低限必要としている技術力、語学力、コミュニケーション力を表す整数 a_i, b_i, c_i (0 \leq a_i, b_i, c_i \leq 100) とその会社の年収を表す整数 w_i (1 \leq w_i \leq 1{,}000{,}000{,}000 ) が与えられる。
続く M 行には、i 番目の求職者の技術力、語学力、コミュニケーション力を表す整数 x_i, y_i, z_i (0 \leq x_i, y_i, z_i \leq 100) が与えられる。

出力

それぞれの求職者に対して、その求職者が応募可能な会社の中で、最も年収が高い会社の年収を一行で出力せよ。

応募可能な会社が存在しない場合は、代わりに 0 を出力せよ。

入力例1

3 6
1 2 3 3
3 3 3 6
4 4 4 8
3 4 3
4 4 4
100 100 1
2 3 4
0 0 0
100 100 100

出力例1

D - Longest Path

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社は、Speed と Price を重視している。
Price を重視しているため、世界中に存在する Indeed 社の開発拠点は次のようなネットワークでつながれている。

一部の通信路は単方向通信しかできない。
全ての通信路の向きを無視した場合、任意の 2 拠点間において、通信路をたどって行けるようなパスがちょうど一つ存在する。

以上の条件を満たすグラフは木構造になる。
Speedも重視しているため、社員らは通信できる拠点のなかで最も中継する拠点数が多い 2 拠点を知りたがっている。
そのような 2 拠点間において、中継する拠点数はいくつになるだろうか。

入力

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

n
a_1 b_1 t_1
a_2 b_2 t_2
...
a_{n-1} b_{n-1} t_{n-1}

1 行目には、拠点の数 n ( 2 \leq n \leq 100{,}000) が与えられる。
2 行目から続く n-1 行には、拠点間を繋ぐ通信路の情報が与えられる。
1 \leq a_i, b_i \leq n, a_i \neq b_i
t_i = 1 のとき、a_i から b_i へと単方向通信に使える通信路が存在することを意味する。
t_i = 2 のとき、a_i と b_i の間に双方向通信に使える通信路が存在することを意味する。

出力

求める値を一行で出力せよ。

入力例1

出力例1

入力例2

出力例2

E - Page Rank

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある会社には n 人の社員がいる。
この会社では座席が一直線上に並んでおり、この直線の端から順に社員番号が割り当てられている。
この会社では社員の能力を測定するために、以下に述べる方法を使用している。

まず、すべての社員は優秀だと思っている社員のリストを会社に提出する。
i 番目の社員が提出したリストを N(i) とする。
遠くの席にいる社員のことはよくわからないので、N(i) には座席が机 10 個分以上離れている社員が含まれていることはない。
(任意の x \in N(i) について |i - x| < 10 が成り立つ)
全員分のリストを集めたら、社員を頂点とし優秀だと思っている関係を有向辺とするグラフを構築する。
そして、このグラフ上での Page Rank を社員の能力とする。
i 番目の社員の Page Rank を PR(i)、i 番目の社員を優秀だと思っている社員の集合を M(i) とすると、Page Rank は次の条件式を満たす。

この会社のために Page Rank を求めるプログラムを書くのがあなたの仕事である。

入力

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

n m
a_1 b_1
...
a_m b_m

1 行目には社員数を表す整数 n (1 \leq n \leq 10{,}000)、ある社員が別の社員を優秀だと思っている関係の個数を表す整数 m (1 \leq m \leq 10{,}000) が与えられる。
続く m 行には、2 つの整数 a_i, b_i (1 \leq a_i, b_i \leq n, |a_i - b_i| < 10) が含まれており、これは a_i 番目の社員は b 番目の社員を優秀だと思っていることを表す。

出力

それぞれの社員に対する Page Rank の値を一行で出力せよ。

相対誤差または絶対誤差が 10^{-6} 以下ならば正解とみなされる。

入力例1

出力例1

1
1
1

入力例2

出力例2

1.473684210526316
0.7631578947368423
0.7631578947368423

この場合は 3 人の社員がいる。
1 番目の社員は 2 番目の社員と 3 番目の社員を優秀だと思っている。
2 番目の社員は 1 番目の社員を優秀だと思っている。
3 番目の社員は 1 番目の社員を優秀だと思っている。
したがって、各社員の Page Rank は以下の条件をすべて満たす。
PR(1) = 0.1 + 0.9 (\frac{PR(2)}{1} + \frac{PR(3)}{1})
PR(2) = 0.1 + 0.9 (\frac{PR(1)}{2})
PR(3) = 0.1 + 0.9 (\frac{PR(1)}{2})

F - 就職活動

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Indeed 社では、す社、ぬ社、け社の三社への就職活動について調査をすることにした。
X 人の就職希望者にす、ぬ、け各社に就職したいかアンケートをとり、3X 組の会社と人のペアに対し、各就職希望者がす、ぬ、け各社に就職したいかどうかを集計した表を作成した。
(このような表は 2^{3X} 通り考えられる。)
す社、ぬ社、け社にはそれぞれ最大で S 人、N 人、K 人までの人が入社できる。
2^{3X} 通りの表のうち、全ての人が希望する就職先に就職できるようなものは何通りあるだろうか。
その値を 1{,}000{,}000{,}007 で割った余りを求めよ。

入力

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

X S N K

1 行目には、問題文中で与えられた 4 つの整数 X, S, N, K (1 \leq S,N,K \leq X \leq 150) が空白区切りで与えられる。

部分点

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

1 \leq S,N,K \leq X \leq 12 であるようなデータセットに正解した場合は、25 点が与えられる。
全てのテストケースに正解した場合は、上記とは別に 75 点が与えられる。

出力

求める値を一行で出力せよ。

入力例1

1 1 1 1

出力例1

一人の就職希望者がいるため、就職希望の表は 8 通り考えられる。
このうち、どの会社も希望しない場合は就職希望先に就職できなかったものと考える。
したがって、全部で 7 通りとなる。

入力例2

2 2 1 2

出力例2

入力例3

5 4 3 2

出力例3

入力例4

15 12 9 6

出力例4

667797496