初めて参加した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%B0atcodernode.js
    

目次

概要

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問題)

    

関連記事

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

[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…

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

[JS]ラジアンから度数に度数からラジアンに変換する
コード 度数からラジアンへ ラジアンから度数へ サンプル ラジアンから度数に度数からラジアンに変換する際のスニペット。 コード 度数からラジアンへ ラジアンから度数へ サンプル

JS/TSのclassでclass名を取得する
コード JS/TSのconstructorを利用して自分自身のクラス名を取得する際のメモ。 コード このコードの結果は次のようになります。

JSで32ビット符号付き整数に対してのビット演算でハマった
具体例 参考にしたサイト JSでサブネットマスクの計算を行おうとしたとき、ビット演算でハマりました。その時のメモです。 JSでサブネットマスクの計算 JSでビット演算子を利用する場合 3…

JSでIPアドレスがサブネットマスクで指定した範囲内にあるか判定する
IPアドレスが指定した範囲内にあるかどうか判定 参考にしたサイト JSでIPアドレス(IPv4)が指定したサブネットの範囲に含まれるか判定するロジックを作った時の記録です。 IPアドレスが指定した範囲内にあるかどうか判定 処理としては、IP…

プログラムの数値計算で発生する誤差の種類 丸め誤差・打ち切り誤差・桁落ち
はじめに 誤差の種類 丸め誤差 打ち切り誤差 桁落ち 情報落ち 桁溢れ誤差 参考にしたサイト コンピュータで出てくる誤差はいくつかありますが、 それらをコードに落として整理しました。 はじめに 例えば の計算の答えは 0.6666666666…

最新の投稿

[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