『銀髪赤眼の後輩と学ぶ競技プログラミング2』サポートページ
https://scrapbox.io/files/6240716a449bd60020da32b2.jpg
技術書典 6 で頒布した「銀髪赤眼の後輩と学ぶ競技プログラミング」のサポートページです。 table:正誤表
版 場所 誤 正
第1版 p.10 解法 22 行目 floor(H/a_max) : H/max 以上の最大の整数 ans += ceil(H/a_max) : H/max 以上の最大の整数
第1版 p.15 解法 28 行目 floor(less/(1 問あたりの点数)) ceil(less/(1 問あたりの点数))
第1版 p.16 解法 15 行目 (less-1)/(100*(i+1))+1 (less+100*(i+1)-1)/(100*(i+1))
第1版 p.19 解法 2 行目 const LL INF = 1e12; const LL INF = 1e10;
第1版 p.29 注釈 7 C++では整数型どうしの割り算はこれに... C++では整数型どうしの正の割り算はこれに...
第1版 p.31 mod の性質 a≡b, c≡d a≡c, b≡d
第1版 p.32 この計算、ans の値は最大で 1e9+8 になります この計算途中の ans の値は最大で 1e9+6 になります
第1版 p.44 写像 12 相 箱、玉ともに区別する場合、nPr = n!/(n-r)!通り rPn = r!/(r-n)!通り
第1版 p.44 写像 12 相 箱は区別し、玉を区別しない場合、nCr = n!/r!(n-r)!通り rCn = r!/n!(r-n)!通り
第1版 p.44 写像 12 相 ただし、n<k ならば 0 通り。 ただし、n>r ならば 0 通り
第1版 p.44 玉の並べ方違いの r!パターンを n!/(n-r)!から除く 玉の並べ方違いの n!パターンを r!/(r-n)!から除く
第1版 p.45 注釈 11 r → r-i i → r-i
第1版 p.53 dp[i][j]=max(dp[i-1][j]+(j 以外の活動の幸福度)) dp[i][k]=max(dp[i-1][j]+(j 以外の活動kの幸福度))
第1版 p.23 図
https://scrapbox.io/files/6240755c449bd60020da44b8.jpg
コード
おことわり
この本は2019年に執筆されたものです。
1章
code:dfs.cpp
void dfs(int now(探索中の頂点番号)){
for(int i=0; i<(now から伸びている辺の数); i++){
next = (次に探索する頂点番号);
if(nextをまだ探索していなければ) dfs(next);
}
}
All Green
code:二分探索.cpp
int binary_search(int ok, int ng){
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if(f(mid)) ok = mid;
else ng = mid;
}
return ok;
}
code:union_find.cpp
struct UnionFind {
vector<int> data;
UnionFind(int size) : data(size, -1) { }
// 集合をマージする
// すでに同じ集合ならfalseが返る
bool merge(int x, int y) {
x = root(x); y = root(y);
if (x == y) return false;
// 要素数の少ない方を多い方に繋げる
if (datay < datax) swap(x, y); return true;
}
// ある要素がどの集合に属しているかを答える
int root(int x) {
// 根に直接つなぎ直す
return datax<0 ? x : (datax=root(datax)); }
// ある集合の大きさを答える
int size(int x) {
}
};
2章
素数、コンテスト、素数
code:gcd.cpp
LL gcd(LL a, LL b) {
if(b == 0) return a;
else return gcd(b, a%b);
}
code:拡張ユークリッドの互除法.cpp
LL extgcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
LL g = extgcd(b, a % b, x, y);
LL nextx = y, nexty = x-(a/b)*y;
x = nextx; y = nexty;
return g;
}
int main(){
LL a, p;
cin >> a >> p;
LL x, y;
LL g = extgcd(a, p, x, y);
while(x < 0) x += p;
x %= p;
cout << x << endl;
}
いろはちゃんとマス目
code:modint構造体.cpp
template<int mod>
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(long long y) : x( y>=0 ? y%mod : (mod - (-y)%mod) % mod ) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a/b;
a -= t*b;
swap(a, b);
u -= t*v;
swap(u, v);
}
return ModInt(u);
}
ModInt pow(int e) const {
long long a = 1, p = x;
while(e > 0) {
if(e%2 == 0) {p = (p*p) % mod; e /= 2;}
else {a = (a*p) % mod; e--;}
}
return ModInt(a);
}
};
補足
modint 型の数値 a を cout するには a.xとします。
3章
code:スターリング数.cpp
const int mod = 1e9 + 7;
using modint = ModInt<mod>;
int main(){
int N, r;
cin >> N >> r;
for(int i=1; i<=N; i++){
}
for(int i=2; i<=N; i++){
for(int j=2; j<=r; j++){
}
}
for(int i=1; i<=N; i++){
for(int j=1; j<=r; j++){
}
cout << endl;
}
}