mod 1000000007 をする問題。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 正の整数 が与えられる。 を 1000000007 で割った余りを求めよ。 制約 コード #include <bits/stdc++.h> using namespace std; // a^n mod m template<class T> T mod_pow(T a, T n, T m) { T </class></bits/stdc++.h>…

グリッド上の最短経路の数え上げをする DP。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 のグリッドがあり、各マスは壁または通路である。左上マスと右下マスは通路である。 左上マスから右下マスへと、右方向と下方向の移動のみを繰り返し、…

一次元 DP で「配る DP」が書きやすい問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 マス目に と記された マスの双六がある。1 からスタートして へ進みたい。 マス からマス () に進むことができて：100pt 獲得 マス からマス () に進むこ…

ナップサック問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 宝箱には 個の品物が入っている。品物 の重さは 、価値は である。 太郎君は、いくつかの品物を選んで持ち帰りたいと考えている。しかし、彼のナップザックには容量制限があるの…

部分和問題。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 個の整数 からいくつか選んで、総和を にすることが可能かどうかを判定せよ。 制約 コード #include <bits/stdc++.h> using namespace std; int main() { int N, S; cin >> N >> S; vector<int> A(N); for</int></bits/stdc++.h>…

DP の経路復元を学ぶ問題。鉄則本の問題なのでコードのみ。 問題へのリンク 問題概要 あるダンジョンには 個の部屋があり、 と番号がついている。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができる。各通路に…

座標圧縮せよ、という問題 問題へのリンク 問題概要 長さ の数列 が与えられるので、座標圧縮せよ。 制約 考えたこと 座標圧縮は次の記事に詳しく書いた。 drken1215.hatenablog.com コード #include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; v</bits/stdc++.h>…

「答えで二分探索」のめちゃくちゃいい練習問題！ 問題へのリンク 問題概要 台のプリンターがあり、 番目のプリンターは 秒後にプリントする。 合わせて 番目のプリントが行われるのは何秒後か？ 制約 答えが 以下] 解法 鉄則本の問題なので、鉄則本参照。 1…

lower_bound() の練習！！ 問題へのリンク 問題概要 長さ の配列 が与えられる。この配列に対して 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、配列 の中に より小さい要素が何個あるかを求めよ。 制約 解法 github.com コード #include <bits/stdc++.h> using</bits/stdc++.h>…

これは A07 と大体一緒ですね！ 問題へのリンク 問題概要 あるコンビニは時刻 0 に開店し、時刻 に閉店する。 人の従業員が働いていて、従業員 は時刻 に出勤して、時刻 に退勤する。 について、時刻 に何人の従業員が働いているかを求めよ。 制約 解法 gith…

いもす法！！ 問題へのリンク 問題概要 日間のイベントに 人の参加者が出席した。参加者 は 日目から 日目まで出席した。 各日の出席者数を求めよ。 制約 解法 鉄則本の問題なので、本の方を参照！！ コード #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…