Codeforces Round #551 (Div. 2) E. Serval and Snake
解法
- パスの端点を一つも含まないような範囲
範囲に入った後出ることを繰り返すので返ってくる値は必ず偶数 - パスの端点を両方含むような範囲
範囲から出た後入るを繰り返すので返ってくる値は必ず偶数 - パスの端点を片方だけ含む範囲
範囲内と範囲外を往復したあと出て終わりになるので返ってくる値は必ず奇数
各列/行を覆うような範囲を指定してどの行/列に端点があるのか?を特定する。その後二分探索を行うことで返ってくる値が奇数の範囲を見つける。
行/列の特定に1000回、二分探索にそれぞれ10回最悪でかかるので最悪ケースが来ると条件を満たさない。しかし行/列を指定する順番をランダムにすると最悪を引く確率はかなり小さそうだったので投げると通った。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a) { out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(const T &i: a) out<<i<<','; out<<']'; return out; } template<class T> ostream &operator <<(ostream& out, const set<T>& a) { out<<'{'; for(const T &i: a) out<<i<<','; out<<'}'; return out; } template<class T, class S> ostream &operator <<(ostream& out, const map<T,S>& a) { out<<'{'; for(auto &i: a) out<<i<<','; out<<'}'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; // #define DEBUG ll query(ll x1, ll y1, ll x2, ll y2) { #ifdef DEBUG #else cout << "? " << y1+1 << " " << x1+1 << " " << y2+1 << " " << x2+1 << endl; ll ret; cin >> ret; return ret; #endif } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vector<ll> idx(n); iota(ALL(idx), 0); mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); shuffle(ALL(idx), mt); PII p1({-1, -1}), p2({-1, -1}); for(auto i: idx) { ll num = query(0, i, n-1, i); if(num%2) { if(p1.first == -1 && p1.second == -1) p1.first = -1, p1.second = i; else { p2.first = -1, p2.second = i; break; } } } for(auto i: idx) { if(p2.first != -1 || p2.second != -1) break; ll num = query(i, 0, i, n-1); if(num%2) { if(p1.first == -1 && p1.second == -1) p1.first = i, p1.second = -1; else { p2.first = i, p2.second = -1; break; } } } ll lb=0,ub=n; while(ub-lb>1) { ll mid = (lb+ub)/2; ll num; if(p1.first == -1) num = query(mid, p1.second, ub-1, p1.second); else num = query(p1.first, mid, p1.first, ub-1); if(num%2) lb = mid; else ub = mid; } ll x1, y1; if(p1.first == -1) x1 = lb, y1 = p1.second; else x1 = p1.first, y1 = lb; lb=0,ub=n; while(ub-lb>1) { ll mid = (lb+ub)/2; ll num; if(p2.first == -1) num = query(mid, p2.second, ub-1, p2.second); else num = query(p2.first, mid, p2.first, ub-1); if(num%2) lb = mid; else ub = mid; } ll x2, y2; if(p2.first == -1) x2 = lb, y2 = p2.second; else x2 = p2.first, y2 = lb; cout << "! " << y1+1 << " " << x1+1 << " " << y2+1 << " " << x2+1 << endl; return 0; }
AGC018 D - Tree and Hamilton Path
考えたこと
- 完全グラフだと辺の本数が多すぎてつらそう
- 木の任意の頂点間を移動できると思った方がよさそう
- 任意の順番で木上を移動するとき最長となる経路長を答える問題になった
- よくわからないので実験する
- ある頂点からはじめて最も遠い頂点に移動するを繰り返すみたいな貪欲をしてみる
- サンプル1で頂点1から始めると重み5の辺を一回しか通れない
- 頂点2か頂点5から始めるとよさそう
- 重みが小さい辺の端点から始めるといい?
- サンプル2で試すと132じゃなくて128になる
- 通れてない辺がありそう
- 辺を通れる回数について考えることにする
- ある辺で木を切断したときに連結成分の要素数がs1、s2になったとする
- s1 = s2 の場合 s1*2-1回 しか通れない
- s1 != s2 の場合 min(s1, s2)*2回 しか通れない
- 各辺を通れる回数の上界はわかった
- 上界を取れるとして計算するとサンプル2は合うがサンプル1は合わない
- 上界を取れない木を見つけて適当な辺一つの重みを引けばよさそう…?
- 上界を取れない木がどのようなものなのか考えたいので実験する
- 上界を取れない木ならmin(辺の重み)を答えから引けばいいかなと思ったけどそうではなさそう
- 上界を取れない辺は大体1頂点を端点として共有していそう…?
- 頂点数の偶奇で上界を取れる木と取れない木の判定できるかと思ったけど違う
- 上界を取れる木と取れない木の判定、上界を取れない辺がどの辺なのかがわからない
-----解説を見た-----
- 上界を取れる木と取れない木の判定はs1==s2となる辺が存在するか?
- 上界を取れない辺は重心を端点とする点
実験してたのを見返すと上界を取れない辺が中心付近なのはわかるので重心を端点とする点なのはわかってもよかったかもしれない
重心が絡むことに気づけると重心は1個の場合と2個の場合が存在してるのでそれぞれ場合分けして考えればこの条件も導けた…?
解説放送のやり方
パス の距離は となる。どう順番を決めたところで の中間は変わらないのでどうでもよくて先頭と末尾だけ影響する。LCAの部分がいろいろ変わって厄介だけど重心を根に取ったグラフを考えるとLCAの部分は常に0にできることが示せる。結局先頭を重心、末尾を重心に隣接する点のうち深さが最小なものと取ればよい。
木の距離って言われたらとりあえずLCAを持ち出すのこの間こどふぉでも見たし覚えておいてよさそう
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a) { out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(const T &i: a) out<<i<<','; out<<']'; return out; } template<class T> ostream &operator <<(ostream& out, const set<T>& a) { out<<'{'; for(const T &i: a) out<<i<<','; out<<'}'; return out; } template<class T, class S> ostream &operator <<(ostream& out, const map<T,S>& a) { out<<'{'; for(auto &i: a) out<<i<<','; out<<'}'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; bool flag; ll n, ans, centroid = -1; vector<PII> g[100010]; ll dfs(ll v, ll p) { ll ret = 1; bool is_centroid = true; for(auto to: g[v]) { if(to.first == p) continue; ll sz1 = dfs(to.first, v); if(sz1 > n/2) is_centroid = false; ret += sz1; // sz と n-sz ll sz2 = n-sz1; if(sz1 == sz2) { ans += (sz1*2-1) * to.second; flag = true; } else { ans += min(sz1, sz2) * 2 * to.second; } } if(n-ret > n/2) is_centroid = false; if(is_centroid) centroid = v; return ret; } signed main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> n; REP(i, n-1) { ll a, b, c; cin >> a >> b >> c; a--, b--; g[a].push_back({b, c}); g[b].push_back({a, c}); } dfs(0, -1); if(!flag) { assert(centroid != -1); ll mi = LLINF; for(auto i: g[centroid]) { chmin(mi, i.second); } ans -= mi; } cout << ans << endl; return 0; }
CPSCO 2019
全部解いたので略解と感想メモ
Session1
A: 算数
B: 各文字の出現回数を数える
C: binom(32, 6) の全探索
D: 8*5n-1
E: 各数は高々1回しか消されないのでsetとかで愚直に書いてもok
F: 最小値の最大化と言われたので二分探索を考える
満足度を決めると各果物を食べられる区間がわかる
区間でN日間を覆えるか?の判定を貪欲にする
G: dpの遷移を見る必要がある場所が少ないのでインラインDPをする
dpの遷移で区間minになるのでセグメント木でdpテーブルを持つとできる
H: 分割統治でl,m,rに制限をつけたやつを解くのを再帰的に繰り返す
mにずっと注目してたけどlに注目すると簡単になる
Session2
A: 算数
B: +したあとに*をする
C: +1/-1に置き換えたあと累積和取って大きい方からK個
D: ゲームなので実験すると両方奇数が条件
E: 木DPしてくださいと問題文が言っている
制約が二乗の木DPですと言っている
dp[部分木i][切った辺がj本] = 必要な操作回数 をしようとするとできるのでする
F: 各マスのコインを取る方法はロボットを横に動かすか縦に動かすかの二通り
各マスがどちらに属するか二分割する && 縦/横で取れるマスに依存性がある
グラフをつくって最小カット問題に帰着する(燃やす埋める)
G: クラスカル法の要領で考える
任意のxで使う辺を予め全部つないでおく
コストが小さい辺から見ていき非連結 → その辺をつなぐ and xの辺の本数を少なくする
xの値がw[i]のときの 定数の辺の重み と xの辺の本数 が求められる
Session3
A: 文字列処理
B: 降順ソートして上からM個取る
C: s,tを2倍してimos
D: s[0]='R' && s[n-1]=='B' && 部分文字列にRB/GGがない → Yes
E: bitごとに独立で考えられる 累積xorと0/1の数を持っておけばいい
区間xorの遅延セグ木貼ったらTLEしてつらい
F: P[i] = i は無視してあとで binom(n, a+b) を掛ければいい
あとは箱根駅伝のDP
G: 各アイドルについて賞金を増やしたときに目的関数が減少する量を考える
減少量は単調非減少なのでx_i=0から順番に見ていってもok
各アイドルについて減少量はX/Aを超えるタイミングで3通りしか取らない
3N通りの減少量を求めて大きい方から取る
Session4
A: 算数
B: 全探索
C: r[i]+D以下の人が何人いるか二分探索
D: 退屈さ決め打ち二分探索
E: ox/xoのどちらか
oxが交互の列に分割できる
先頭と末尾が同じ列ならox/xoのどちらかを優先すると取れる数が増える
取れる数が増える方を優先して貪欲に取る
F: 根を決めると残りの頂点をどのように子に分割するかが決められる
再帰的に構築
Codeforces Round #556 (Div. 2) D. Three Religions
解法
まずクエリが存在しない場合にどのように解くか考える。構造が複雑で制約も小さいのでdpをする。 文字列 の 番目までで(文字列1の 文字 && 文字列2の 文字 && 文字列3の 文字)をつくれるか? という愚直なdpがあるがこのままでは状態数が大きすぎてTLEする。dpの値がtrue/falseの2択になっているがここに情報を持たせる。 文字列の何番目まででつくれるか? としたdpが可能である。dpの遷移は
文字列 の より後で文字列1の 文字目が現れる最初の位置, 文字列 の より後で文字列2の 文字目が現れる最初の位置, 文字列 の より後で文字列3の 文字目が現れる最初の位置
となる。文字列 で 文字目以降で文字 が現れる最初の位置を前計算しておくことでこれらの遷移は で計算できる。よってクエリが存在しない場合の計算量は 程度でできる。
クエリごとに毎回dpをしていたのでは かかってしまいTLEする。クエリで変化するのは文字列の末尾1文字だけである点に注目する。クエリによって文字列1の長さが変化したとする。このときdpの値が変動する場所は 文字列1の長さ だけであり 個しか変動しないことがわかる。その他の文字列の長さが変化したとしても同様に 個しか変動しないため 程度の計算量で問題なく解けることがわかる。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; ll dp[255][255][255], pos[100010][30]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n, q; cin >> n >> q; string s; cin >> s; FOR(j, n-1, 100010) REP(i, 26) pos[j][i] = INF; for(ll i=n-1; i>=0; --i) { REP(j, 26) { if(j == s[i]-'a') pos[i][j] = i; else if(i<n-1) pos[i][j] = pos[i+1][j]; } } REP(i, 255) REP(j, 255) REP(k, 255) dp[i][j][k] = INF; dp[0][0][0] = -1; vector<string> v(3); while(q--) { char type; cin >> type; if(type == '+') { ll idx; char c; cin >> idx >> c; idx--; v[idx] += c; ll a, b; if(idx == 0) a = 1, b = 2; else if(idx == 1) a = 0, b = 2; else if(idx == 2) a = 0, b = 1; REP(i, v[a].size()+1) REP(j, v[b].size()+1) { ll x=-1, y=-1, z=-1; if(idx == 0) x = v[0].size(), y = i, z = j; else if(idx == 1) x = i, y = v[1].size(), z = j; else if(idx == 2) x = i, y = j, z = v[2].size(); if(x) { ll tmp = dp[x-1][y][z]+1; if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[0][x-1]-'a']); } if(y) { ll tmp = dp[x][y-1][z]+1; if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[1][y-1]-'a']); } if(z) { ll tmp = dp[x][y][z-1]+1; if(tmp < n) chmin(dp[x][y][z], pos[tmp][v[2][z-1]-'a']); } } } else { ll idx; cin >> idx; idx--; if(idx == 0) { REP(i, v[1].size()+1) REP(j, v[2].size()+1) { dp[v[0].size()][i][j] = INF; } } else if(idx == 1) { REP(i, v[0].size()+1) REP(j, v[2].size()+1) { dp[i][v[1].size()][j] = INF; } } else if(idx == 2) { REP(i, v[0].size()+1) REP(j, v[1].size()+1) { dp[i][j][v[2].size()] = INF; } } v[idx].pop_back(); } if(dp[v[0].size()][v[1].size()][v[2].size()] < n) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
GCJ 2019 R1B Fair Fight
解法
部分点は で取りうる区間を全探索すればよい。
満点では 個の区間を全部見ているのでは間に合わない。 が最大になり、 についても条件を満たすような区間がそれぞれ何個あるか?を各 に対して求めることで答えを求める。この各区間に課される条件を3つに分割することで数えやすくする。
(1) となるような最大の区間の
(2) となるような最大の区間
(3) となるような最大の区間
(1)~(3)のそれぞれについて最大の区間に内包される全ての区間についても条件を満たす。よって条件を満たす区間は 個となる。また、(1)について同じ区間を複数回数えないようにするため区間の最大値が複数ある場合は最も左の を選ぶとする。
答えは ((1)と(2)を両方を満たすような区間の数)-((1)と(3)の両方を満たすような区間の数) となる。よってこれらの区間の数を高速に求めることができればよい。(1)を満たすような区間が で(2)を満たすような区間が であるとき、これら両方を満たすような区間は から となる。したがって(1)~(3)を求めることができれば答えがわかる。
(1)の を求めることを考える。 として を満たすような最大の が求まればよい。これは区間の最大値が単調増加することから二分探索を使って求めることができる。sparse table等の でRMQができるデータ構造を用いることで で各 について を求めることができる。その他の についても同様に二分探索を行うことで求めることができ で解くことができた。
(1)で重複して数えないようにするため と のpairの区間minを求めるとした。(2)(3)の区間が空の場合に注意。
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; template <typename S> struct sparseTable { using T = typename S::T; int n; vector<int> log2; vector<vector<T>> t; sparseTable(int nn) { n = nn; log2.assign(n+1, 0); for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1; t = vector<vector<T>>(log2[n]+1, vector<T>(n)); } void init(vector<T> v) { for(int i=0; i<n; ++i) t[0][i] = v[i]; for(int j=1; j<=log2[n]; ++j) { int w = 1LL<<(j-1); for (int i = 0; i+(w<<1) <= n; ++i) { t[j][i] = S::op(t[j-1][i], t[j-1][i+w]); } } } // [l, r] T query(int l, int r) { int j = log2[r - l]; return S::op(t[j][l], t[j][r-(1 << j)+1]); } }; // 集合T、結合則・可換・冪等律が成り立つ二項演算op struct maximum { using T = ll; static T op(const T& a, const T& b) { return max(a, b); } }; struct maximum_P { using T = PII; static T op(const T& a, const T& b) { return max(a, b); } }; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll test; cin >> test; REP(tes, test) { ll n, k; cin >> n >> k; vector<ll> c(n), d(n); REP(i, n) cin >> c[i]; REP(i, n) cin >> d[i]; vector<PII> cc(n); REP(i, n) cc[i] = {c[i], i}; sparseTable<maximum_P> seg1(n); seg1.init(cc); sparseTable<maximum> seg2(n); seg2.init(d); ll ret = 0; REP(i, n) { // max(c[l],…,c[r]) = c[i] となるようなl,r ll l1, r1; ll lb=-1, ub=i; while(ub-lb>1) { ll mid = (lb+ub)/2; if(seg1.query(mid, i) <= cc[i]) ub = mid; else lb = mid; } l1 = ub; lb=i, ub=n; while(ub-lb>1) { ll mid = (lb+ub)/2; if(seg1.query(i, mid) <= cc[i]) lb = mid; else ub = mid; } r1 = lb; // max(d[l],…,d[r]) <= c[i]+k となるようなl,r if(d[i] > c[i]+k) continue; ll l2, r2; lb=-1, ub=i; while(ub-lb>1) { ll mid = (lb+ub)/2; if(seg2.query(mid, i) <= c[i]+k) ub = mid; else lb = mid; } l2 = ub; lb=i, ub=n; while(ub-lb>1) { ll mid = (lb+ub)/2; if(seg2.query(i, mid) <= c[i]+k) lb = mid; else ub = mid; } r2 = lb; // max(d[l],…,d[r]) < c[i]-k となるようなl,r ll l3, r3; lb=-1, ub=i; while(ub-lb>1) { ll mid = (lb+ub)/2; if(seg2.query(mid, i) < c[i]-k) ub = mid; else lb = mid; } l3 = ub; lb=i, ub=n; while(ub-lb>1) { ll mid = (lb+ub)/2; if(seg2.query(i, mid) < c[i]-k) lb = mid; else ub = mid; } r3 = lb; // max(c[l],…,c[r])=c[i] かつ max(d[l],…,d[r])<=c[i]+k ll l = max(l1, l2), r = min(r1, r2); ret += (i-l+1) * (r-i+1); // max(c[l],…,c[r])=c[i] かつ max(d[l],…,d[r])<c[i]-k if(d[i] < c[i]-k) { l = max(l1, l3), r = min(r1, r3); ret -= (i-l+1) * (r-i+1); } } cout << "Case #" << tes+1 << ": "; cout << ret << endl; } return 0; }
Tenka1 Programmer Contest 2019 E - Polynomial Divisors
解法
解説放送で言ってることを自分流に書いたもの
pを一つ固定してその素数が条件を満たすか判定することを考える。pで割り切れるか考えるので以降ではmod pで考える。任意のxに対してf(x)=0 mod pとなればよい。フェルマーの小定理よりx=x^pである。したがって
f(x)
= a[N]x^N + a[N-1]x^(N-1) + … + a[1]x + a[0]
= (a[p-1]+a[2p-2]+…)x^(p-1) + … + (a[2]+a[p+1]+…)x^2 + (a[1]+a[p]+…)x + a[0]
となる。多項式がどのようなxに対しても0になる⇔係数が全て0 であるから係数が全て0か判定することでpが条件を満たすか判定することができる。係数を足してpの倍数になっているかの判定をO(N)ですればよい。
あとはpの候補全てに対してこの判定を行えばよい。pの候補の数を絞ることで全ての候補に対して判定を行っても間に合うようにする。
- p<=N
10^4以下の素数は大した個数がないので全ての素数に対して判定を行う - p>N
フェルマーの小定理を使って変形したようにx^iの係数が複数のaの和になることがない。よってaNがpの倍数でないと条件を満たすことはない。したがってpの候補となるのはa[n]の素因数のみであり大した個数ではないので全てに対して判定を行えばよい。a[n]<0の場合に注意
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; const ll MOD = 1000000007; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; vector<ll> a(n+1); REP(i, n+1) cin >> a[n-i]; auto test = [&](ll p) { if(a[0]%p) return false; vector<ll> sum(p); FOR(i, 1, n+1) sum[i%(p-1)] += a[i]; bool flag = true; REP(i, p) if(sum[i]%p != 0) flag = false; return flag; }; vector<ll> ans; // P <= N vector<bool> prime(n+2, true); prime[0] = prime[1] = false; for (int i = 2; i <= n; i++) { if (prime[i]) { if(test(i)) ans.push_back(i); for (int j = 2 * i; j <= n; j += i) { prime[j] = false; } } } // P > N ll t = abs(a[n]); vector<ll> div; for(ll i=2; i*i<=t; ++i) { if(t%i==0) div.push_back(i); while(t%i==0) t/=i; } if(t>1) div.push_back(t); for(auto i: div) { if(i <= n) continue; bool flag = true; REP(j, n+1) if(a[j]%i != 0) flag = false; if(flag) ans.push_back(i); } for(auto i: ans) cout << i << endl; return 0; }
Tenka1 Programmer Contest 2019 D - Three Colors
考えたこと
- 部分和問題っぽくて貪欲は無理そうだし制約小さいしまあDP
- dp[i番目まで][R=j][G=j] みたいなDPを考える
- R,G,Bは90000くらいまで取りうるのでどう考えても無理
- 三角形の成立条件を考える
- R+G>B && R+B>G && B+G>R
- どれか一つ和を持っておけば済むとかがあると嬉しいけど思いつかない
- 条件の否定を取って補集合の方を数えることにしてみる
- R+G<=B || R+B<=G || B+G<=R になる
- 和集合を数えたいので包除原理っぽい
- R+G<=Bだけを満たすのを数えるだけならDPすればできる
- 対称性があるので3倍すればよさそう
- 2つ条件を満たす場合を数え上げたい
- R+G<=B && R+B<=G
- いろいろ考えてしばらく迷走する
- これ満たすのB=G, R=0 しかない
- R=0 or G=0 or B=0 だったら三角形ができることはない
- R>0 && G>0 && B>0 && R+G<=B のパターンを数え上げる
- 対称性でこれを3倍する
- 全体(R!=0&&G!=0&&B!=0の塗り方)からこの値を引けば答えになる
- dp[i番目まで][j=R+G][k=(R>0)][l=(G>0)] = (組み合わせ数) としてDP
modintバグってたのとmake_vをグローバルにしたら爆速になったのとかが虚無だった
#include <bits/stdc++.h> using namespace std; using ll = long long; // #define int ll using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); } template<typename T,typename... Ts> auto make_v(size_t a,Ts... ts) { return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...)); } template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t, const V &v) { t=v; } template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL const int INF = 1<<30; const ll LLINF = 1LL<<60; // const ll MOD = 1000000007; template<ll MOD> struct modint { ll x; modint(): x(0) {} modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {} static constexpr ll mod() { return MOD; } // e乗 modint pow(ll e) { ll 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 inv() const { ll a=x, b=MOD, u=1, y=1, v=0, z=0; while(a) { ll q = b/a; swap(z -= q*u, u); swap(y -= q*v, v); swap(b -= q*a, a); } return z; } // Comparators bool operator <(modint b) { return x < b.x; } bool operator >(modint b) { return x > b.x; } bool operator<=(modint b) { return x <= b.x; } bool operator>=(modint b) { return x >= b.x; } bool operator!=(modint b) { return x != b.x; } bool operator==(modint b) { return x == b.x; } // Basic Operations modint operator+(modint r) const { return modint(*this) += r; } modint operator-(modint r) const { return modint(*this) -= r; } modint operator*(modint r) const { return modint(*this) *= r; } modint operator/(modint r) const { return modint(*this) /= r; } modint &operator+=(modint r) { if((x += r.x) >= MOD) x -= MOD; return *this; } modint &operator-=(modint r) { if((x -= r.x) < 0) x += MOD; return *this; } modint &operator*=(modint r) { x = x * r.x % MOD; return *this; } modint &operator/=(modint r) { return *this *= r.inv(); } // increment, decrement modint operator++() { x++; return *this; } modint operator++(signed) { modint t = *this; x++; return t; } modint operator--() { x--; return *this; } modint operator--(signed) { modint t = *this; x--; return t; } }; using mint = modint<998244353>; template<class T> mint operator*(T l, mint r) { return mint(l) *= r; } template<class T> mint operator+(T l, mint r) { return mint(l) += r; } template<class T> mint operator-(T l, mint r) { return mint(l) -= r; } template<class T> mint operator/(T l, mint r) { return mint(l) /= r; } template<class T> bool operator==(T l, mint r) { return mint(l) == r; } template<class T> bool operator!=(T l, mint r) { return mint(l) != r; } // Input/Output ostream &operator<<(ostream& os, mint a) { return os << a.x; } istream &operator>>(istream& is, mint &a) { return is >> a.x; } string to_frac(mint v) { static map<ll, PII> mp; if(mp.empty()) { mp[0] = mp[mint::mod()] = {0, 1}; FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) { mp[(mint(i) / j).x] = {i, j}; } } auto itr = mp.lower_bound(v.x); if(itr != mp.begin() && v.x - prev(itr)->first < itr->first - v.x) --itr; string ret = to_string(itr->second.first + itr->second.second * ((int)v.x - itr->first)); if(itr->second.second > 1) { ret += '/'; ret += to_string(itr->second.second); } return ret; } mint dp[300][90001][2][2]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); ll n; cin >> n; ll sum = 0; vector<ll> a(n); REP(i, n) cin >> a[i], sum += a[i]; dp[0][0][0][0] = 1; dp[0][a[0]][1][0] = 1; dp[0][a[0]][0][1] = 1; FOR(i, 1, n) REP(j, sum+1) REP(k, 2) REP(l, 2) { if(j>=a[i]) { dp[i][j][k|1][l] += dp[i-1][j-a[i]][k][l]; dp[i][j][k][l|1] += dp[i-1][j-a[i]][k][l]; } dp[i][j][k][l] += dp[i-1][j][k][l]; } mint ret = 0; FOR(i, 1, sum) if(i <= sum-i) ret += dp[n-1][i][1][1]; cout << mint(3).pow(n) - mint(2).pow(n)*3 + 3 - ret*3 << endl; return 0; }