A - Tricky Template / Educational Codeforces Round 161 (Rated for Div. 2)

問題

整数 と 文字の英小文字からなる3つの文字列 が与えられる。

また、 文字の英小文字と英大文字からなる文字列をテンプレートと呼ぶ。 から までのすべての について、以下の条件が成立するとき、文字列 がテンプレート にマッチすると言う。

• テンプレートの 番目の文字が小文字の場合、 と が同じである。
• テンプレートの 番目の文字が大文字の場合、 と の小文字は同じではない。
  • 例えば、 A のとき、 は a 以外の文字でなければならない。

このとき、 と のテンプレートであり、 のテンプレートではない文字列が存在するかを判定せよ。

入力

まず最初の1行目に、テストケースの個数を表す整数 が与えられる。

その後、 個のテストケースのそれぞれに対して、以下のように入力が与えられる。

• 最初の1行目には、整数 が与えられる。
• その後3行に渡り、文字列 がそれぞれ1行ずつで与えられる。

条件

• 実行時間制限: 2s
• メモリ制限: 256MB
• 
• 

出力

行に渡り、各テストケースについて、テンプレートが存在する場合は YES を、存在しない場合は NO を出力すること。

解法

まず、与えられる2つの文字列 のテンプレートとなる文字列は必ず存在します。 これは、そのテンプレートとなる文字列を とすると、 である について、

• であるならば、 とすることにより、条件を満たす
• であるならば、 に の大文字、 の大文字とは異なる大文字を配置することにより、条件を満たす

という方法をすべての に対して行えばテンプレートが完成するためです。

さて、テンプレートとなるための条件は 文字目から 文字目までのすべての文字について、与えられた条件を満たすことになります。 従って、逆に与えられた条件を満たさないような箇所が1箇所でもあると、テンプレートとはなりません。

以上から、 のテンプレートであって、 のテンプレートではない文字列が存在すると仮定して、これを とします。 このときに、 の 番目の文字によって、 は のテンプレートではないと判断できるとすると、

• であるならば、 は小文字であるため、 ならば は のテンプレートでなくなる
  • このとき、 であるため、 かつ が成立する
• であるならば、 は大文字であるため、 が の大文字であれば、 は のテンプレートでなくなる
  • このとき、 が存在する仮定なので、 は の大文字と の大文字であってはならない
  • 従って、 かつ が成立する

というように条件を整理することができます。

従って、問題の条件を満たすような文字列が存在するための条件は、 [txe: {a}_{i} \ne {c}_{i}] かつ を満たすような が少なくとも1つは存在すること、ということになります。

これは、 の計算量で求めることができるので、実行時間制限にも十分間に合うと言えます。

ソースコード

各テストケースに対して、テンプレートが存在する場合は true を、存在しない場合は false を返す関数 solve() を以下のように実装しました。

int n;
string s[3]; // 3つの文字列が入る配列

bool solve() {
  // 値の入力
  cin >> n;
  for (int i = 0; i < 3; i++) {
    cin >> s[i];
  }

  for (int i = 0; i < n; i++) {
    // 上記条件が1つでも満たされていればテンプレートは存在するので、 true を返す
    if (s[0][i] != s[2][i] && s[1][i] != s[2][i]) {
      return true;
    }
  }

  return false;
}

• 提出したコード: https://codeforces.com/contest/1922/submission/242788787
• GitHub

感想

最初問題文を原文のまま見たときに、何を判断させる問題なのかわかりませんでした。 自身の英語力を鍛えないといけないですね…。