AGC028 A - Two Abbreviations

atcoder.jp

分数が出てくるととたんに難しく感じる。問題文を理解するために例も見ていくのが良さそう。

…ちなみに自分はWA出まくったので諦めて解説とか解答例見てACしました（勉強になったので良し）。今回学んだのは

• やはりGCD、LCMの知識は必要
• 紙考察は大切

の二つです。

自分なりの解説

入出力例1から

「accept」を例にして図にすると、

文字列Xを作るためにはこの条件をクリアしていないといけないっぽい。赤と青が重なってない所(c,e,p)は文字の中身の違いにかかわらず矛盾は起きないので、重なっている所だけ(a)文字が同じかどうかを確認していくとよさそう。

ちなみに、L=6だけで大丈夫か？と思う人もいるかもしれないのでL=12の時の図。

間に一つずつ空白が入るだけなので、L=6の場合を考えるだけでよさそうです。はい。

入出力例3から

重なるところだけ確認していけばいいのですが、どこが重なるのかと。

dnsusrayukuaiiaの方は45÷15=3つずつ配置され、
dujrunumaの方は45÷9=5つずつ配置されます。つまり重なるのは
lcm(3,5)=15つごとです。
15つ先に進むためには赤は15÷3=5文字使い、一方青の方は
15つ先に進むために15÷5=3文字使っています。つまり、
dnsusrayukuaiiaの方は5文字おき、
dujrunumaの方は3文字おきに同じかどうか確認すればいいです。
（うーん、わかりにくい）

式で表すと、赤の方は

ずつ確認すればいいです。
ここで、とは互いに素なので(たぶん)、は単純に掛けてになり、
になり、
なので、
になります。

つまり、赤の方はgcd(n,m)をgとすると、回おきに確認すればいいです。
同様に、青の方も回おきに確認すればいいです。

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

int main() {
  ll n, m;
  cin >> n >> m;
  string s, t;
  cin >> s >> t;
  ll g = gcd(n, m);

  string a, b;
  for (int i = 0; i < n; i += n / g) a.push_back(s[i]);
  for (int i = 0; i < m; i += m / g) b.push_back(t[i]);

  cout << (a == b ? n * m / g : -1) << endl;
}

こんな感じになりました。単純なif~else文なら、三項演算子の方がスッキリします（読みにくいけど）。

感想

数学は大切。texすごい。にしても今回の説明は分かりにくい気しかしない。