/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
1,2,\ldots,N の番号が付けられた N 人の人が居ます。i\neq j に対して、人 i と人 j の親密度は A_{i,j} です。
N 人それぞれに対して、部屋 X, 部屋 Y のどちらか一方を割り当てます。N 人はそれぞれ割り当てられた部屋に移動します。誰も居ない部屋が存在しても構いません。
人 i が 良い状態 であるとは、以下を満たすことと定義します。
(人 i と同じ部屋に居る人全員の、人 i との親密度の和) \geq (人 i と異なる部屋に居る人全員の、人 i との親密度の和)
N 人全員が良い状態になるような部屋の割り当てを 1 つ出力してください。
なお、そのような割り当ては必ず存在することが証明できます。
制約
- 2 \leq N \leq 50
- -50 \leq A_{i,j} \leq 50
- A_{i,j} = A_{j,i}
- A_{i,i}=0
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
出力
条件を満たす割り当てを 1 つ出力してください。答えが複数存在する場合はどれを出力しても構いません。
割り当ては長さ N の文字列 S で表し、人 i を部屋 X に割り当てる場合は S の i 文字目を X, 部屋 Y に割り当てる場合は S の i 文字目を Y にしてください。
入力例 1
4 0 4 -2 -1 4 0 -3 -5 -2 -3 0 2 -1 -5 2 0
出力例 1
XXYY
人 1,2 を部屋 X、人 3,4 を部屋 Y に割り当てるとします。
人 1 は、同じ部屋に居る人(人 2)との親密度の和は 4、異なる部屋に居る人(人 3 と人 4)との親密度の和は (-2)+(-1)=-3 であるため、良い状態です。
他の人も全て良い状態であるため、この割り当ては条件を満たします。
他に YYXX を出力した場合も正解となります。
入力例 2
3 0 0 0 0 0 0 0 0 0
出力例 2
XXX
誰も居ない部屋が存在しても構いません。
Score : 600 points
Problem Statement
There are N people numbered 1,2,\ldots,N. For i\neq j, the intimacy between persons i and j is A_{i,j}.
For each of the N people, assign room X or room Y. Each of the N people moves to their assigned room. It is acceptable if there is an empty room.
Person i is in a good state if the following is satisfied:
(Sum of intimacy with person i of all people in the same room as person i) \geq (Sum of intimacy with person i of all people in a different room from person i).
Output one assignment of rooms such that all N people are in a good state.
It can be proved that such an assignment always exists.
Constraints
- 2 \leq N \leq 50
- -50 \leq A_{i,j} \leq 50
- A_{i,j} = A_{j,i}
- A_{i,i}=0
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
Output
Output one assignment that satisfies the condition. If there are multiple solutions, you may output any of them.
Represent the assignment by a string S of length N. If person i is assigned to room X, the i-th character of S should be X; if assigned to room Y, the i-th character of S should be Y.
Sample Input 1
4 0 4 -2 -1 4 0 -3 -5 -2 -3 0 2 -1 -5 2 0
Sample Output 1
XXYY
Suppose persons 1,2 are assigned to room X and persons 3,4 are assigned to room Y.
For person 1, the sum of intimacy with people in the same room (person 2) is 4, and the sum of intimacy with people in different rooms (persons 3 and 4) is (-2)+(-1)=-3, so they are in a good state.
All other people are also in a good state, so this assignment satisfies the condition.
Outputting YYXX is also correct.
Sample Input 2
3 0 0 0 0 0 0 0 0 0
Sample Output 2
XXX
It is acceptable if there is an empty room.