#include <bits/stdc++.h> //#include <atcoder/all> //using namespace std; //using namespace atcoder // 時間管理 class TimeKeeperDouble { private: std::chrono::high_resolution_clock::time_point start_time_; double time_threshold_; double now_time_ = 0; public: TimeKeep</atcoder/all></bits/stdc++.h>…

AHC短期メモ 解説記事を読んだ上での改善含むので自力ではない ■AtCoder Heuristic Contest 002 時間：004:00 概要：フィールド上を与えられた初期位置移動してポイント稼ぎ perf：3512(1位) やったこと：焼きなまし 初期解をdfsをすることで発見する 初期解…

■M - Candies(EDPCM) https://atcoder.jp/contests/dp/tasks/dp_m [x^k]Π(1-x^(a+1))/(1-x)■D - Binomial Coefficient is Fun(ARC110D) https://atcoder.jp/contests/arc110/tasks/arc110_d f_i=ΣBinom(b,a_i)x^bとして 求めるものは [x^m]1/(1-x)*Πf_iであ…

■A - コンテスト(Typical DP Contest) https://atcoder.jp/contests/tdpc/tasks/tdpc_contest Π(1+x^p)■D - Polynomial division (ABC245) https://atcoder.jp/contests/abc245/tasks/abc245_d b=c/a ただしライブラリによってはa[0]!=0じゃないとREするので…

https://kenkoooo.com/atcoder/#/contest/show/28c6016e-1df1-4039-aeee-95f2777bd5ac ■01. D - Harlequin(CADDi 2018 for Beginners) https://atcoder.jp/contests/caddi2018b/tasks/caddi2018_b ・取りうる状態を考える 状態A：すべてのりんごが偶数個 状…

よくどれがどれかわからなくなるので ■suffix_array ◆概要 長さnの文字列sのSuffix Arrayとして、長さnのvectorを返す。◆例 string s = "missisippi";に対して {9,6,4,1,0,8,7,5,3,2}を返す { "i", "ippi", "isippi", "issisippi", "missisippi", "pi", "ppi…

＜mcf_graph(MinCostFlow)＞ 最小費用流 sからtに流量を流せるだけ流したときのコストの最小値を求める 流量にlimを定めることも出来る■O - 輪投げ（第三回 アルゴリズム実技検定 過去問） 求めたいもの：最終得点の最大値 反転させ最小値を求めることでMinC…

積の和典型 自分用の書き換え ■例題 長さがn総和がmな整数列Aの全て対して ΣΠA[i]を求めよo:=m-n個 x:=n個 ! :=n-1個の並び替えを考える。但しxと!は交互に配置する つまりBinom(m+n-1,2*n-1)で求まる■D - Binomial Coefficient is Fun（AtCoder Regular Con…

問題特有のAdhocな部分の解説はしない ■典型 n進数での高速ゼータ変換 // 遷移 int x = 10; rep(j, k) {//桁数 int pw = 1; rep(i, j)pw *= x; rrep(i, sz) { // iの下からj桁目 int num = (i / pw) % x; rep(k, num) { dp[i] += dp[i - pw * (num - k)]; } …

二週連続で食らったので 以下全て問題は 長さ2^nの配列Aが与えられ 各iに対して、j⊂iを満たすAjの和とする。 ①まず愚直解 rep(i, 1 << n) { int ans = 0; rep(j, 1 << n) { if (j == (i& j))ans += a[j]; } cout << ans << endl; }②高速ゼータ変換 /* dp[i][…

汎用的エスパー？なので書き残し 問題の設定上、答えはx/2^Nの形になるのは明らか。 なのでサンプルの答えに2^Nをかけてみる サンプル3に2^19をかけたもの 4980736 4980736 4980742 4980782 4981006 4982158 4987790 5014414 5137294 5694350 5137294 501441…