競技プログラミング特有の変な実装テク - ichyo.jp
初めに この記事はCompetitive Programming Advent Calendar 2014の15日目の記事です． 競技プログラミングでは，アルゴリズムをひらめく力や，数学やアルゴリズムの知識量などが強さを決める大きな要素ではありますが， もちろん，プログラミングを使った競技である以上は，コードの実装力が勝敗を分けることもあります． 例えば，ICPC系のコンテストでは，アルゴリズムを考える能力よりも，実装量の多いプログラムをいかにバグなく高速に実装するかが重要な 問題セットが与えられることが時々あります． 競技プログラミングと無縁なプログラマーは，実装力と聞くと， クラスの構造をうまく設計したり，変更に強い美しいコードを実装する能力だと想像する人がいるかもしれません． ですが，プログラミングコンテストに必要な実装力は，そうした保守性や拡張性ではなく， 「目的の処理をシンプルな
実行時間の差は996倍以上。オンラインハッカソン最速コードの裏側に迫る！ - paiza times
2013年12月2日より2014年1月8日まで開催していたpaizaオンラインハッカソン（略してPOH![ポー！]）Vol.1「新人女子の書いたコードを直すだけの簡単なお仕事です！」で0.01秒を叩き出したコード(最遅コードとの差は最大996倍！ 詳しくは結果発表をご確認ください)はどんな過程で生み出されたのでしょうか？ 今回は前回の最速コード発表レポート（【結果発表】新人女子PGを最も助けたプログラミング言語とは？）に引き続き、最速コードの裏側に迫ります。 ※ちなみにこちらの野田ちゃん画像は、2014年1月17日に開催されたエンジニアサポートcross2014というイベントで等身大パネルとしてpaizaブースを盛り上げてくれました！ ■高速化のアプローチ 前回のレポートでもふれましたが、POH Vol.1はアルゴリズムに変更による計算量(オーダー)の改善による大幅な高速化と、定数倍高速化
技術/歴史/zip,gzip,zlib,bzip2 - Glamenv-Septzen.net
id: 495 所有者: msakamoto-sf 作成日: 2009-11-22 17:11:47 カテゴリ: Linux UNIX Windows [ Prev ] [ Next ] [ 技術 ] お仕事絡みで、ZIPファイルの歴史が気になったので調べてみた。 前々から何となく「gzipとzlibとzipってどう違うんだろう」とは思っていたのだけれど、WindowsでLhacaやLhaplusなどのアーカイブソフト、あるいはXP以降ならOSの機能としてデフォルトでzip圧縮できるし、Linux/UNIXでも2-3回コマンドラインオプションを試行錯誤してmanページ見ればtar.gz作ったり逆にWindows上で圧縮したzipを適当に解凍できるので「ま、いっか。」で済ませてた。 でもせっかくなので、技術的な詳細には突っ込まないが、ざっくりとした歴史や流れをWikipediaを中心に追って
SmartNewsを支える機械学習
ニュースアプリSmartNews(https://www.smartnews.be/)の背景のアルゴリズムについてTokyoWebMining30th(http://tokyowebmining30.eventbrite.com/)で話させていただいた際の資料です。 •SmartNews iphone版: https://itunes.apple.com/jp/app/id579581125 •SmartNews Android版 https://play.google.com/store/apps/details?id=jp.gocro.smartnews.android •SmartNews開発者ブログ http://developer.smartnews.be/blog/Read less
Googleの新しい圧縮アルゴリズムZopfliについて調べた。 - EchizenBlog-Zwei
Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。 Compress data more densely with Zopfli - Google Developers Blog deflateアルゴリズム zopfliはdeflateアルゴリズムに基づいた圧縮ライブラリ。deflateアルゴリズムはデータをLZSSというLZ77を改良した圧縮法で圧縮し、その後ハフマン符号で符号化したもの。 deflateアルゴリズムの実装としてはzlibやgzipがある。zlibとgzipの違いはヘッダとフッタの持っている情報。 使ってみる googlecode(http://code.google.com/p/zopfli/)から取ってくる。 $$ git clone https://code.google.com/p/zopfli/ $$ cd zopfli $$ ma
計量学習を用いた画像検索エンジンとアニメ顔類似検索v3について - デー
まだgithubにはpushしていないのですが、さいきょうの組み込み型画像検索エンジンotamaに計量学習を用いて与えられたデータにあった画像間の距離関数を学習してそれを使って検索するというドライバを入れたので、先行的なデモとしてアニメ顔類似検索v3を作ってみました。 計量学習は、ベクトル間の距離の計り方を機械学習で決めるみたいな分野です。 アニメ顔類似検索v3 AnimeFace Search v3 - Otama LMCA_VLAD_HSV Driver randomボタンを押すと顔画像がランダムに出るのでどれかクリックするとそれをクエリに検索します。color weightは色の重みを調節するパラメーターで、1にすると色だけで検索します。0にすると形状やテクスチャだけで検索します。結果画像の上の数字は類似度的なもので、その横のgglは元画像をGoogle Search by Imag
フィボナッチで各種言語をベンチマーク - satosystemsの日記
AWK、Ada、Bash、Boo、C、C#、C++、Clojure、D、Erlang、Forth、Fortran、Go、Groovy、Haskell、Io、Java、JavaScript、Lisp、Lua、OCaml、Objective-C、PHP、Pascal、Perl、Pike、Prolog、Python、R、Ruby、Scala、Scheme、Smalltalk、Tcl でフィボナッチ数を求める処理時間を計測してみました。 フィボナッチ数は漸化式で求められます。 F0 = 0 F1 = 1 Fn+2 = Fn+1 + Fn フィボナッチ数を求めるアルゴリズムはいろいろありますが、今回は以下の再帰で求めるアルゴリズムで統一しました。 #include <stdio.h> int fib(int n) { if (n < 2) return n; return fib(n - 2) +
全国高等専門学校プログラミングコンテスト有明大会 - natrium's reminder
第23回全国高専プログラミングコンテスト・有明大会に、競技部門のメンバーとして@nikollson、@HETARE09と参加してきました！ 結果は… 一回戦4位/6チーム→敗者復活戦4位/6チームでしたorz（通過出来るのはいずれも上位2チーム） 問題内容 大・中・小3種類の大きさのサイコロが、テーブル上に沢山あります。サイコロ以外の物もあります。全体のサイコロの重さも教えます。それぞれの大きさのサイコロがいくつあるのか頑張って数えてね！ というルールです。 超端折りましたが、詳細なルールはこちら(PDF)の7ページ以降に書いてあります。興味が有る方は御覧ください。 あと割と大事なQ&Aで、こういうのもあります。サイコロは自然に散らべ、手で並べたりはしないらしい。 例えばこんな感じです。（クリックすると拡大します） 取り組んだこと 4月 問題が公開される。絶望する。 というのは置いておいて
Ｃ言語講座：リスト型のデータ構造
サイトマップ / Ｃ言語講座＞出入り口＞総目次＞目次：ヒープ領域＞リスト型のデータ構造 リスト型のデータ構造 [分割コンパイル]←このソース→[ハッシュテーブル] /* プログラムが起動するとメモリアドレスの小さい方から順に、コードセグメント、データセグメント、そしてプログラム実行時に必要に応じて、動的にメモリが確保されるヒープ領域が取られます。 ヒープ領域にメモリが確保されるのは、例えば、calloc( ) や malloc( ) の呼び出し時です。 */ /* スタック */ /* これとは別に、上記のメモリと不連続に、上位のメモリから下位のメモリに向けて、スタックという領域がとられます。関数を呼び出すと、スタックに戻り場所や変数の値を ( 引数 ) を積んで制御が関数に移ります。呼ばれた関数はスタックから値を取り込みます ( Call by value )。 関数の再帰的呼び出しでは
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)
partake.in