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

2018-09-24
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0atcoder
    

目次

概要

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'));

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

結論

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

    

関連記事

JavaScriptで優先度付きキューを実装する
優先度付きキューについて ソース 参考 JavaScriptで優先度付きキュー (プライオリティキュー) を実装する 優先度付きキューについて 具体的には次のような機能があります。 キューに対して要素を優先度付きで追加 (push…

next_permutationをJSで実装する
ソース 使い方 参考 C++で提供されている順列を生成する next_permutation のJS実装です。 ソース 順列が存在する場合はtrueを返し、そうでなければfalse…

10進数から2進数 2進数から10進数への変換 JavaScript
10進数から2進数 2進数から10進数 テスト 10進数から2進数、2進数から10進数への変換を行うJavaScriptのコードの紹介。 JSの場合、10進数から2進数への変換はメソッド。2進数から1…

JavaScriptの配列ショートハンド (AtCoder用)

JavaScriptでワーシャルフロイド法を実装
AtCoder ABC012 D問題 D - バスと避けられない運命 解説 実装 AtCoder ABC012 の D問題でワーシャルフロイド法が利用できる問題が出てきたので、 JavaScriptで実装しました。 AtCoder ABC012 D問題 D…

JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2分探索について ソース 参考 JavaScriptで2分探索(バイナリサーチ)を実装してみました。…

JavaScriptで幅優先探索 (bfs) を実装する
bfsソースコード 前提 bfs関数 テストコード JavaScriptで幅優先探索 (bfs) を実装し簡単な最短経路の探索問題を解いてみました。 AtCoderの問題を参考にしています bfsソースコード 前提 bfs 関数の定義について 引数 table…

JavaScriptでbig-integerでできること
定数 メソッド abs add, plus and bitLength compare compareTo compareAmb divide, over divmod equals, eq greater, gt greaterOrEquals, geq…

順列・組み合わせ のサンプルコード JS [permutation] [combination]
順列 - permutation サンプルコード Usage 組み合わせ - combination サンプルコード Usage 順列(permutation) と 組み合わせ(combination) のサンプルコードをJavaScript…

JavaScript で bit全探索
サンプル1 サンプル2 参考 AtCoderとかをやっていると、 動的計画法(DP)、部分和といった問題とかに遭遇したりしますが、…

最新の投稿

[Mac]ipコマンドの導入[iproute2mac]
iproute2macについて 導入 homebrewで導入 直接インストール 確認 サポートコマンド を導入して、macOSでipコマンドを導入した際のメモ iproute2macについて brona/iproute2mac: CLI wrapper for…

AutotoolsでconfigureやMakefileの作成
はじめに Autotools 環境 準備 ツール類のインストール ソースコードの作成 configure.ac と Makefile.am configure Makeの生成 その他 makeオプション autoreconf について Perlの場合 リンク はじめに C…

RPMパッケージ作成 Dockerを利用して
はじめに RPMパッケージ step1.環境構築からRPMパッケージングまで 事前準備 ワークスペースの作成 プログラム配置 specファイル rpmbuild インストール リンク はじめに Dockerを利用してRPM開発環境を用意し、実際にRPM…

RPMのspecファイルで利用するマクロ・変数
はじめに マクロ一覧 基本情報系 Body項目 コメント 参考文献 はじめに RPM(Fedora/CentOS系)を作成する際に利用するspecファイルで利用できるマクロについて調べた際のメモです。 マクロ一覧 基本情報系 パッケージの名前を定義します。これはspec…

CentOS8/RHEL8でのRPM管理における検討事項
初めに 前提 rpm rpm yum dnf コマンド リポジトリ リポジトリとライフサイクル AppStream Compatibility Level について AppStreamのサポート期間 Yum v3 -> Yum v4 リンク 初めに CentOS8/RHEL…

homebrewでnodejsインストール&任意のバージョン利用
初めに homebrewインストール nodejsの検索 インストール nodejsの利用 初めに homebrewでサクッとnodejsのインストールを行なった際のメモです。 環境はMacを対象としていますが、Linux…

tracerouteコマンドでネットワークの経路を洗い出す
tracerouteの用途 tracerouteの原理 IPヘッダのTTL コマンドを実行してみる 参考文献 tracerouteコマンドでネットワークの経路を洗い出した際の操作をメモしました。 環境はmacで実施しています。 また、traceroute…

[Vue]フロントエンド機能のみでダウンロードを実装する[JS]
実装 ポイント ソース デモ 参考サイト フロントエンドのみ(=サーバサイドがダウンロードさせない) でダウンロードを行う機能を実装した時のメモです。 Vueを利用して実装していますが、ここで記載しているコードはVueに依存した機能ではなく、ピュアなJSのAPI…

Node.js で作成した REST API を Docker化
Node.jsでREST APIを作成 コンテナ化 コンテナ化定義 コンテナ化作業 参考 Node.js で作成した REST API を Docker化した際のメモです。 Node.jsでREST APIを作成 まずはNode.js…

JavaScriptで優先度付きキューを実装する
優先度付きキューについて ソース 参考 JavaScriptで優先度付きキュー (プライオリティキュー) を実装する 優先度付きキューについて 具体的には次のような機能があります。 キューに対して要素を優先度付きで追加 (push…

Tags

Dates

s-yoshiki
s-yoshiki
githubtwitterqiita
ただの備忘録です。
JS/TS/node.js/PHP/AWS/OpenCV/CentOS
※このブログの内容は個人の見解であり、所属する組織等の見解ではありません。
© 2022   404 motivation not found