コーディングインタビューの対策とその意義 (2/2)：インタビュー本番中に何を考えるか - 16bitのメモランダム
前回の記事（下のリンクを参照）では、コーディングインタビュー前日までに役立つ知識とインタビューの意義を考察した。 en9.hatenablog.com この記事では、コーディングインタビュー当日の思考過程について考えてみる。 コーディングインタビュー最中の思考 あなたがGoogleやFacebookといった、競争の激しいテック企業のコーディングインタビューを受ける状況を想像してほしい。 何ヶ月にも及ぶ練習を乗り越え、準備は万端だ。 だが、面接官が問題の設定を説明し始めると、自分の鼓動が速まっていくのを感じる。 なんてことだ、今までやったことない問題だ。 あれだけ解いたのに。 いったいどうアプローチすればよいのだろう？ どのデータ構造を使えば解けるのかも分からない。 動的計画法のような気も、単なる分割統治法の気もする。 それともgreedyに解けるのか？ どんな境界例が考えられるのか頭に思い
Atcoder ABC32 D - ナップザック問題を分岐限定法で爆速で解く - Qiita
概要 ナップザック問題を分岐限定法で爆速（$n<2000, v_i<10^{12}, w_i<10^{12}$を$1$秒）で解きます。実行時間ベースで今のところ3位です。提出はこちら これは競技プログラミング 解説 Advent Calendar 2017の16日目の記事です。 ナップザック問題 ナップザック問題とは、重さ制約$W$と$n$個の荷物価値ペア($v_i, w_i$)が与えられて、$\displaystyle \max_{S \in 2^n, \sum_S w_i \le W} \sum_S v_i$を求める問題です。Atcoder ABC 32 - D - ナップザック問題は、様々な$n$, $v_i$, $w_i$の制約のもとで、この問題を解くという趣旨でした。 この問題は、以下の3つのDP解を、テストケースごとに作成することで通すことができます（提出）。 (1) $n$が
Splay Treeの可視化Webページを簡易的に作った - 日々ｄｒｄｒする人のメモ
この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。 adventar.org 今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。 はじめに Splay Treeとは? bottom-up top-down visualizationの実装 参考 はじめに 最近、Splay Treeがぬるぬる動く様子を眺めて癒やされたい(?)、という気持ちになり自作したくなったのでさくっと作りました。 作成期間はこのアドベントカレンダー記事を書こうとしてからの直近1週間です。 Splay Treeとは? スプレー木 - Wikipedia Splay tree - Wikipedia 平衝二分探索木の1つであり、参照したノードを回転しながらrootに持ってくるsplay操作によって平衝を保つ。 splay操作では zig,
ゲーム理論の講義ノート
結構頑張って作ってるのに授業用ウェブサイトに置いているだけではあまり読まれることもなさそうなので，授業で作った資料の中で公開することに多少の価値がありそうなものについては定期的にこちらで公開してみることにします． 授業に関するよりup-to-dateな情報や資料は私のteaching関係websiteをご覧ください． Advanced Microeconomics II の講義ノート（英語）（2019/12/04掲載） 西南財経大学の大学院向けのミクロ経済学の授業でゲーム理論を教えるにあたって作成した講義資料です（授業ではノートのメインな部分はほとんどカバーしていますが，いくつかの理論的なトピックはスキップしています）．理論研究自体というよりも，実証・応用研究の研究者になることを目指す学生にどのように動機づけを与えるか，そして「理論の人たちの興味」がどのように応用に結びついているかをなんと
Proximity search：列挙アルゴリズムの新たな構築手法 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Proximity search：列挙アルゴリズムの新たな構築手法 本記事は「データ構造とアルゴリズム Advent Calendar 2019」３日目の記事です． 2 日目は @yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です． 4 日目は @ygussanyさんによる「群ラベル制約付き最短路問題」です． この記事の元ネタは，STOC 2019で発表されたProximity searchに関する論文です．証明等に関しては省略します．詳しく知りたい方は下記文献にあたってください．また，グラフアルゴリズムにおけ
データ構造とアルゴリズム - Qiita Advent Calendar 2019 - Qiita
データ構造とアルゴリズムに関する話題なら何でもOKです。 メジャーなものからマイナーなものまで様々なトピックを好きなように書きましょう！ カレンダーの愛称は「デーアルアドカレ」でお願いします！ 関連： 以下は「文字列アルゴリズム Advent Calendar」を含みますが、実態は何でもありで様々なデータ構造とアルゴリズムが紹介されています。 文字列アルゴリズム Advent Calendar 2016 - Qiita 文字列アルゴリズム Advent Calendar 2017 - Qiita データ構造とアルゴリズム Advent Calendar 2018 - Qiita データ構造とアルゴリズム #2 Advent Calendar 2018 - Qiita
Sliding Window Aggregation - data-structures
#Sequences Operations 半群の列 を扱う． 空間計算量 空の状態でデータ構造を作成する 時間計算量 を計算する 時間計算量 を末尾に追加する 時間計算量 を削除する 時間計算量 Summary Queue をつの Stack でシミュレートする技法を用いる それぞれの Stack は要素の他に、最初の要素からその位置までの累積和も管理する 先頭側の Stack 全体と末尾側の Stack 全体の fold 結果はわかっているので，それらを結合すればに答えられる 先頭側の Stack が空でないとき，単に先頭側の Stack を pop する 先頭側の Stack が空になった際に末尾側の Stack の全要素を反転して先頭にする この操作にはかかるが，つの要素が Stack に される回数を考えると償却定数時間になることが言える． References Knapsack
Runの列挙 (Main-Lorentz algorithm) - 迷いませんか？
Main-Lorentz Algorithm 概要 文字列のrunをで列挙することができるアルゴリズム runは文字列内に現れる部分文字列の繰り返しのことで、特に長さが極大で周期が最小のものを指すっぽい 情報としては区間と周期を持ち、実際に使うときは(l, r, period)としてs[l, r)の周期がperiodみたいに持つ 注意するべきなのは、繰り返しはピッタリである必要はなくて(r - l) % period != 0でもよい ただしr - l >= 2*periodであるもののみを考える 例 "mississippi" 区間: [1, 8), period: 3 長さ3の"iss"が7/3周期分ある s[0] != s[0+period(= 3)] かつ s[8] != s[8-period(= 5)]だからこれ以上伸ばせなくて長さが極大である あとは周期1で2周期分のやつが3つ
External memory algorithm - Wikipedia
In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such as hard drives or tape drives, or when memory is on a computer network.[1][2] External memory alg
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
素数テーブルをO(n)で構築する - 裏紙
からまでの数が素数であるかどうかの配列(素数テーブル)をで構築する。 はじめに まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、で構築できます。実装も素直で簡単です： const int N = 10000001; bool prime[N]; void build_sieve(){ fill(prime,prime+N,true); prime[0] = prime[1] = false; for(int i=2; i<N; ++i)if(prime[i]){ for(int j=2*i; j<N; j+=i) prime[j] = false; } } 実装 次にの実装を見てみます。 const int N = 10000001; int mind[N]; vector<int> pr; void b
LCAをベースに構築するAuxiliary Treeのメモ - 日々ｄｒｄｒする人のメモ
(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。 最近、LCAを元に構築する Auxiliary Tree を使う問題に出会ったので書いた。 CodeChef July Challenge 2019 で以下の問題があった。 smijake3.hatenablog.com 自分は Auxiliary Tree を使わず解いたが、想定解法が Binarization of a tree + Centroid Decomposition on Edge + Auxiliary Tree だったらしい。 discuss.codechef.com 以下を参考にしている。 虚树学习笔记 -
競プロのための高速フーリエ変換
■「フーリエ変換って知ってる？」 ●「フーリエ変換ですか？ 信号処理でもするんですか、先輩」 ■「いや、競プロで使えるようになりたいなって」 ●「ああ、畳み込みの高速化ですか。あれは高速フーリエ変換をそのまま使うだけですからね」 ■「勉強しようと思って色々調べたんだけど、なかなか理解できなくて」 ●「私もうまく説明できるかわかりませんが、お話しましょうか」 離散フーリエ変換（DFT） フーリエ変換の仲間たち ●「フーリエ変換の仲間には色々種類があるんですけど、競プロで使うのは離散フーリエ変換（DFT: Discrete Fourier Transform）ですね」 ■「離散ってことは、連続もあるんだよね」 ●「はい。ざっくり 4 種類あります。フーリエ変換では元の信号を別の信号に変換するんですが、元の信号が周期信号だと変換後は離散信号（数列）になります」 ■「周期信号っていうのは、決まった
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Private Presentation
pakencamp_slide.pdf
AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法
Data Structure for Disjoint Sets
10秒で衝突するUUIDの作り方
近似最近傍探索の最前線
