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/

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

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

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

関連記事

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…

bit全探索で動的計画法を実装する JavaScript
サンプル1 サンプル2 参考 AtCoderとかをやっていると、 動的計画法(DP)、部分和といった問題とかに遭遇したりしますが、…

ブラウザで動くAtCoder用のデバッガを作ってみた (JSのみ)
AtCoder-JsDebugger 説明 フレームワーク、ライブラリなど ブラウザで完結するAtCoder用のデバッガを作ってみました。 対応言語は(JS)のみになっています。 というのも、書いたコードをブラウザ上でeval…

深さ優先探索アルゴリズムを実装 部分和問題を解く
深さ優先探索について 部分和問題を解いてみる 問題 サンプルコード デバッグ おまけ : 2進数を利用して 深さ優先探索について 深さ優先探索(depth-first search)は探索手法の一つです。 DFS、バックトラック法とも呼ばれます。 探索する木の…

素因数分解を行うプログラム サンプルコード JS/PHP
サンプルコード JavaScript PHP ある任意の正の整数の素因数を配列で返すサンプルコードを紹介します。 サンプルコード JavaScript パターン1 : 純粋な素因数分解 デバッグ パターン2 : 指数部と仮数部に分ける デバッグ PHP

【AtCoder】ABCで初めてC問題が解けました。【ABC114】
はじめに AtCoderについて はじめてC問題が解けました C問題を解いた時のパフォーマンス おまけ:解いた問題 C - 755 問題 計算例 回答ソース JavaScript おまけ2 はじめに AtCoderについて http://osrehun…

AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
はじめに 初めての参加 3回目くらいで雰囲気を掴む 苦戦した原因 レートの上がり方について 各問題の内容と必要になる思った知識 - ABCの場合 ツール レート感の話 — s-yoshiki | スクリプトカス (@syoshikidev) 2018年11月2…

最新の投稿

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