noyのブログ

プログラミングとかゲームとか

アルゴリズム

AtCoder Beginner Contest D問題ジャンル分け

imos法 D: 感雨時刻の整理 - AtCoder Beginner Contest 001 | AtCoder 全探索 D: 派閥 - AtCoder Beginner Contest 002 | AtCoder D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder D: 語呂合わせ - AtCoder Beginner Contest 031 | AtCoder D…

ABC009 - D 漸化式

D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder 問題概要 二つの数列 と が入力で与えられる。数列 A は以下の式によって計算できる。 数列 A の M 番目の値を求めよ。 解き方 漸化式を計算するには、DPを使えば良いです。しかし、制約が大きく、DPで…

ABC025D - 25個の整数

D: 25個の整数 - AtCoder Beginner Contest 025 | AtCoder 解説を見て実装を放置していたため、考察要素はないです。 問題概要 5 * 5 のマスがあります。 1 ~ 25 までの数値を、各マスに一つずつ書きます。 ただし、以下の条件を満たすように書かなければい…

AOJ 0553 ダンジョンの解説

AOJ 0553 ダンジョン ダンジョン | Aizu Online Judge 考察 問題点 あり本にある優先度キューを用いたガソリン問題と似ています。 ただし、こちらの問題では、ガソリンを入れられる量の上限があります。体力が0以下になる前に、どこかで回復しなければいけな…

Binary Indexed Tree(BIT)を学ぶ(1)

BITとはなんぞや POJ1990 MooFest 解法 コード 参考 BITとはなんぞや 参考:蟻本159頁列a_1, a_2, ... , a_nがある。 iが与えられたとき、a_1からa_iまでの和を求める。 (iとjが与えられたとき、a_iからa_jまでの和を求める。) iとxが与えられたとき、 a_i +…

C++ 素数を求める2種類の方法

素数を求める方法 ひとつ目は愚直な割り算の繰り返し。ふたつ目はエラトステネスのふるい。割り算を繰り返せば、どんな素数でも求められる。しかし、多くの数を素数か判定するのには遅すぎる。 エラトステネスさえ覚えれば、多くの素数問題は攻略できる。し…