【AtCoder】#110 反省会 C問題でLTEを連発。スクリプト言語でループゴリ押し計算はキツい

目次

1. 概要
2. c問題
3. 結論

概要

AtCoder #110 に参加しました。 A、Bはいつも通り。10分程度でクリア。 Dも理解できそうな問題ではあったがパス。 問題はC。

問題内容自体は難しいと感じなかったが、いくつかのテストケースがどうしてもLTEとなってしまい、 それをズルズルと1時間以上はまり続け結局クリアできず。

C問題

https://beta.atcoder.jp/contests/abc110/tasks/abc110_c

英小文字のみからなる文字列 S,Tが与えられます。 文字列 S に対して、次の操作を何度でも行うことができます。 操作: 2つの異なる英小文字 c1, c2 を選び、S に含まれる全ての c1 を c2 に、c2 を c1 に置き換える 0 回以上操作を行って、S を T に一致させられるか判定してください。

という問題である。

LTEとなったコード

function main(arg) {
  arg = arg.split('\n');
  var s = arg[0];
  var t = arg[1];

  for (var i = 0; i < t.length; i++) {
    var si = s[i].slice();
    var ti = t[i].slice();

    if (si === ti) {
      continue;
    }

    if (s === t) {
      break;
    }

    s = s.split(si).join(ti.toUpperCase());
    s = s.split(ti).join(si.toUpperCase());

    s = s.toLowerCase();
  }

  if (s.toLowerCase() === t) {
    console.log('Yes');
  } else {
    console.log('No');
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

全ての例題で与えられていたテストケースをクリアすることができたので、 問題ないだろうと提出。しかしながら、クリアできず。LTEとなる。 置換している部分のパフォーマンスがおそらく悪かったのだろう。そもそもYesかNoを出力するだけなので、配列操作自体が不要だった。

それに加え、大文字で置換した文字を小文字に倒している処理もありスマートではない。

JSじゃなかったらループゴリ押しで片付けられてたのかもしれないが。

解法

解説では、 「置換表を作った上で整合性が取れないものがあった場合、Noを出力するように実装する。文字列置換を愚直に行うな。」と言っている。

最速の解法 (?)

適当に調べていたら、こんなコードがあった。(元はPythonの提出の1つ)

function main(arg) {
  arg = arg.split('\n');
  var s = arg[0];
  var t = arg[1];

  while (1) {
    if (s === '') {
      break;
    }

    s = s.split(s[0]).join('');
    t = t.split(t[0]).join('');

    if (s.length !== t.length) {
      console.log('No');
      return;
    }
  }
  console.log('Yes');
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

なんていうか、目から鱗だった。 最良ではないかもしれないが、コードがシンプルで素敵。

結論

お算数力が足りない。ただそれだけ。以上。