
【AtCoder】#110 反省会 C問題でLTEを連発。スクリプト言語でループゴリ押し計算はキツい
2018-09-247 min read
目次
概要
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'));
なんていうか、目から鱗だった。 最良ではないかもしれないが、コードがシンプルで素敵。
結論
お算数力が足りない。ただそれだけ。以上。
Recommends
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
JavaScript で bit全探索
2019-06-10
ブラウザで動くAtCoder用のデバッガを作ってみた (JSのみ)
2019-05-02
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
【AtCoder】#110 反省会 C問題でLTEを連発。スクリプト言語でループゴリ押し計...
2018-09-24
AtCoder 109反省会。C問題が比較的に楽だったのに落としてしまった。あぁレート落ち...
2018-09-09
【JavaScript】AtCoderとかでも利用したい、ブラウザで動くエディタ + デバ...
2018-08-29
AtCoderに3回出場してわかったこと (AtCoder ABC 107 反省会)
2018-08-26
初めて参加したAtCoderで惨敗した話
2018-07-23
javascriptで累積和を解く
2022-02-27
JavaScriptで優先度付きキューを実装する
2021-08-01
next_permutationをJSで実装する
2021-07-22
10進数から2進数 2進数から10進数への変換 JavaScript
2020-07-12
JavaScriptでワーシャルフロイド法を実装
2020-06-21
New Posts
[AWS CDK]ECS FargateでNestJSで作成したRESTfull APIデ...
2022-05-24
[AWS CDK]S3 CloudFront OAI Route53 構成 で NextJ...
2022-05-23
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
GatsbyからNext.jsへのサイト移行
2022-04-04
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
[AWS CDK] Cognito を構築
2022-03-04
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
javascriptで累積和を解く
2022-02-27
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
NextJSでDevToysのようなものを作成した
2022-02-22
JSで動的計画法を利用して部分和問題を解く
2022-02-20
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
OpenCVのMatのタイプ一覧表
2018-11-25
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
Macでターミナルからポートスキャンを行う方法。
2018-12-09
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
Date
▶︎
2022 年 (23)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
Author