差分

このページの2つのバージョン間の差分を表示します。

この比較画面にリンクする

strsrt [2020/04/13 10:23] (現在)
行 1: 行 1:
 +# Sorting String
 +## 問題
 +ともに長さ$N$の文字列$S$と文字列$T$が与えられます。
 +$S$に対して **隣接する文字を入れ替える** という操作を$K+1000000007n (n \in \mathbb N)$回行ったとき、
 +(すなわち$\text{(操作回数)} \equiv K \mod{10^9+7}$)
 +$T$と等しくすることができるかを判定してください
 +
 +## 制約
 +$2 \le N \le 10^6$
 +$0 \le K < 10^9+7$
 +$|S| = |T| = N$
 +$S$,$T$は英小文字のみで構成される文字列である
 +($|S|$は$S$の長さ)
 +
 +### 小課題
 +本来の制約に加えて次の制約を満たすテストケースに正解すると得点の20%を与えられる。
 +$2 \le N \le 10$
 +
 +## 入力
 +$N$ $K$
 +$S$
 +$T$
 +
 +## 出力
 +問題の操作が可能なら`Yes`、そうでなければ`No`を出力してください。
 +
 +## 入出力例
 +### 例1
 +#### 入力
 +```
 +5 1
 +abcde
 +abced
 +```
 +
 +#### 出力
 +```
 +Yes
 +```
 +
 +1回の操作で実現可能です。
 +
 +### 例2
 +#### 入力
 +```
 +3 5
 +abc
 +cba
 +```
 +
 +#### 出力
 +```
 +Yes
 +```
 +
 +`abc`→`acb`→`cab`→`cba`→`cab`→`cba`と5回で操作を行うことができました。
 +
 +### 例3
 +#### 入力
 +```
 +3 10
 +abc
 +def
 +```
 +
 +#### 出力
 +```
 +No
 +```
 +
 +含む文字が違うので実現不可能です。
 +
 +### 例4
 +#### 入力
 +```
 +10 5
 +abcdefghij
 +badcfehgji
 +```
 +
 +#### 出力
 +```
 +Yes
 +```
 +
 +このサンプルは小課題の制約を満たしません。
  
最終更新: 2020/04/13 10:23