蟻本をする
やりかた: 蟻本読解と類題解きを非同期でやっていく(読みたいときにさくさく先に進むため)
類題を前から1問ずつ解いていってダメだったら適宜戻る、コンテスト中に解いたことがある場合はサボります(最悪)
類題の出典: https://qiita.com/drken/items/e77685614f3c6bf86f44
特別に断りがない限り例題の自力 or notは脳内AC(POJはつらいので)、類題は該当submitを併記
2-1 全探索
グリッド -> グラフライブラリのverifyがてら暇なときに埋めていく予定
例題 2-1-1 部分和問題
自力: 〇
類題: https://atcoder.jp/contests/arc061/submissions/9672420
自力: 〇
bit全探索だね
例題 2-1-2 Lake Counting (POJ No.2386)
自力: 〇
類題: https://atcoder.jp/contests/atc001/submissions/9673321
自力: 〇
例題 2-1-3 迷路の最短路
自力: 〇
類題: https://atcoder.jp/contests/abc007/submissions/9676680
例題 2-1-4 特殊な状態の列挙
自力: 〇
類題: https://atcoder.jp/contests/abc150/submissions/me
自力: 〇
コメント: next_permutationを使う問題というだけ
2-2 貪欲
例題 2-2-1 硬貨の問題
自力: 〇
AtCoder上に類題なさそうだしパス
例題 2-2-2 区間スケジューリング問題
自力: ×
区間スケジューリング問題 -> 末尾でソートして貪欲
区間を見たら先頭 or 末尾 でソート
知らなかったら無から思いつくのはかなりつらくないですか
類題: https://atcoder.jp/contests/keyence2020/submissions/9565253
自力: 〇
コメント: 蟻本やるかーって言いだした直後のこれだったのでラッキー
例題 2-2-3 Best Cow Line (POJ No.3617)
自力: 〇
辞書順最小 -> 先頭から貪欲
先頭と末尾が同じ場合は reverse して比較することで同じ区間を無視して比較できる かしこい
類題: https://atcoder.jp/contests/abc076/submissions/8885620
自力: 〇
例題 2-2-4 Saruman's Army (POJ No.3069)
制約が厳しい順に貪欲(あるある)
類題: https://atcoder.jp/contests/abc083/submissions/9697785
自力: 〇
Fence Repair (POJ No.3253)
自力: ×
小さい順に合成していけばよいというのが非自明だった、言われてみればそれはそうなのだけど
類題: https://codeforces.com/contest/462/submission/69303070
自力: 〇
ほぼ例題そのまんまだった、手順逆回し、大きい集合がたくさん出てくると有利なのでその通りにする
2-3 DP
例題 2-3-1 01ナップサック問題
自力: 〇
知っていたので……
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4130992#1
自力: 〇
コラム:
貰うDPと配るDPの話、遷移元を意識するか遷移先を意識するか、という気持ちで理解している
個人的には"貰う" でメモ化再帰するのが一番らく(再帰関数が遅延評価っぽく解決してくれるため更新順序を考えなくて済むので)だと思うけど気がついたら配ってたりするのでわからんちん
例題 2-3-2 最長共通部分列問題
自力: ×
知っていたけど覚えていなかったので……
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4131284#1
自力: △
解説見ながら写経しちゃった
例題 2-3-3 個数制限なしナップサック問題
自力: ×
ナップザック問題の、取得できる品物の個数が無限になったバージョン
dp[i+1][j] := i番目の品物から重さの総和がjイカになるように選んだ時の価値の最大値
とすると、 dp[i+1][j] を計算するとき、k(>=1)個品物iを取得する場合、dp[i+1][j-w[i]] を計算するときにk-1個選んだ場合と同様である と考えることができる。(<- 天才)
よって、dp[i+1][j-w[i]] (一つ以上の品物iを取得するかもしれない場合) とdp[i][j] (品物iを取得しない場合) から"貰う" ことでDPの更新とできる。
ふつうの(01)ナップザック問題では dp[i][j-w[i]] (品物iを取得する場合) とdp[i][j] (品物iを取得しない場合) から"貰う" ことでDPの更新とすることに注意する。(添え字が違う)
添え字の違いは遷移元の違いなのだなあ、という気持ち
類題: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4131387#1
自力: 〇
知ってればそれはできるね、という感じ
例題 2-3-4 01ナップサック問題その2
自力: ×
類題: https://atcoder.jp/contests/abc032/submissions/9813660
自力: △
半分全列挙のところだけ×
例題 2-3-5 個数制限付き部分和問題
自力: ×
類題: https://atcoder.jp/contests/maximum-cup-2018/submissions/9830320
自力: 〇
DPの値にbool以上の意味を持たせる、って言われていれば素直に思いつく系
例題 2-3-6 最長増加部分列問題
自力: ×
類題: https://atcoder.jp/contests/chokudai_S001/submissions/9839984
まあ りす はDPでNlogNで求められるということを覚えていればよさそう
例題 2-3-7 分割数
自力: ×
解説が不親切シリーズ1
ここが詳しい
dp[i][j] := jのi分割(jのi分割、とはjをi個"イカ"の集合に分割する場合の数、であることに気を付ける、jをi個の集合に分割する場合の数、ではない) としたとき、分割した数の集合をa_k (0<=k<=i) とおくと、
1. a_k == 0 なるk が存在する場合
これはjのi-1分割に含まれるので、 dp[i-1][j]
2. そうでない場合
これは、jをi個の空でない集合に分割する必要があるので、集合が空集合にならないことを保証するためにi個の集合に先に1つだけ振り分けると(大学入試でよく見るヤツです)、dp[i][j-i]で表される
結局、 dp[i][j] = dp[i-1][j] + dp[i][j-i] で更新できる
類題: https://yukicoder.me/submissions/424992
自力: 〇
先に必要数だけ振り分けるという思考をついでに事前計算でもやる問題だった
例題 2-3-8 重複組合せ
自力: ×
解説が不親切シリーズ2
ここが詳しい
emtubasa.hateblo.jp 自分でもちょっと真面目に考えた
j-1に置き換える時のmの扱いに若干誤魔化しがあるけどこれでわかった感 pic.twitter.com/wGSNZduhd6
— AIRをプレイする (@ymduu) 2020年2月1日
類題: https://atcoder.jp/contests/abc021/tasks/abc021_dj-1に置換したときのmはmin(j, a[i])からmin(j-1, a[i]) になっているけど、mがjになるとj-m-1 が負になって、dpの定義からdp[i][-1] = 0 なので、mがjでもj-1でもdp[i+1][j-1] の値は変わらないといえる(ので、正当な式変形と言える)
— AIRをプレイする (@ymduu) 2020年2月1日
自力: 〇
素直な重複組み合わせなのでDPせずnCrのライブラリで殴っちゃった(演習の意味)
2-4 データ構造
例題 2-4-1 Expedition (POJ No.2431)
自力: 〇
類題: https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/9867313
自力: 〇
例題 2-4-2 二分探索木 (set, map の練習) 流石に無 + 蟻本に対応する例題がないためパス
例題 2-4-3 食物連鎖 (POJ No.1182)
自力: ×
類題: https://atcoder.jp/contests/arc036/submissions/9868509
自力: 〇
グラフ上で「ある状態で」(今回の場合、移動距離が偶数の状態で)場所Nに到達できるか? -> 拡張ダイクストラ(頂点倍加)
今回は接続性さえわかればいいので、今までの移動距離が偶数であるノードと奇数であるノードを用意してUnionFindでOK
2-5 グラフ
例題 2-5-1 二部グラフ判定
自力: 〇
類題: https://atcoder.jp/contests/maximum-cup-2018/submissions/9898898
例題 2-5-2 Roadblocks (POJ No.3255)
自力: ×
https://atcoder.jp/contests/abc035/submissions/9926603
複数の街に滞在する意味がないことはすぐにわかる。
帰り道の最短経路がわからないが、単一終点最短経路をしたいときは辺の向きを逆転させたグラフに対して単一始点最短経路をすればよい(賢すぎか?)
例題 2-5-3 Conscription (POJ No.3723)
自力: 〇
類題: https://atcoder.jp/contests/abc065/submissions/9954687
所見の時は思いつかなかった記憶があるけど今回は見た瞬間x軸y軸における両隣に辺を張ればよいことがすぐに思いつけたので、成長
例題 2-5-4 Layout (POJ No.3169)
自力: ×
牛ゲーム、不等式がたくさんあって、それを満たしながら最適化する問題は最短経路問題に落ちるかもということだけ覚えておく
類題: https://atcoder.jp/contests/utpc2013/submissions/9966659
自力: △
よくわかってないところがあり
牛ゲー(不等式 * 大量 の線形計画問題を最短経路に落とすやつ)、なんで負閉路が存在する場合(≒最短経路が存在しない場合)条件を満たす解が存在しないことになるんだろう
— AIRをプレイする (@ymduu) 2020年2月9日
このような不等式をすべて満たすようなdにおけるd(v) - d(s) の最大値がsからvへの最短距離となっています なので、負閉路が存在する場合最短距離が存在せず、不等式をすべて満たすd とやらも存在しなくなってしまうのだ、という話かなあ
— AIRをプレイする (@ymduu) 2020年2月9日
これ以上詳しい理解をしたければ蟻本でしれっと当たり前だが……みたいな顔で登場している"このような不等式をすべて満たすようなdにおけるd(v) - d(s) の最大値がsからvへの最短距離となっています" の理由を理解しないとダメそう
— AIRをプレイする (@ymduu) 2020年2月9日
例題 2-6-1 線分上の格子点の個数
自力: △
(すぐ下にある解説を見てしまった)
類題: https://atcoder.jp/contests/abc070/submissions/9970561
オーバーフローがめんどうでPythonしてしまった
例題 2-6-2 双六
自力: 〇
拡張ユークリッドの互除法やるだけ
類題: https://codeforces.com/contest/1244/submission/71210362
自力: 〇
拡張ユークリッドの互除法でごり押しできる(オーバーフローするので多倍長整数が必要だけど)
試合数に制限があるので、なるべくたくさん勝ったほうが有利であることを考える。
y の範囲は w 未満である(w 回 引き分けるなら d 回勝ったとするほうが試合回数的に有利であるため)ことを考えれば全探索できる
例題 2-6-3 素数判定
自力: 〇
類題: https://atcoder.jp/contests/arc017/submissions/10126400
はい
例題 2-6-4 素数の個数
自力: 〇
類題: https://atcoder.jp/contests/tenka1-2012-qualc/submissions/10127486
自力: 〇
例題 2-6-5 区間内の素数の個数
自力: 〇
類題: https://atcoder.jp/contests/jag2017autumn/submissions/10320359
自力: ×
言われてみれば区間篩なのだけど初見では全然わからんかった、区間[l, r] についてすべての素因数を処理したかったら sqrt(r) までの素数を列挙しておいてエラトステネスの篩っぽく飛び飛びに処理をする(語彙力)とよい区間[l, r]内の prime factor が素数である(a)数を列挙する問題で、sqrt(r)までの素数を列挙しておけば素因数分解がlogでできるので(ここまで自力)
— AIRをプレイする (@ymduu) 2020年2月24日
[l, r] の数を並べておいて、エラトステネスの篩っぽく素数pの倍数だけpで割れるだけ割っていく
sqrt(n) までの素因数を列挙しておけばlogで素因数分解ができるので、たくさん素因数分解をしなければならぬ ときには有効かも
例題 2-6-6 Carmichael Numbers (Uva No.10006)
自力: 〇
類題: https://atcoder.jp/contests/joisc2007/submissions/10322004
くりかえし二条城
類題はTL0.5sec で p = 104 なのに p2 が通るのでびっくりしてしまう(logがつくとダメ、というレベルでTLが厳しいので、すべての数についてn乗を計算しておく、とかvectorを使わない、とか涙ぐましい最適化が必要)
GCJの問題に挑戦
Minimum Scalar Product
自力: 〇
大きい奴には小さい奴をマッチングさせる貪欲なんだけど、どこかで全く同じ問題を見た気がする。
Crazy Rows
自力: ×
先に最右の1の位置(ダジャレ)を計算しておいて転倒数を計算したらいいじゃん、と思ったが嘘で死亡
制約がめちゃめちゃ小さいので1行目からシミュレートして確定させていってもよい
Bribe the Prisoners
自力: 〇
区間DP、これを自力できたのはかなりうれしいので記念に(?)コードを貼っておく
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <numeric> #include <queue> #include <stack> #include <map> #include <set> #include <string> #include <functional> #include <list> #include <random> #include <time.h> #include <iomanip> #include <assert.h> #include <numeric> #define BIT(nr) (1UL << (nr)) #define int long long #define ll long long #define double long double #define mod 1000000007 #define MAXN (int)1e+5 * 2+1 #define LL_MAX 9223372036854775807 //ない環境用 #define LL_HALFMAX 9223372036854775807 / 2 //ない環境用 #define MIN -(9223372036854775807 / 2) #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() #define REPS(i,x) for(int i=1;i<=(int)(x);i++) #define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--) #define RREPS(i,x) for(int i=((int)(x));i>0;i--) #define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define mp make_pair template<typename T1, typename T2> inline void chmin(T1 & a, T2 b) { if (a > b) a = b; } template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; } using namespace std; int dp[10010][10010]; int A[101]; void solve() { int P, Q; cin >> P >> Q; rep(i, P + 5) { rep(j, P + 5) { dp[i][j] = LL_HALFMAX; } } vector<int> A(Q); rep(i, Q) { cin >> A[i]; } sort(ALLOF(A)); // [left, right) の解を返す function<int(int, int)> rec = [&](int left, int right) -> int { if (dp[left][right] != LL_HALFMAX) { return dp[left][right]; } int cost = LL_HALFMAX; auto lit = lower_bound(ALLOF(A), left); // もしも区間に開放すべき囚人がいなかったら、0 if (lit == A.end() || !(*lit < right)) { cost = 0; } while (lit < A.end() && *lit < right) { int n = *lit; chmin(cost, rec(left, n) + rec(n + 1, right) + (right - left - 1)); lit++; } return dp[left][right] = cost; }; cout << rec(1, P + 1) << "\n"; } signed main() { int T; cin >> T; rep(i, T) { cout << "Case #" << i + 1 << ": "; solve(); } return 0; }
Millinaire
自力: ×
解説が不親切シリーズ
解説を読んでもなにもわからないのでツイッターでググったりしながら頑張って読解した
蟻本のソースにガンバってコメントをつけてみたのでツッコミを募集します
int M, X; double P; double dp[2][(1 << 15) + 1]; void solve(){ cin >> M >> P >> X; int n = 1 << M; double *prv = dp[0], *nxt = dp[1]; memset(prv, 0, sizeof(double) * (n + 1)); // 尻からたどる想定、最後には $1000000 を持っているものとする prv[n] = 1.0; for (int r = 0; r < M; r++) { // 所持金がiから勝てる確率を求める、prv[i] := 今ラウンド後所持金iから勝てる確率、 nxt[i]:=今ラウンド前所持金がiから勝てる確率(尻から見て行ってるので実装上の prv nxt と時系列の前後が逆転することに注意) for (int i = 0; i <= n; i++) { // 所持金がnを超える必要はないので、最大掛け金はi(所持金全部)かn-i(nになるのに不足するぶんの掛け金) int jub = min(i, n - i); double t = 0.0; // jだけかける for (int j = 0; j <= jub; j++) { // 確率Pで勝ち、1-Pで負けるので、確率Pで勝った未来から、確率1-Pで負けた未来から遷移してくる(尻から見ていることに注意) t = max(t, P*prv[i + j] + (1 - P) * prv[i - j]); } nxt[i] = t; } swap(prv, nxt); } int i = (int)X*n / 1000000; printf("%.6f\n", prv[i]); } signed main() { int T; cin >> T; rep(i, T) { cout << "Case #" << i + 1 << ": "; solve(); } return 0; }
試行錯誤の記録
ググってもなにも出てこないし蟻本の解説から実装を理解できないので最後の望み†Twitter†をする
i:所持金
— hogeover40 (@hogeover30) 2016年4月12日
j:賭金
i + j:買った場合の所持金
i - j:負けた場合の所持金
所持金を超える額は賭けられない→ j <= i
所持金がnを超える必要は無い→ i + j <= n → j <= n - i
→ j <= min(i, n - i)#メモ
prv と nxt 、配列を使いまわすことで(2 ** 15) * 15 の配列を取らなくて済むようにしているのか(とっても10^5だしたいしたことはないと思うけど)
— AIRをプレイする (@ymduu) 2020年2月24日
いやでも t = max(t, P*prv[i + j] + (1 - P) * prv[i - j]); の max ってなんの max だ
— AIRをプレイする (@ymduu) 2020年2月24日
ゲームが終わった時点から見ていて、dpの各セルに入るのは ここから勝てる確率 であるので正当でした
— AIRをプレイする (@ymduu) 2020年2月24日
所持金iに対して可能なすべての掛け金jを試して、iになる確率がもっとも高いjを採用しているように見える(これ正当なのか?)
— AIRをプレイする (@ymduu) 2020年2月24日
大人しくdp[i][j] := i番目のゲームが終わった時所持金の区分がjである状態から勝てる確率 としたほうがわかりやすかったのでは……(メモリもおそらく間に合うし)
— AIRをプレイする (@ymduu) 2020年2月24日
確率で勝ったり負けたりするゲームで勝てる確率を計算するときは尻から各状態に遷移する確率を計算するDPをするといいかも、だけ覚えておけばいいかな
— AIRをプレイする (@ymduu) 2020年2月24日