しばらく忙しくて,更新が途絶えてしまいました. 少なくとも今年度中は,2週間に1回更新を続けていきたいです. 本題. 競技プログラミングで,ダイクストラアルゴリズムを実装する機会があったので,ソースコードを載せておきます. ダイクストラアルゴリズムとは? ダイクストラアルゴリズム(ダイクストラ法)とは,重み付きグラフの探索アルゴリズムの一種で,すべての辺の重みが非負なグラフの単一始点最短経路問題を解くためのアルゴリズムです. グラフの始点が与えられた時,そこから他の(すべての)頂点までの最短経路と,そこまでの重みの和(最短距離)を求めることができます. ダイクストラ法 - Wikipedia ナイーブなダイクストラアルゴリズムはO(|V|^2)ですが,プライオリティキュー(優先度付きキュー)と呼ばれるデータ構造を用いることで,O(|E|log|V|)程度で最短経路を求められます. 優先度つ
まえがき 使ってるもの クラウド 言語 アーキテクチャ やったことを簡潔に お金がやばくなる 無料運用する方法をググってみる 自分でapp.yamlを書いてみる お金が減り続ける お金が減り続ける2 GAEの動作環境 スタンダード環境を試してみる Future Contestをスタンダード環境に切り替える 定期的に更新する その他 AtCoderのAPIサーバーを立てる ページがプレーンテキストとして表示される ページが更新されない 結果 感想 これから まえがき Future Contestとは?→これ 初めてWebサイト作ってみたで作ったサイトを無料運用にしたのでログを取っておく。 ただのメモなので技術的なことは詳しく書いてない 時系列順に書いてく たぶんめっちゃアホみたいなことやってる 使ってるもの クラウド GAE 言語 Go アーキテクチャ 最終的には以下のようなアーキテクチャに
今回は素集合データ構造であるUnion-Find木に重みを付けた、Weighted(重み付き) Union-Find木についてまとめます。 Union-Find木についてよくわからないという方は、 at274.hatenablog.com こちらを先に見ていただいた方がいいかと思います。 Weighted Union-Find木について Pythonによる実装 準備 検索(find) 併合(union) 完成形 Weighted Union-Find木について 実装前に、Weighted Union-Findがどんなものかざっくり説明しておきましょう。 まずはイメージ図を見てやってください。 特に深い説明はいらないかと思います。 イメージ図通りです。 例えば、「AさんはBさんより3歳年上。CさんはBさんより2つ下。ではAさんはCさんよりいくつ上?(もしくは下?)」みたいな問題に対して使えま
はじめに 標準入力 input と sys.stdin.readline ソート sort と sorted ソートの key ループ for と while リスト リストの初期化 二次元配列の場合 リストの値参照 リストへの値追加 それぞれの処理速度 まとめ はじめに 最近、PythonでAtCoderなどの競技プログラミングに挑戦しています。これまであまりに気にしなかったけど、ちょっとした書き方で処理速度が変わってくることに気づいたので、これを気に少し調べてみました。 目次にあるように、標準入力、ソート、ループ、リストについて、計8個の処理の速度比較を行いました。処理速度の計測方法は、Mac Book Pro*1を使い、timeitでそれぞれ100回計測*2し、平均と標準偏差を求めています。 結果だけ知りたい方は、まとめへどうぞ。 計測に用いたコードは以下にあります。 github.
@Morinikki様のPythonでREST APIをサクっと実装 を参考にさせていただき、GETを実装。 エンドポイントの作り方がわかったので、同様にPOST、PUT、DELETEを生やし、peeweeのドキュメントを読みながら実装しました。 # -*- coding: utf-8 -*- from flask import Flask, jsonify, abort, make_response, request import peewee as pe import random import json # ランダム文字列 def random_string(length, seq='0123456789abcdefghijklmnopqrstuvwxyz'): sr = random.SystemRandom() return ''.join([sr.choice(seq) for
TOP マガジン イベント 【レポート】デジタルマーケティングから紐解き、マーケティングをもういちど考える:デジタルマーケティング[第1部] - TECH PLAY Conference 2017 【レポート】デジタルマーケティングから紐解き、マーケティングをもういちど考える:デジタルマーケティング[第1部] - TECH PLAY Conference 2017 2017年8月20日(日)から25日(金)の6日間にわたり、「TECH PLAY Conference 2017」が開催されました。 本レポートでは、8月23(火)12時よりスタートした第4日目の「デジタルマーケティング」のうち、第1部「デジタルマーケティングから紐解き、マーケティングをもういちど考える」の内容をお届けします。 第1部は、花王の石井さんによる基調講演です。それでは内容をご紹介します! 「マス」の消滅。 石井龍夫(
特集記事「SNSバズ百景 ――『RT』&『いいね』時代のクリエイション100」が、本日7月6日発売の『MdN2018年8月号』に掲載されている。 同特集では、プライベートな体験を描いたレポート漫画や、アイデアを形にした造形物、プロが仕事の息抜きに描いたイラストなどがSNS上で瞬時に受け手に届き、消えていく環境を「SNSバズ百景」と名付け、イラスト、漫画、造形物、グラフィックなど100点を掲載。虎硬による「SNS時代のイラストレーションの動向」「VTuberの流れ、そして鳩羽つぐという存在」、編集部による「『いらすとや』の魅力をSNS上から探る」といった記事や、表紙を飾るバーチャルYouTuber鳩羽つぐの「自撮り写真」が収録される。 特集外では、齋藤優一郎(スタジオ地図)と西村義明(スタジオポノック)の対談や、VIDEOTAPEMUSIC、イラストレーターの「絵を描くPETER」らを紹介。
概要 ナイーブベイズ分類器(ベイジアンフィルター)のアルゴリズムを具体的な数値を使って説明します。また、Pythonで実装してみました。自分の勉強メモのつもりで書いたのですが、他の方の役にも立てたら嬉しいです。 ナイーブベイズ分類器って? あるデータ(文章)をどのカテゴリーに属するのかを判定させる、機械学習の教師あり学習の手法の一つです。 スパムメールフィルターやWEBニュース記事のカテゴライズによく使われています。 難易度 ベイズの定理を利用した単純な手法で、難易度は低です。 なるべく数式を使わないで説明してみました。 ナイーブベイズ分類器の計算 対象文章がどのカテゴリーに分類されるかを決めるための計算ロジックを、具体的な数値を使って説明します。 学習データが以下である場合、対象文章がどのカテゴリーに分類されるか計算します。 学習データ サッカー [ ボール | スポーツ | ワールド
This domain may be for sale!
本記事を終えた次は? AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版!蟻本 (初級編) AtCoder 版!蟻本 (中級編) AtCoder 版!蟻本 (上級編) AtCoder 版!蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える!アルゴリズムとデータ構造 (通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト
現在、Twitterの「#ネームタグ」ハッシュタグなどで、「この写真をストーリーズカメラで開くと○○さんをフォローできます」という画像が多数投稿されています。 しかしこの「ストーリーズカメラで開くと」という指示の意味や使い方が分からないユーザーが多数発生してしまっている模様です。 この画像の意味について紹介します。 目次 1. 「この写真をストーリーズカメラで開くと○○さんをフォローできます」画像2. ネームタグ機能の画像3. 「ストーリーズカメラで開く」のやり方4. スマホで表示したネームタグ画像(Twitterでシェアされている画像・ダウンロードした画像)の読み込み方は? スポンサーリンク 「この写真をストーリーズカメラで開くと○○さんをフォローできます」画像 現在、投稿するユーザーが増えているのは、次のような画像です: この写真をストーリーズカメラで開くと○○さんををフォローできます
このサイトについて このサイトのモットーは「ビットコインの仕組みは決して難しくない」です。 このサイトは、技術的にビットコインを解説するサイトです。簡単な説明から入り、最後は、ウォレットをRubyで実装します。しかし、プログラミングに慣れていない方にも、十分に理解できるようよう配慮しました。 私は、多くの人が容易に理解できるからこそ、ビットコインは価値ある発明だと思っています。 ビットコインの簡単な仕組み ビットコインは、中央を持たないのに、銀行を経由しているかのようにコインをやりとりできる「通貨」。 「公開鍵暗号」で第三者がコインを勝手に盗めなくなり、 「ブロックチェーン」のしくみで、当事者が通貨を二重に譲渡するのを防ぐことができる。 「ブロックチェーン」の運営に貢献した人は報酬がもらえる、これが「マイニング」。 これだけではよく分からない? はやく仕組みを知りたい:「Bitcoinの仕
有効さ (Effectiveness): ユーザが指定された目標を達成する上での正確さ、完全性。 効率 (Efficiency): ユーザが目標を達成する際に、正確さと完全性に費やした資源。 満足度 (Satisfaction): 製品を使用する際の、不快感のなさ、および肯定的な態度。 この中の「利用状況」とは、ユーザ、仕事、装置(ハードウェア、ソフトウェア及び資材)、並びに製品が使用される物理的及び社会的環境を指しています。 ここまで読むと、なんだか「UX」と似ていませんか?! そうなんです。「UX」という言葉が広まる以前は、この「UX的な考え方」のことを「ユーザビリティ」と呼んでいました。 いまUXデザインに携わっている、歴史の長い方たちは、もともとはみんな「ユーザビリティを良くしよう」という活動を行っていました。 しかし、「使いやすさ/使い勝手だけでなく、利用状況や各局面におけるユー
この記事には広告を含む場合があります。 記事内で紹介する商品を購入することで、当サイトに売り上げの一部が還元されることがあります。 英語の分詞構文とは、現在分詞(-ing)や過去分詞(-ed)ではじまる句が、文全体に情報を付け加えるはたらきをするものを言う。 例えば、Working as an engineer, John earned a lot of money.(技術者として働き、ジョンはたくさんのお金を得た)であれば、Working as an engineer(技術者として働き)が分詞構文に該当する。 この記事では分詞構文について詳細を解説していく。学習の役に立つはずだ。 1. 分詞構文は接続詞のように情報を付け足す表現 分詞構文とはそもそも何なのか? 分詞構文はどのような場面で使うのか? 例文を使って見ていきたい。 (1) Watching the movie, I remem
All in Slack いまさらですが Slack を使い始めました。チャット用途ではなく、RSS 読むためだけに Feedly 開くの面倒だから何とかしたいというのと、モヒカン Slack に入ったらなかなかよかったためです。 究極のIT系最新技術情報収集用Slackチーム公開 - モヒカンSlack - - Qiita そういえば Twitter も全然開かないし会社の SNS も見なきゃいけないし Instagram は見てるヒマないしたまーに Skype 届くし GoogleCalendar の通知は毎日見逃すし、気づけばスマホにもPCにもいろいろなアプリが常駐してるしいろんなタブが開いてる。 しんどくなってきたので何でもかんでも Slack でまとめてみようと思いました。 Slack でできること・やること RSS Feed を読む、Twitter, Instagram, Ya
ホーム英語学習コラム3つのC(正確・明確・簡潔)による日英技術翻訳第3回【日英でニュアンスがずれることがある動詞<realize, expect, contribute>】 動詞の選択は、明確で力強い英文を書くために重要です。また、選択を誤ると、正しく内容を伝えられなくなってしまいます。 日本語と英語でニュアンスがずれやすい動詞があります。realizeとexpectを取り上げます。 「実現する」の英訳「realize」の何が問題? 日本語「実現する」の英訳に使われる英語の動詞realizeにまつわる問題として、次の3つが挙げられます。 ①日本語「実現する」にはプラスのニュアンスが伴いがち。一方、英語realizeは単に「現実化する」であって、動詞自体にプラスのニュアンスがあるわけではない。 ②日本語の「実現する」は多用な場面で使われ、それらすべてをrealizeで表すことが難しい。特に、
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く