アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 - Qiita
こんにちは、大学 1 年生になったばかりの E869120 です。 私は競技プログラミングが趣味で、AtCoder や日本情報オリンピックなどに出場しています。ちなみに、2021 年 4 月 7 日現在、AtCoder では赤（レッドコーダー）です。 本記事では、アルゴリズムの学習や競技プログラミングで使える数学的な部分を総整理し、それらについて解説したいと思います。前編・中編では数学的知識、後編（2021/4/26 公開予定）では数学的考察の側面から書いていきます。 【シリーズ】 アルゴリズム・AtCoder のための数学【前編：数学的知識編①】 ← 本記事 アルゴリズム・AtCoder のための数学【中編：数学的知識編②】 アルゴリズム・AtCoder のための数学【後編：数学的考察編】 1. はじめに 21 世紀も中盤に入り、情報化社会（いわゆる「IT 化」）が急激に進行していく中、
本当に役立つFAQ検索システムを目指して - Nota TechConf
Nota Tech Conf 2021 Spring 3日目の発表資料です 2021/3/11 こんばんは daiizdaiiz.iconです Helpfeelの検索技術の話をします 開発、運用チーム プロダクトオーナー daiiz.icon プロジェクトマネージャー akix.icon Webディレクター akix.icon など テクニカルライター カスタマーサクセス エンジニア、デザイナー rakusai.iconakix.icondaiiz.iconshokai.icontakeru.iconTiro.icon 予測検索 Helpfeel CTO /masui/増井俊之.iconの展開ヘルプをベースとするFAQ検索システム PayPayフリマ様 FAQ テキパキと高速に検索できている クエリの表現に合わせて柔軟に結果が提示される Agenda いかにして探すか 1. 入力に対して遅
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
ワーシャルフロイド 入門 - TechFULの中の人
こんにちは！ganariyaです。 今回はグラフ理論のアルゴリズム、「ワーシャルフロイド」についてです。 実世界において、グラフ理論はあらゆるところで利用されます。 例えば、インターネットにおける通信パスや、JRなどの電車の経路パス探索です。 これらはグラフ理論を発展させて、実務的に使用しているものです。 グラフ理論は殆ど、駅などをノード、道路などをエッジとして扱い、点と線が結ばれたものとして扱われます。 グラフのキホン（1）グラフ概要編やグラフのキホン（2）表現方法と探索編の記事を読むとグラフの基礎が身につくと思います。 そして、グラフ理論で扱われる大きなジャンルの一つには、最短経路問題というものがあります。 これは、与えられたグラフの2つのノード間の最小のコストの経路を見つけるというものです。 例えば、以下のようなグラフがあったとします。 グラフ 以上のようなグラフで、始点から終点まで
動的計画法（ナップサック問題） - アルゴリズム講習会
動的計画法（ナップサック問題） 動的計画法とナップサック問題について解説します。 動的計画法とは 直接計算すると大きな時間がかかってしまう問題に対し、途中の計算結果をうまく再利用することで計算効率を上げる手法のこと。 「途中の計算結果を再利用」＝「同じ計算をしない」ということ 難しいように見えて考え方自体は単純 ICPC国内予選でもC問題～F問題くらいに何かしらの形で2,3題ほどでます 英語では「Dynamic Programming」と呼び、略して「DP」と呼ぶことが多いです。 動的計画法で効率的に解ける問題の一つに、ナップサック問題というものがあります。 ナップサック問題 ナップサック問題は、価値と重さが決まっている複数の品物を容量が一定のナップサックに詰め込むとき、ナップサックに詰め込める品物の価値の和の最大値は何であるか？ という問題です。 具体的には、以下の図のようになります。ナ
エレベータープログラミングしてみた - RAKUS Developers Blog | ラクス エンジニアブログ
こんにちは、fuj_takです。 エレベーターがなかなか来なくてもやもやすることありませんか？ かく言う私もエレベーター待ちになると、いつ来るんだろうと悩まされます。 自分にエレベーターの制御をやらせれば、もっといい感じにできる 皆さんも一度は考えた事があるのではないでしょうか！ そんなあなたにこちらをご紹介します。 Elevator Saga Elevator Saga - the elevator programming game GitHubにも公開されています。 GitHub - magwo/elevatorsaga: The elevator programming game! ※私の環境だとIEでうまく画面表示できなかったので、Chromeなどのブラウザでお試しください プログラミング内容 ブラウザ上でJavaScriptのコードを記述し、エレベーターの操作を行います。 エレベ
競技プログラミングを趣味にしよう
競技プログラミングを趣味にしよう この記事はtraP Advent Calendar 2016の22日目の記事です。ドカベントカレンダー こんにちは。nariです。競技プログラミングではrickythetaと名乗っていたりします。 今年も去年同様、競技プログラミングに関する記事を書きます。traPは競技プログラミングサークルですからね[要出典]。 対象読者 先に読者の厳選をしておきます。この記事は競技プログラミングを始めたはいいものの、なかなか実力が上がってこないという人を対象としています。 競技プログラミングを始めようとしている人は、他の競技プログラミング入門系の記事を読んでから来ることをおすすめします。 蛇足ですが、最近ではAtCoder社が初心者向けコンテンツを開発中らしいです。期待が高まります。 AtCoderのプログラミング入門教材 AtCoder Programming Gui
尺取法についてのあれこれ - kira924ageの雑記帳
はじめに 尺取法というものを知った。 尺取法の概要 JOI用語集によると、 配列に対して二つのインデックスを持ち、条件に応じて片方を進める操作を繰り返すことで答えを得る方法のこと。尺取虫の動きにちなんで名付けられた。DPの一種ともとれる。またキューの実装も尺取法の一種である。 とのこと。 例えば、AtCoder Regular Contest 022のB問題はこの尺取法を使って解くことができる。 問題の概要 問題文 高橋君は細長いお菓子を持っています。このお菓子は Ncm の長さのお菓子で、 1cm ごとにブロックに分かれています。それぞれのブロックには 種類の味うちのいずれかの味がついていて、左端から i 番目のブロックには 番目の味がついています。 高橋君はこのお菓子から、出来るだけ長い「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」を切り出したいと思っています。最
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜 - Qiita
はじめに はじめまして。 NTTデータ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 C や C++ を使用しているとしばしばビット演算を行う場面が出て来ます。 計算機リソースが限られている状況では、ビットを用いることでデータ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがあります。 本記事では、ビット演算を用いて実現できる処理について、簡単なものから高度なものまで集大成します。極力わかりやすく頑張って執筆しました。特に前半 4 つはビットの説明の中でもかなりわかりやすい方だと思います。後半の 7 つのテーマは比較的高度なアルゴリズムの話題ですので、フラグ管理やマスクビットについて詳しく学びたい方は前半 4 つを中心に読んでいただいて、後半 6 つは必要に応じて読んでいただければと思います。反対にビットの知識はあってビットを用いたアルゴリズ
AtCoder 版！蟻本 (初級編) - Qiita
0 はじめに プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほとんどすべて POJ 上の問題です) を AtCoder 上でジャッジできる問題に対応付けようという試みです。今回は初級編を扱い、中級編、上級編は別記事に続きます。AtCoder 上で見つからなかったものは AOJ, yukicoder 上の問題も載せています
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
