asaのブログ

プログラミングの勉強まとめ

アルゴリズム

DPL_1_B ナップザック問題

ゼミの教科書に出ていてどんな問題か気になっていたナップザック問題の近似解が解けました。NP困難な問題として知られるナップザック問題ですが、貪欲法ではなく動的計画法で解くことで近似解をだすことができます。 N個の品物についてナップザックに入れる…

ALDS_10_C 最長共通部分列

今日はアルゴリズムの日。問題を複数まとめて書くとごちゃごちゃして見ずらいので問題ごとに分けて書いています。参考書はこれ。 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 作者: 渡部有隆 出版社/メーカー: マイナビ出版 発売日: 2015…

ALDS1_10_A フィボナッチ数列と動的計画法

研究でナップザック問題が出てきたので、久しぶりにアルゴリズム問題を解いています。使用している参考書は下の本です。 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 作者: 渡部有隆 出版社/メーカー: マイナビ出版 発売日: 2015/01/30 …

ALDS1_3_Aスタックの実装

参考書の続きです。大体一日一問といているような感じです。今回もC++でしか回答が載っていないので、Javaで実装しました。ほとんど参考書どおりですが、例外だけ作ってません。Publicの回答を見ると、BufferedReader使っていますが、今回はScannerクラスを…

ALDS1_2_Cの解説(安定なソート)

参考書を新しく購入しました。下の本です↓。解説がC++で書かれているので、Javaで実装しました。 プログラミングコンテスト攻略のためのアルゴリズムとデータ構造 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力) 出版社/メーカー: マイナビ 発売日: 2015/01/30 メ…

ソートアルゴリズム(クイックソート)

集合と文字列検索があっさり終わって、現在リストに入ってます。だいぶ前にやった感がありますが、クイックソートをまとめました。参考書は変わらず『明解Javaによるアルゴリズムとデータ構造』を使っています。 明解Javaによるアルゴリズムとデータ構造 作…

ソートアルゴリズム(バブルソート)

今日は、タイトルにあるソートを勉強しました。単純選択ソートとシェルソートまで進みましたが、ずらずら書くと冗長なので今回はバブルソートをまとめました。参考書は『明解javaによるアルゴリズムとデータ構造』です。 明解Javaによるアルゴリズムとデータ…

AtcorderBiginerContest056のD問題

題名の通り、この前あったAtcorderの大会のD問題を『みんなの回答』から解説してみました。公式回答とは若干違いますが、答えを導けます。 gist7379266b326379cf4829408d2982c9d4