A - Two Abbreviations
はじめに
競技プログラミング、AtCoder Grand Contest 028
A - Two Abbreviations
言語はC#
何かあればTwitter→@pirorirori_n712まで
問題
問題文
長さ Nの文字列 Sと長さ Mの文字列 Tが与えられます。 どちらの文字列も、英小文字からなります。 文字列 Xは、以下の条件をすべて満たす時、よい文字列と呼ばれます。 ・Xの長さを Lとした時、Lは Nと Mのどちらでも割り切れる ・Xの「1,L/N+1, 2×L/N+1, ...(N−1)×L/N+1」番目の文字を並べ替えることなく連結すると Sになる ・Xの「1,L/M+1,2×L/M+1,...(M−1)×L/M+1」番目の文字を並べ替えることなく連結するとTになる よい文字列が存在するか判定し、存在するならば、その中で最短のものの長さを求めてください。
制約
1≤N,M≤10^5 S, Tは英小文字からなる。 |S|=N |T|=M
入力
N M S T
出力
よい文字列が存在しないならば、-1 と出力せよ。 存在するならば、その中で最短のものの長さを出力せよ。
解き方
まず、問題文の「作成される文字列Xの長さを Lとした時、
Lは Nと Mのどちらでも割り切れる」というよい文字列の条件から
よい文字列は必ず「NとMのどちらでも割り切れる」、
すなわち「NとMの最小公倍数の倍数」であるということが分かる。
次に、2つ目3つ目の条件について考える。
条件は以下である。
・Xの「1,L/N+1, 2×L/N+1, ...(N−1)×L/N+1」番目の文字を並べ替えることなく連結すると Sになる ・Xの「1,L/M+1,2×L/M+1,...(M−1)×L/M+1」番目の文字を並べ替えることなく連結するとTになる
このままだと意味がよく分からないので、入力例にあてはめて考えてみる。
入力例1
3 2 acp ae
出力例1
6
ここから、Lは「6」、Nは「3」、Mは「2」、Sは「acp」、Tは「ae」である。
これを条件に当てはめると以下のようになる。
・Xの「1,6/3+1, 2×6/3+1, ...(6−1)×6/3+1」番目の文字を並べ替えることなく連結すると acpになる ・Xの「1,6/2+1, 2×6/2+1, ...(6−1)×6/2+1」番目の文字を並べ替えることなく連結すると aeになる
Xの長さが6（L=6）であることを考慮して、
計算式の中を整理すると以下のようになる。
・Xの「1,3,5」番目の文字を並べ替えることなく連結すると acpになる ・Xの「1,4」番目の文字を並べ替えることなく連結すると aeになる
つまり、この条件は
よい文字列を作ろうとすると
与えられた等差数列で求められるXのインデックスによって
Xを構成するために文字を置く場所が制限されることを示す。
上の条件に沿って文字を並べると以下のようになる。
1 2 3 4 5 6 S a - c - p - T a - - e - -
また、
ここで注目するポイントは
上の条件を見るとインデックスの1番が
両者とも「a」に指定されているということである。
・Xの「1,3,5」番目の文字を並べ替えることなく連結すると acpになる
・Xの「1,4」番目の文字を並べ替えることなく連結すると aeになる
また、
よい文字列の条件より
この「1番初めの文字の指定」は例題1に限ったことではない。
・Xの「1,L/N+1, 2×L/N+1, ...(N−1)×L/N+1」番目の文字を並べ替えることなく連結すると Sになる
・Xの「1,L/M+1,2×L/M+1,...(M−1)×L/M+1」番目の文字を並べ替えることなく連結するとTになる
そのため、
入力で与えらえる文字列、SとTの一番初めの文字が違う時点で
その文字列はよい文字列を作ることはできなくなる。
さらに、他の例題にも数字を当てはめてみる。
入力２
6 3 abcdef abc
出力２
-1
与えられる文字列の長さが6と3なので
Lを最小公倍数の6としてみる。
よい文字列の条件に当てはめて、計算式の中を整理すると以下のようになる。
・Xの「1,2,3…6」番目の文字を並べ替えることなく連結すると abcdefになる ・Xの「1,3,5」番目の文字を並べ替えることなく連結すると abcになる
この条件から文字列を作成すると、文字列を作成することができないことが分かる。
1 2 3 4 5 6 S a b c d e f T a - b - c -
ここで、
よい文字列の長さは
最小公倍数の倍数であることが分かっているので、
6の倍、12でできるかどうかを考えてみる。
Lを最小公倍数6の倍、12としてみる。
よい文字列の条件に当てはめて、計算式の中を整理すると以下のようになる。
・Xの「1,3,5…11」番目の文字を並べ替えることなく連結すると abcdefになる ・Xの「1,5,11」番目の文字を並べ替えることなく連結すると abcになる
この条件から文字列を作成すると、文字列を作成することができないことが分かる。
1 2 3 4 5 6 7 8 9 10 11 12 S a - b - c - d - e - f - T a - - - b - - - c - - -
ここで注目したいのは、
先程かぶった場所が同じようにかぶっているということである。
すなわち、最小公倍数でかぶるインデックスは
最小公倍数の倍数でも同じようにかぶることになる。
そのため、最小公倍数で同じインデックスに
異なる文字が指定されていた場合は
よい文字列を作ることはできないと言える。
最後に出力3を条件にあてはめて考えてみる。
入力3
15 9 dnsusrayukuaiia dujrunuma
出力3
45
よい文字列の条件に当てはめて、計算式の中を整理すると以下のようになる。
・Xの「1,4,7…43」番目の文字を並べ替えることなく連結すると abcdefになる ・Xの「1,6,11…41」番目の文字を並べ替えることなく連結すると abcになる
ここでは、上の条件の等差数列について考えてみる。
それぞれの条件が、文字を指定したいインデックスを並べると以下のようになる。
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 1 6 11 16 21 26 31 36 41
ここから、重なっているものを抜き出すと「1,16,31」である。
また、ここで条件の等差数列に注目すると
・Sの文字列に関わる条件は、差が「3」の等差数列
・Tの文字列に関わる条件は、差が「5」の等差数列
なので、この2つの等差数列の差の最小公倍数は「15」
そして先ほどの重なっていたインデックスをみると
確かに、「15」ごとに指定したいインデックスがかぶっていることが分かる。
ここから、重なる文字は
「条件の等差数列の各差の最小公倍数ごとに現れる」ということが分かる。
最後にもう一つ、
この「条件の等差数列の各差の最小公倍数ごとに現れる」という条件だが
これを確かめなくてもよいパターンがある。
それは、入力1のような最小公倍数がNMそのままのパターンである。
このパターンは重なる部分が一番初めの文字のみなので
中身については確かめる必要がない。
今までで出てきた、
よい文字列かどうかを確かめるために必要なことを整理すると
以下のようになる。
・よい文字列の長さLはSとTの最小公倍数である。
・SとTの一番初めの文字が違うと、よい文字列を作ることはできない。
・重なる文字は、条件の等差数列の各差の最小公倍数ごとに現れる
（ただし、NMが両者の最小公倍数そのままの場合はこの条件を確かめる必要がない）
以上をもとにして、コードを書くと以下のようになる。
コード例
using System;
using System.Linq;
class Amondai
{
static void Main()
{
//int型だとはみ出すのでlong型
var num = Console.ReadLine().Split(' ').Select(x => Int64.Parse(x)).ToArray();
//大きいほうをmax、小さいほうをminに入れる
var max = num[0] < num[1] ? num[1] : num[0];
var min = max == num[0] ? num[1] : num[0];
//答え用の変数を用意
var ans = -1L;
//それぞれの文字列（SとT）
var line1 = Console.ReadLine().ToCharArray();
var line2 = Console.ReadLine().ToCharArray();
//初めの文字が違った場合はよい文字列を作れない
if (line1[0] != line2[0])
{
Console.WriteLine(ans);
return;
}
//最小公倍数を答えに代入
ans = GetS(max, min);
//最小公倍数がNとMをかけた数そのままであれば
//重なる文字は初めだけなので
//ここにたどり着いた時点で最小公倍数がよい文字列の長さであると言える
//そのため、それ以外をみていく
if (max * min != ans)
{
//kankaku1,kankaku2はそれぞれの等差数列の差
var kankaku1 = ans / num[0];
var kankaku2 = ans / num[1];
//等差数列の差の最小公倍数
var kankaku = GetS(kankaku1, kankaku2);
//等差数列の差の最小公倍数ごとに重なる文字が現れるので
//等差数列の差の最小公倍数ごとに文字を確かめる
for (long i = kankaku; i < ans; i += kankaku)
{
//異なる文字列があった場合、よい文字列はできない
if (line1[i / kankaku1] != line2[i / kankaku2] )
{
ans = -1;
break;
}
}
}
Console.WriteLine(ans);
}
//最小公倍数を求めるメソッド
//ユークリッドの互除法を使います
static long GetS(long max, long min)
{
var r = 0L;
var a = max;
var b = min;
while ((r = max % min) != 0)
{
max = min;
min = r;
}
return a * b / min;
}
}
最小公倍数の求め方
入力した2つの自然数の最小公倍数を求める
