サービス終了のお知らせ NAVERまとめは2020年9月30日をもちましてサービス終了いたしました。 約11年間、NAVERまとめをご利用・ご愛顧いただき誠にありがとうございました。
指数時間アルゴリズムというのは,NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで,できるだけ指数の底の小さいアルゴリズムを開発することが目指されています. コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが特に有名だと思います. この分野は近年盛んに研究され始め,自分も大学でこの分野を中心に研究をしています. 今回,情報オリンピック春合宿講義とPFIセミナーで発表する機会があったので,この分野の基礎的な手法から最先端の手法までをまとめてみました. 指数時間アルゴリズム入門@情報オリンピック春合宿講義 http://www.slideshare.net/wata_orz/ss-12131479 指数時間アルゴリズムの最先端(キャンセリング)@PFIセミナー http://www.slideshare.net/wata_orz/ss-12208032
1. 2012/3/20 NTTデータ駒場研修所 (情報オリンピック春合宿) プログラミングコンテストでの データ構造2 ~平衡二分探索木編~ 東京大学情報理工学系研究科 秋葉 拓哉 1 2. 自己紹介 • 秋葉 拓哉 / @iwiwi • 東京大学 情報理工学系研究科 コンピュータ科学専攻 • プログラミングコンテスト好き • プログラミングコンテストチャレンジブック 2 3. データ構造たち (もちろん他にもありますが) • 二分ヒープ • 組み込み辞書 (std::map) • Union-Find 木 初級編 • Binary Indexed Tree コンテストでの データ構造1 • セグメント木 (2010 年) • バケット法 中級編 • 平衡二分探索木 • 動的木 本講義 • (永続データ構造) 3
2012年01月16日16:30 カテゴリアルゴリズム百選Lightweight Languages Algorithm - Suffix Array を JavaScript で再発明してみた WEB+DB 総集編 [Vol. 1〜60] もう10年以上前に某社のCTOだったころ、Suffix array(接尾辞配列)の解説を毎週の技術者ミーティングでしたら一名を除いて「ハァ?」状態だったことを思い出しつつ。 Suffix Arrayは何が画期的だったのか? 以下は、計算機科学者でなくても直感的に理解できると思います。 ソートされていない通常のデータの中にあるサブデータ(キー)を検索しようとすると、データの大きさに比例した時間(O(n))がかかる。 ソート済みのデータであれば、二分探索でデータの大きさの対数時間(O(logn))でキーを検索できる。 さらにキーからIDを定数時間で作成でき
グーグルでは、社内のプログラマによって作り出される大量のコードの品質を保つため、チェックイン前にユニットテストとコードレビューが行われているそうです。しかし、コードが大量になってくると、ユニットテストやレビューをすり抜けるバグも少なからず発生します。 そこでコードの品質をさらに高めるために、グーグルでは「バグ予測アルゴリズム」を採用。バグがありそうな部分をレビュアーにアドバイスする仕組みを採用したとのこと。 そのバグ予測アルゴリズムとはどんなものなのか。Google Engineering Toolsブログに投稿されたエントリ「Bug Prediction at Google」(グーグルにおけるバグ予測)で説明されています。 ソースコードの修正履歴を基に予測 コードの中にバグがありそうな箇所を分析する手法としては、「ソフトウェアメトリクス」がよく用いられます。これはコードを静的に分析して、
効率的な別解とか存在する問題もあるけど演習によさそうなやつをピックアップ。そのアルゴリズムじゃないと解けないわけではないって問題も多いので注意。(ただ演習するのには都合が良いかなと)※個人的難易度をつけてみました。とても主観的な難易度付けなので気にせず解いてみてください。深さ優先探索・Balls[☆]・Sum of Integers[☆]・The Number of Island[☆]・Block[★]幅優先探索・Mysterious Worm[★]・Cheese[★]・Seven Puzzle[★☆]・Stray Twins[★★]・Deven-Eleven[★★]・Summer of Phyonkichi[★★☆]ワーシャルフロイド法(For 全点対最短路問題)・Traveling Alone: One-way Ticket of Youth[★]・A reward for a Car
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く