【TypeScript】AtCoder abc120_c

atcoder.jp

テストコード

import { main } from './main'

describe('tests', () => {
  test('1', () => {
    expect(main('0011')).toEqual(4)
  })

  test('2', () => {
    expect(main('11011010001011')).toEqual(12)
  })

  test('3', () => {
    expect(main('0')).toEqual(0)
  })
})

提出コード (TLE)

愚直に問題手順を再現。

当然のようにTLE。

TypeScript

export const main = (S: string): number => {
  let sList = S.split('')
  let res = 0
  let flg = true

  while (flg) {
    let cnt = 0
    for (let i = 0; i < sList.length - 1; i++) {
      if (
        (sList[i] === '0' && sList[i + 1] === '1') ||
        (sList[i] === '1' && sList[i + 1] === '0')
      ) {
        sList[i] = 'removed'
        sList[i + 1] = 'removed'
        cnt += 2
      }
    }
    sList = sList.filter(s => s !== 'removed')
    if (cnt === 0) {
      flg = false
    }
    res += cnt
  }

  return res
}

const input: string = require('fs').readFileSync('/dev/stdin', 'UTF-8')

const res = main(input)
console.log(res)

ES5トランスパイル

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.main = function (S) {
    var sList = S.split('');
    var res = 0;
    var flg = true;
    while (flg) {
        var cnt = 0;
        for (var i = 0; i < sList.length - 1; i++) {
            if ((sList[i] === '0' && sList[i + 1] === '1') ||
                (sList[i] === '1' && sList[i + 1] === '0')) {
                sList[i] = 'removed';
                sList[i + 1] = 'removed';
                cnt += 2;
            }
        }
        sList = sList.filter(function (s) { return s !== 'removed'; });
        if (cnt === 0) {
            flg = false;
        }
        res += cnt;
    }
    return res;
};
var input = require('fs').readFileSync('/dev/stdin', 'UTF-8');
var res = exports.main(input);
console.log(res);

提出コード (AC)

drken1215.hatenablog.com

こちらの解法1を参考にした。

スタックをうまく利用する点が肝のようだ。

JSの配列はそもそもスタックの仕様を満たしているようなのでそのまま使用。

TypeScript

export const main = (S: string): number => {
  let sList = S.split('')
  let res = 0

  const st: string[] = []

  for (let i = 0; i < sList.length; i++) {
    if (st.length === 0 || st[st.length - 1] === sList[i]) {
      st.push(sList[i])
    } else {
      res += 2
      st.pop()
    }
  }

  return res
}

const input: string = require('fs').readFileSync('/dev/stdin', 'UTF-8')
const lines = input.split('\n')
const res = main(lines[0])
console.log(res)

ES5トランスパイル

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.main = function (S) {
    var sList = S.split('');
    var res = 0;
    var st = [];
    for (var i = 0; i < sList.length; i++) {
        if (st.length === 0 || st[st.length - 1] === sList[i]) {
            st.push(sList[i]);
        }
        else {
            res += 2;
            st.pop();
        }
    }
    return res;
};
var input = require('fs').readFileSync('/dev/stdin', 'UTF-8');
var lines = input.split('\n');
var res = exports.main(lines[0]);
console.log(res);