初めて参加したAtCoderで惨敗した話

初めて参加したAtCoderで惨敗した話

2018-07-234 min read

目次

  1. 概要
  2. 状況
  3. 結果
  4. 敗因
  5. 対策
  6. atcoderとかでも利用したいブラウザで動くエディタ--デバッグ環境を作る-追記-201808
  7. atcoderで初めて色がつくまでの話茶色-追記-201811
  8. 追記--atcoderabcで初めてc問題が解けました-追記-201812

概要

2018/07/21。

特に事前調査もせず軽いノリで AtCoderに初めて参戦しました。

そして惨敗しました。

敗因を書きます。

状況

今回、参戦したのは「AtCoder Beginner Contest 103」 https://beta.atcoder.jp/contests/abc103 100分 言語は全4門ともJavaScript(nodejs)を選択。

そして....

結果

  • 順位 1810/2188 位

  • 得点 300/1000点

  • パフォーマンス 346

  • レーティング 17

  • A :100 :○

  • B :200 :○

  • C :300 :×

  • D :400 :×

2完。 しかもB問題に少し手間取ったため、レーティングも伸びず。 C問題がクリアできれば、半分より上の順位には入れそうであった。

敗因

ざっと思いつく敗因は以下の通り。

  • 標準入出力に手間取りロジックを考える時間が奪われてしまったこと。
  • 数学的な基礎知識の欠如
  • 配列操作に手こずった

標準入出力に手間取りロジックを考える時間が奪われてしまったこと。

完全に標準入出力を忘れてました。 ここで数分ロスしてしまいました。

数学的な基礎知識の欠如

今回の問題は

入力値を a b c ... とした時

** f(X) = (a mod X) + (b mod X) + (c mod X) + ..... **

で、f(X)が最大になる時のXを求める問題です。

頭では解けたつもりだったが、 どうしてもタイムオーバ(TLE)してしまいクリアできず。

** X = (a + b + c + ....) - length(a + b + c + ....) **

でクリアしている人がおり全く理解できなかった。 とにかく数学的な基礎知識が欠けているんだなと思った。

全探索のような実装でも解けるけど、問題の意図は、 効率的な方法を実装をしなければならないということだと感じました。

データ操作に手こずった

標準入出力から受け取った文字列を任意のデータにするのに時間がかかってしまいました。 回答中に基本的な配列操作方法をググりだしてしまう始末。

そもそも pop push shift unshift などは、実装時にパッと浮かばなきゃマズイと思いました。

と言うわけで

対策

標準入出力の処理をテンプレ化する

AtCoderの問題形式は必ず標準入出力で変数の受け取り、回答の出力を行うので 開始したらとりあえずこれをコピペする(言語でjsを選択した場合)。

まずは、このフォーマットに沿って書けば問題ないかと思います。

