No.3230 Mutual Corresponding System
タグ : / 解いたユーザー数 30
作問者 :
ジュ・ビオレ・グレイス
/ テスター :
👑 
p-adic
問題文
$N$ 人の人間 $H_1, \dots, H_N$ が互いに手紙を $M$ 通出し合います。
各人間 $H_n$ は $T_n$ 日目に他の全員宛に一斉に $1$ 通目の手紙を送りつけます。
各人間 $H_n$ は以下の条件が満たされたその日に、他の全員宛に一斉に $m+1$ 通目の手紙を送りつけます ($m \geq 1$):
- $H_n$ は $m$ 通目の手紙を前日または当日までに送りつけている
- $H_n$ は他の人間 $H_{n'} \ (n' \neq n)$ たち全員からの $m$ 通目の手紙が届いている
各人間 $H_n$ に他の全員からの $M$ 通目の手紙が届くのは何日目かを $n = 1, \dots, N$ について求めてください。
入力
$N\ M$
$T_1 \ \dots \ T_N$
$A_{1, 1} \ A_{1, 2} \ \dots \ A_{1, N}$
$\vdots$
$A_{N, 1} \ A_{N, 2} \ \dots \ A_{N, N}$
$1 \leq N \leq 10^2,$
$2 \leq M \leq 10^{15},$
$0 \leq T_n \leq 10^3,$
$0 \leq A_{i, j} \leq 10^3,$
$A_{i, i} = 0$
は全て整数です。問題では $A_{i, i}$ は使いませんが、入力形式を簡単にするため便宜上与えています。答えは全て $2^{63}$ 未満になることが保証されています。
出力
各人間 $H_n$ に他の全員からの $M$ 通目の手紙が届くのは何日目かを $n = 1, \dots, N$ についてそれぞれ半角スペース一字で区切って出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 2 0 4 10 0 2 3 9 0 5 1 7 0
出力
26 17 22
$H_1$ の手元に $H_2$ の $1$ 通目の手紙が届くのは $4 + 9 = 13$ 日目、$H_3$ の $1$ 通目の手紙が届くのは $10 + 1 = 11$ 日目です。そのため $H_1$ は $13$ 日目に $2$ 通目の手紙を送りつけます。
$H_2$ の手元に $H_1$ の $1$ 通目の手紙が届くのは $0 + 2 = 2\ $ 日目、$H_3$ の $1$ 通目の手紙が届くのは $10 + 7 = 17$ 日目です。そのため $H_2$ は $17$ 日目に $2$ 通目の手紙を送りつけます。
$H_3$ の手元に $H_1$ の $1$ 通目の手紙が届くのは $0 + 3 = 3\ $ 日目、$H_2$ の $1$ 通目の手紙が届くのは $4 + 5 = 9\ $ 日目です。そのため $H_3$ は $10$ 日目に $2$ 通目の手紙を送りつけます（自分が $1$ 通目を送りつけるまでは $2$ 通目は送りつけないことに注意）。
$H_1$ から $13$ 日目に送られた $2$ 通目の手紙は、$13 + 2 = 15$ 日目に $H_2$ の手元に届き、$13 + 3 = 16$ 日目に $H_3$ の手元に届きます。
$H_2$ から $17$ 日目に送られた $2$ 通目の手紙は、$17 + 9 = 26$ 日目に $H_1$ の手元に届き、$17 + 5 = 22$ 日目に $H_3$ の手元に届きます。
$H_3$ から $10$ 日目に送られた $2$ 通目の手紙は、$10 + 1 = 11$ 日目に $H_1$ の手元に届き、$10 + 7 = 17$ 日目に $H_2$ の手元に届きます。
したがって、$H_1, H_2, H_3$ に $2$ 通目の手紙が全員から届くのはそれぞれ $26, 17, 22$ 日目 です。
サンプル2
入力
3 3 2 8 9 0 0 0 0 0 0 0 0 0
出力
9 9 9
$H_1$ の手元に $H_2$ の $1$ 通目の手紙が届くのは $8 + 0 = 8$ 日目、$H_3$ の $1$ 通目の手紙が届くのは $9 + 0 = 9$ 日目です。そのため $H_1$ は $9$ 日目に $2$ 通目の手紙を送りつけます。
$H_2$ の手元に $H_1$ の $1$ 通目の手紙が届くのは $2 + 0 = 2$ 日目、$H_3$ の $1$ 通目の手紙が届くのは $9 + 0 = 9$ 日目です。そのため $H_2$ は $9$ 日目に $2$ 通目の手紙を送りつけます。
$H_3$ の手元に $H_1$ の $1$ 通目の手紙が届くのは $2 + 0 = 2$ 日目、$H_2$ の $1$ 通目の手紙が届くのは $8 + 0 = 8$ 日目です。そのため $H_3$ は $9$ 日目に $2$ 通目の手紙を送りつけます（自分が $1$ 通目を送りつけるまでは $2$ 通目は送りつけないことに注意）。
$H_1$ から $9$ 日目に送られた $2$ 通目の手紙は、$9 + 0 = 9$ 日目に $H_2$ の手元に届き、$9 + 0 = 9$ 日目に $H_3$ の手元に届きます。
$H_2$ から $9$ 日目に送られた $2$ 通目の手紙は、$9 + 0 = 9$ 日目に $H_1$ の手元に届き、$9 + 0 = 9$ 日目に $H_3$ の手元に届きます。
$H_3$ から $9$ 日目に送られた $2$ 通目の手紙は、$9 + 0$ 日目に $H_1$ の手元に届き、$9 + 0$ 日目に $H_2$ の手元に届きます。
$H_1, H_2, H_3$ たちが $9$ 日目に送りつけた $2$ 通目の手紙は $9$ 日目にそれぞれに届き、$3$ 通目を $9$ 日目に送りつけ、$3$ 通目の手紙は $9$ 日目にそれぞれに届きます。
同日に複数送りつけることもあることに注意してください。
サンプル3
入力
4 3 2 8 9 13 0 81 72 13 18 0 91 73 89 26 0 42 44 43 29 0
出力
263 269 270 252
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。