AtCoder 109反省会。C問題が比較的に楽だったのに落としてしまった。あぁレート落ちるわ。

2018-09-09
%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
    

目次

概要

ABはいつも通り通過。Dはまあいいや。問題はC。

今日こそ落とすような問題ではなかったのにも関わらず

1ケースがどうしても通らずREのまま終わった。

今日は参加数が多かったのでなんとも言えないが、

多くの人が正解してたっぽいのでレートが落ちるのは確実。

ひとまず振り返る。

C問題

C -Skip

数直線上に N 個の都市があり、i 番目の都市は座標 xi にあります。

あなたの目的は、これら全ての都市を 1 度以上訪れることです。あなたは、はじめに正整数 D を設定します。

その後、あなたは座標 X から出発し、以下の移動 1、移動 2 を好きなだけ行います。

  • 移動 1: 座標 y から座標 y+D に移動する
  • 移動 2: 座標 y から座標 y−D に移動する
全ての都市を 1 度以上訪れることのできる D の最大値を求めてください。

ここで、都市を訪れるとは、その都市のある座標に移動することです。

入力

3 3
1 7 11

出力

2

引用

https://beta.atcoder.jp/contests/abc109/tasks/abc109_c

問題の考察:最小公倍数

とりあえず数値を並べてみると

1 7 11

スタートの3を加えてソート

1 3 7 11

数列の差を取得して

2 4 4

最小公倍数を計算する

2

と求めれば解けるんじゃないかなと考えた。

結論から言うと、解答例を見る限り、考え方的には間違っていたわけではなさそうである。 解答例:editorial.pdf

提出ソース

上記を実装したのがこちら

function gcd(a, b) {
    if (b === 0)
        return a;

    return gcd(b, a % b);
}

function main(arg) {
    arg = arg.split("\n")
    var tmp = arg[0].split(" ")
    var N = tmp[0]
    var X = tmp[1]
    var xi = arg[1].split(" ")
    
    xi.push(X)
    xi = xi.map(function(e){return parseInt(e,10)})
    
    xi.sort(function(a,b) {
        if (a > b) {
            return 1
        }
        return -1
    })
    
    if (xi.length === 2) {
        console.log(xi[1] - xi[0])
        return
    }
    
    
    var result = []
    
    for (var i = 1; i < xi.length; i++ ){
        result.push(xi[i] - xi[i-1])
    }
    
    result = result.filter(function (x, i, self) {
        return self.indexOf(x) === i;
    });
    
    if (result.length === 1) {
        console.log(result[0])
        return
    } else {
        while(1) {
            var _tmp = [];
            for (var j = 1; j < result.length;j++) {
                _tmp.push(gcd(
                    result[j],
                    result[j-1]
                ))
            }
            if (_tmp.length === 1) {
                break;
            } else{
                result = _tmp
            }
        }
        console.log(result[0])
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

で提出結果がこちら。

hand_1のテストケースの内容はわからなかったず....こいつのせいで30分以上苦しんだ。 最終的に通過したケースはこちら。
function gcd(a, b) {
    if (b === 0)
        return a;

    return gcd(b, a % b);
}

function main(arg) {
    arg = arg.split("
")
    var tmp = arg[0].split(" ")
    var N = tmp[0]
    var X = tmp[1]
    var xi = arg[1].split(" ")
    
    X = Number(X)
    xi = xi.map(function(e){return Math.abs(parseInt(e,10)-X)})
    
    xi.sort(function(a,b) {
        if (a > b) {
            return 1
        }
        return -1
    })
    
    if (xi.length === 2) {
        console.log(xi[1] - xi[0])
        return
    }
    
    
    var result = []
    
    for (var i = 1; i < xi.length; i++ ){
        result.push(xi[i] - xi[i-1])
    }
    
    result = result.filter(function (x, i, self) {
        return self.indexOf(x) === i;
    });
    
    if (result.length === 1) {
        console.log(result[0])
        return
    } else {
        while(1) {
            var _tmp = [];
            for (var j = 1; j < result.length;j++) {
                _tmp.push(gcd(
                    result[j],
                    result[j-1]
                ))
            }
            if (_tmp.length === 1) {
                break;
            } else{
                result = _tmp
            }
        }
        console.log(result[0])
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

最小公倍数あたりに目をつけられたのは良かった点である。

初期の行列を始点となるポイントXの座標の値でオフセットすれば問題なく通るようだった。 これだけの差か残念だ〜。

今回おぼえたこと

ある2つの整数の最小公倍数を求める関数はこれ。

function gcd(a, b) {
    if (b === 0)
        return a;

    return gcd(b, a % b);
}

ブラウザで動くエディタ + デバッグ環境

https://tech-blog.s-yoshiki.com/2018/08/435/

以前作ったこれを初めて実戦投入したところ思ったよりも使い勝手がよかった。

次はもう少し改良して臨みたい。 そろそろアリ本を買おうかな

    

関連記事

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)、部分和といった問題とかに遭遇したりしますが、…

最新の投稿

Node.js で作成した REST API を Docker化
Node.jsでREST APIを作成 コンテナ化 コンテナ化定義 コンテナ化作業 参考 Node.js で作成した REST API を Docker化した際のメモです。 Node.jsでREST APIを作成 まずはNode.js…

JavaScriptで優先度付きキューを実装する
優先度付きキューについて ソース 参考 JavaScriptで優先度付きキュー (プライオリティキュー) を実装する 優先度付きキューについて 具体的には次のような機能があります。 キューに対して要素を優先度付きで追加 (push…

AWS Amplify で コンテナベースのデプロイを行い REST API を構築
検証した環境 やってみる 初期準備 パイプラインを確認 終了処理 参考 AWS Amplify で コンテナベースのデプロイを行い REST API を構築した際のメモです。 検証した環境 amplify 5.1.…

Pythonでソケット通信を実装しメッセージの送受信を行う
ソース server.py client.py 動かしてみる 参考 Pythonでソケット通信を実現する方法です。 ソース server.py サーバ側のソースです。 client.py…

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

応用情報技術者試験の合格体験記
受験時のステータス 受験結果 対策 スケジュール 午前問題 午後問題 参考書等 令和…

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

CentOS8 に Python + OpenCV をインストール
インストール テスト CentOS8 で標準で提供されているパッケージで Python + OpenCV 環境を構築する方法です。 検証した環境は CentOS8.3 (Docker) です。 インストール まず opencv…

[Perl] CentOS8 に plenv をインストール
インストール Step1 事前準備 Step2 PATHを通す (README通りにインストール) Step2 PATHを通す ($HOME以外にplenvをインストール) Step3 Perlインストール Step4 cpanmインストール CentOS…

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

Tags

Dates

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