問題一覧 > 通常問題

No.2745 String Swap Battle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 35
作問者 : Nzt3Nzt3 / テスター : ponjuiceponjuice kenken714kenken714 cho435cho435 tassei903tassei903
4 ProblemId : 10840 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-26 12:59:18

問題文

NN 人のプレイヤーがいます。初め、人 ii は文字列 SiS_i を持っています。それぞれのプレイヤーは誰がどのような文字列を持っているかを全て知っています。

次の2つの段階からなるゲームを行います。

段階1
  • それぞれのプレイヤーが好きな正整数を宣言する
  • 宣言された正整数のうち最小のものを KK とする
段階2
  • それぞれのプレイヤー ii が丁度 KK 回次の操作を行う
    • 自分が持っている文字列 SiS_i の異なる位置の2文字を選択し、入れ替える

最終的に作られた文字列のうち、辞書順で最小の文字列を持っていた人全員が勝ちです。また、勝者は勝者の人数を XX として N+1XN+1-X 点が得られます。

全員が自身の得点を最大化する戦略をとったとき、全員の得点を求めてください。

制約

  • N2N \ge 2
  • 2Si1052 \le |S_i| \le 10^5
  • Si2×105\sum |S_i| \le 2 \times 10^5
  • SiS_iは英小文字のみからなる

入力

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

NN
S1S_1
\vdots
SNS_N

出力

NN 行出力せよ。 ii 行目には全員が自身の得点を最大化する戦略をとったときのプレイヤー ii の得点を出力せよ。

サンプル

サンプル1
入力
3
ac
re
wa
出力
0
0
3

全員が最適な戦略を取ると、プレイヤー 33 のみが勝利します。このときプレイヤー 33N+11=3N+1-1=3 点得られます。

サンプル2
入力
4
abc
cba
bac
abc
出力
0
3
3
0

サンプル3
入力
5
apple
banana
cabbage
dragonfruit
egg
出力
0
0
5
0
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。