function main(arg) {
    // 処理
    console.log(arg)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

配列操作等の基本操作を完璧にする

pop push shift unshift あたりの基本操作は完璧にする。 この辺を押さえてないとB問題すら解けるか怪しくなると思います

加えて、jsの場合

arr.sort((a,b) => {
    if (a > b) {
        return 1
    } else {
        return -1
    }
})

で簡単にソートができます。

他にも配列操作のメソッドであれば、map、forEach、fillter、といった便利な機能が用意されています。

スクリプト言語を使うのであれば、標準で用意されている配列操作などのメソッドを覚えておくことで、自分でソートなどのロジックを書くことが省けると思います。

スニペットを用意しておく

全加算、全乗算、素数判定、ソートとかの頻繁に出てきそうな処理はスニペットにすると良いかといます。

多分そうやってやっている人もいるんじゃないかな... GolangでAtCoderの問題を解くためのスニペット集

数をこなす / アルゴリズムの基礎知識の向上

細かいテクニックがどうであれ、基本的なアルゴリズムを押さえてないとそもそも太刀打ちできません。

http://osrehun.hatenadiary.jp/entry/2015/12/13/000716

↑ここでも書かれているように、 「探索」や「データ構造」といったアルゴリズムを一つづつ押さえていくことがC、D問題への最短経路になると思います。

まだまだ問題の傾向がつかめていないところもあるので、 まずは、ある程度ABCに参加して傾向を掴みたいと思います。

AtCoderとかでも利用したい、ブラウザで動くエディタ + デバッグ環境を作る ※追記 2018/08

https://tech-blog.s-yoshiki.com/2018/09/585/

Microsoft謹製のエディタ「Visual Studio Code」でも使われているエディタ機能のJavascriptライブラリ「MonacoEditor」を使って自分専用のデバッグ環境を作りました。

AtCoderで初めて色がつくまでの話(茶色) ※追記 2018/11

https://tech-blog.s-yoshiki.com/2018/11/778/

AtCoderで、ついに色がつきました。茶色になりました。 始めた当初は、はっきり言って茶色なんて大したことのないランクだと思っていました。 ここまで来るのに4ヶ月、回数にして10回目の参加での到達で想定よりも時間がかかってしまいました。

また、上記の改良版をGitHubで公開しました。

https://s-yoshiki.github.io/AtCoder-JsDebugger/#/

※追記 | 【AtCoder】ABCで初めてC問題が解けました。 ※追記 2018/12

https://tech-blog.s-yoshiki.com/2018/12/830/

コンテスト内の順位は656位(/1736)。 出したパフォーマンスは1021。 レーティングは468→554(+86)となりました。

C問題を解いたユーザの中では遅い方でしたが、パフォーマンスは1000を超えました。 安定的にパフォーマンス1000を超えるのであればC問題を解くのは必須と言えそうです。

(※ABC問題)

Recommends
[JS]BigIntでMathが使えない件
2022-06-12
javascript
node.js
atcoder
初めて参加したAtCoderで惨敗した話
2018-07-23
javascript
%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%B0
atcoder
javascriptで累積和を解く
2022-02-27
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%A0%E3%83%9F%E3%83%B3%E3%82%B0
atcoder
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%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%B0
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%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%B0
JavaScriptでbig-integerでできること
2019-12-30
javascript
%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%B0
node.js
JavaScript で bit全探索
2019-06-10
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%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%B0
atcoder
ブラウザで動くAtCoder用のデバッガを作ってみた (JSのみ)
2019-05-02
javascript
%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%B0
atcoder
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%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%B0
複数キーでソートするサンプルコード JavaScript
2018-11-05
javascript
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%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%B0
【JavaScript】AtCoderとかでも利用したい、ブラウザで動くエディタ + デバ...
2018-08-29
javascript
semantic%20ui
%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%B0
[NestJS]少し大きな規模のRESTfull APIを構築するディレクトリ構成を考えて...
2022-09-04
nestjs
typescript
%E3%82%A2%E3%83%BC%E3%82%AD%E3%83%86%E3%82%AF%E3%83%81%E3%83%A3
Fisher-Yates shuffleで配列シャッフル [js/ts/php]
2022-06-19
javascript
node.js
typescript
JavaScriptでUTF-16コードを文字列に変換
2022-06-18
javascript
node.js
[JS]乱数でランダムな整数を生成する
2022-06-18
javascript
node.js
New Posts
[JS]Intl.DateTimeFormatで和暦と西暦を変換
2022-08-18
javascript
[NestJS]少し大きな規模のRESTfull APIを構築するディレクトリ構成を考えて...
2022-09-04
nestjs
typescript
%E3%82%A2%E3%83%BC%E3%82%AD%E3%83%86%E3%82%AF%E3%83%81%E3%83%A3
Prisma MySQL でUTC以外の任意のタイムゾーンを利用するのが難しい件
2022-08-08
prisma
typescript
mysql
Prisma TypeScript MySQLなプロジェクトの構築
2022-08-08
prisma
typescript
mysql
Prisma TypeScript SQLiteなプロジェクトの構築
2022-08-06
prisma
typescript
sqlite
[AWS]Lambda vs Fargate. APIを実装する場合に思うこと
2022-07-30
amazon%20aws
amazon%20ecs
%E9%9B%91%E8%AB%87
macOSにzigをインストールしてHello World!する
2022-07-18
zig
mac
[AWS CDK] Cognito の OIDC プロバイダに Auth0 を設定
2022-07-03
auth0
amazon%20aws
aws%20cdk
Amazon S3 でライフサイクルポリシーを設定する
2022-06-19
amazon%20aws
amazon%20s3
AWS Certified Developer Associate に合格した
2022-06-19
amazon%20aws
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93
Fisher-Yates shuffleで配列シャッフル [js/ts/php]
2022-06-19
javascript
node.js
typescript
JavaScriptでUTF-16コードを文字列に変換
2022-06-18
javascript
node.js
[JS]乱数でランダムな整数を生成する
2022-06-18
javascript
node.js
[JS]BigIntでMathが使えない件
2022-06-12
javascript
node.js
atcoder
AWS SAPに合格しました
2022-06-11
amazon%20aws
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
linux
curl
OpenCVのMatのタイプ一覧表
2018-11-25
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86
opencv
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
linux
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9
mysql
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
oracle
mysql
sqlite
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
amazon%20aws
linux
amazon%20s3
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
%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%B0
%E9%9B%91%E8%AB%87
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
centos
red%20hat
EPEL
Macでターミナルからポートスキャンを行う方法。
2018-12-09
linux
mac
apple
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
python
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86
opencv
Date
▶︎
2022 年 (39)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
javascript(98)
amazon%20aws(47)
linux(47)
node.js(38)
%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0(36)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86(30)
html5(29)
typescript(28)
php(24)
centos(24)
python(22)
%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%B0(21)
mysql(19)
mac(19)
canvas(18)
opencv(17)
%E9%9B%91%E8%AB%87(16)
wordpress(15)
atcoder(14)
docker(14)
apache(12)
%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92(12)
%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9(12)
amazon%20s3(12)
red%20hat(12)
ubuntu(11)
github(10)
git(10)
vue.js(10)
%E7%94%BB%E5%83%8F%E5%87%A6%E7%90%86100%E6%9C%AC%E3%83%8E%E3%83%83%E3%82%AF(10)
mariadb(10)
aws%20cdk(9)
css3(8)
%E5%8F%AF%E8%A6%96%E5%8C%96(8)
%E5%B0%8F%E3%83%8D%E3%82%BF(8)
amazon%20lightsail(7)
react(7)
%E3%83%96%E3%83%AD%E3%82%B0(6)
cms(6)
oracle(6)
perl(6)
gitlab(6)
next.js(6)
iam(5)
amazon%20ec2(5)
%E8%B3%87%E6%A0%BC%E8%A9%A6%E9%A8%93(5)
aws%20amplify(5)
curl(4)
webassembly(4)
ssh(4)
Author
s-yoshiki
s-yoshiki
githubzenntwitterqiita
ただの備忘録です。
JavaScript/TypeScript/node.js/React/AWS/OpenCV
※このブログの内容は個人の見解であり、所属する組織等の見解ではありません。