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

目次

概要

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

    
s-yoshiki
s-yoshiki
githubtwitterqiita
Web作ってますが、インタラクティブなプログラミングも好きです。
JavaScript / Vue / node.js / PHP / AWS / OpenCV

関連記事

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

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

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…

0埋め・ゼロ埋め処理 のコードJavaScript
サンプル コード 呼び出す 説明 参考 追記 JavaScriptで 0埋め / ゼロ埋め / zero埋め 処理を行うサンプルコード サンプル コード 呼び出す 説明 記事タイトルが…

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

うるう年を求めるプログラム JavaScript
閏年の条件 サンプルコード 判定関数 21世紀のうるう年を算出する うるう年を求める実装メモです。 閏年の条件 閏年の条件は以下の通りとなります。 https://www.nao.ac.jp/faq/a0306.html サンプルコード 判定関数 2…

MonacoEditor + Vue を使ってエディタを実装
紹介 セットアップ Vue vue-monaco Usage サンプルコード ポイント テーマカラーについて エディタのリサイズ エディタの変更の検知 Vue + MonacoEditorでJS…

async awaitで画像を読み込み canvasに描画 JavaScript
async サンプルコード async await Promise を使ってブラウザにアップロードした画像をcanvasに非同期で描画するサンプルの紹介です。 onloadメソッド縛りで実装すると非同期地獄になりますが、async await…

OpenCV.jsを動かしてみる + デモ
環境 OpenCV.jsのセットアップ サンプルソース グレースケール 2値化 Cannyエッジ 輪郭抽出 ガウシアン デモ OpenCV.jsを試してみました。 環境 OpenCV.js v4.1.0 OpenCV.jsのセットアップ OpenCVをWasm…

最新の投稿

GitHub Actions で Gatsby をビルドし Amazon S3 にデプロイする
GitHub Actions について あらかじめ準備しておくもの AWS IAM ユーザを環境変数にセットする workflowの記述 ビルド バッジを利用する 終わりに 参考にしたところ Gatsbyで作った静的サイトを、GitHub Actions…

cloudinaryによる画像ファイルの管理 はじめてみる
目的 cloudinary について 他のサービスとの比較 料金プラン アカウントの登録 利用してみる ダッシュボード 画像の編集 APIベースでのアクセス 感想 参考 画像の管理や配信、さらには加工といった事ができるsaas型のcloud…

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

Vue.jsで作成された、ちょっと面白くて役立ちそうなサービス
UIコンポーネント VueSocial CKEditor 5 Vue.Draggable Vuetable 2 vuejs-datepicker Kalendar Vue Apexcharts Vue.js Google Charts vue-cart WebIDE…

GitHubのリポジトリをGitLabに同期する GitLabのミラーリング機能
GitLabのミラーリングについて GitHubのリポジトリをGitLabに反映する その他 参考 GitLabのミラーリング機能によりGitHubなどの外部のリポジトリとのミラーリングを行うことができます。 これを使ってGitHub…

WordPressやめます Gatsbyに移行しました
これまでのWordPress運用 なぜWordPressを捨てるのか? なぜGatsbyを利用するのか? gatsbyについて WordPressから記事の救出 移行対象記事の抽出 記事の置換 Gatsbyテーマの作成 Gatsby…

WordPressのDBから記事データを抽出する
WordPressのDB関連図 公開記事一覧の取得 タグ・カテゴリの取得 サムネイルの取得 おまけ: PHPスクリプト化しました 参考にしたところ WordPressにため込んだデータMarkdown化しGatsby…

ハイフンとかマイナスとかダッシュとか

Firebase + Nuxt で認証付きページを作るときに参考にしたいところ
Webアプリケーションのセッション管理にJWT導入を検討する際の考え方 Service Worker によるセッション管理 ユーザー セッションの管理 Nuxt.jsとFirebaseでSPA×SSR×PWA×サーバーレスを実現する CookieとセッションとJWT SSR…

GolangをCGIとして実行する
環境 golang パッケージ ソースと実行 ビルドとサーバ実行 標準ライブラリのみ Golang を CGIとして実行する際のメモ 環境 golang パッケージ 以下のモジュールを利用しています。 github.com/gorilla/mux…

Tags

Dates

© 2020   404 motivation not found