【AtCoder】ABCで初めてC問題が解けました。【ABC114】

2018-12-03
%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について

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

AtCoder Beginner Contest、 通称ABCはAtCoderのコンテストの1つで初級〜中級者を対象としており、A、B、C、Dの4つの問題で構成されています。

ABCDの問題を難易度順に並べると、

A < B <<< 壁 <<< C <= D 

といった難易度じゃないかと思います。

AB問題に関しては、基本的なプログラミングの文法を試されていますが、 C以降の問題は、数学的な考え方が要求されプログラムの文法だけでは戦えなくなるためAtCoder初心者の壁に成ると思います。

はじめてC問題が解けました

https://beta.atcoder.jp/users/yoshiki1123

AtCoder Beginner Contest 114 (ABC114)で初めてC問題が解けました。 毎回C問題がギリギリのところで解けず、モヤモヤしていたのでとても嬉しいです。

ただ、いつものC問題よりも若干簡単なのかなとも思いました。

C問題を解いた時のパフォーマンス

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

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

緑までの道のりはまだ長そうです。以上。

おまけ:解いた問題 C - 755

ちなみに今回提出してACとなった回答を紹介しておこうと思います。

問題

https://beta.atcoder.jp/contests/abc114/tasks/abc114_c

整数 Nが与えられます。 1以上N以下の整数のうち、七五三数 は何個あるでしょうか?

ここで、七五三数とは以下の条件を満たす正の整数です。 十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1回以上現れ、これら以外の数字は現れない。

AtCoder ABC C - 755

という問題。

計算例

入力例

575

出力例

4

575以下の七五三数は、357,375,537,573の4個。

回答ソース JavaScript

function main(arg) {
    arg = Number(arg.split("\n")[0])

    var master = [0, 3, 5, 7]
    var counter = 0;

    for (var i = 0; ; i++) {
        var tmp = String(i.toString(4))
        var _tmp = "";

        if (tmp.length < 3) {
            continue;
        }

        if (tmp.indexOf('0') !== -1) {
            continue;
        }

        var b = tmp.split("").filter(function (x, i, self) {
            return self.indexOf(x) === i;
        });

        if (b.length < 3) {
            continue;
        }

        for (var j = 0; j < tmp.length; j++) {
            _tmp += master[tmp[j]]
        }

        if (_tmp > arg) {
            break;
        }
        counter++
    }
    console.log(counter)
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

考え方的には、3,5,7から成り立つ3進数に変換して総当たりで解くという方法を考えました。 無事、ACとなりました。

おまけ2

    

関連記事

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