1742 -- Coins POJ1742を解こうとしたが、蟻本P.62の「個数制限付き部分和問題」とほぼ同じだった。 この問題の漸化式の作り方が難しかったので、ここで整理しておく。以下、蟻本P.62-63を参考に書いた。 蟻本：プログラミングコンテストチャレンジブック […

プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ いわゆる「蟻本」である。この章末で紹介されている練習問題をひたすら解いている。 今回は基礎的な動的計画法。基礎的といっても最後…

プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ この本の章末で紹介されている練習問題を解いている。貪欲法（その他）だ。 貪欲法とはいっても、この問題群は要素を選ぶ順番をうまく…

プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ この本の章末で紹介されている練習問題をひたすら解いている。解説だけでなくテーマに沿った類題も豊富に紹介してくれているのがこの…

プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ この本の章末で紹介されている練習問題をひたすら解いている。 競技プログラミングの世界で通用するような人は、最低でも1000題は解い…

幅優先探索が使える問題 「プログラミングコンテストチャレンジブック」第２版（マイナビ）の章末(p.125)で紹介されている練習問題を淡々と解いている。 こういう基本的なアルゴリズムは問題を見たら手が勝手に動くくらいに練習しないと。幅優先探索が使える…

「プログラミングコンテストチャレンジブック」第２版（マイナビ）の章末で紹介されている練習問題を解いて競技プログラミングの練習をしている。今回は「深さ優先探索」（p.125）を4題。深さ優先探索が使える問題の特徴は、 1. 片っ端から全探索してもあま…

以下のコードでは、URLが404 Not Foundのときにエラーになって止まる。 require 'open-uri' url = 'http://example.com' html = open(url) do |f| f.read end URLを開けなかったら例外OpenURI::HTTPErrorを投げてくれるので、ちゃんと捕捉する。 require 'op…

今すぐ始めるスクレイピング nokogiriとかのスクレイピング用ライブラリを使わずに標準ライブラリ'open-uri'だけでスクレイピングをします。HTMLソースを取得するだけならこれで十分。以下のサイトを参考にスクレイピングしたいサイトのHTMLソースをまるごと…

はてな記法に慣れたいのでメモ 見出し *見出し 小見出し **小見出し 小小見出し ***小小見出し リスト1 リスト2 リスト3 -リスト1 -リスト2 -リスト3 定義リスト 定義リスト :定義リスト:定義リスト 表 表 表 |*表|表|表| ソースコードの表示 class Foo def …