にゃん.
oo-oo- 160th.
A. Treasure Hunt
問題概要
が与えられる. 次の操作を何回か行って を にできるか判定せよ.
- .
- .
- .
- .
解法
あまりにも むずかしすぎる.
みたいな操作をすると, の値を動かさずに の値を 動かせる.
あとはフィーリングでえいすれば解ける.
ソース
#include<bits/stdc++.h> using namespace std; int main() { int X1, Y1, X2, Y2, X, Y; cin >> X1 >> Y1 >> X2 >> Y2; cin >> X >> Y; int sa1 = abs(X1 - X2), sa2 = abs(Y1 - Y2); if(sa1 % X != 0 || sa2 % Y != 0) { cout << "NO" << endl; } else { sa1 /= X; sa2 /= Y; if((abs(Y1 - Y2) + sa1*Y) % (2 * Y) == 0 || (abs(X1 - X2) + sa2*X) % (2 * X) == 0) { cout << "YES" << endl; } else { cout << "NO" << endl; } } }
B. Makes And The Product
問題概要
長さ の数列 が与えられる.
が最小となるような の組は何個あるか求めよ.
解法
分考えてよくわからなかったので貼った(正確には面倒そうだった).
まずソートしても答えは変わらないのでソートする. すると つの値が となるものが最小の選び方.
今までで 個選んでいて最後に 番目の要素を選んだ時の組み合わせの個数
とすればなんかいい感じの DP ができる.
を満たす要素 に対して みたいな遷移をする.
サボって BIT を使えば .
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; template< class T > struct BinaryIndexedTree { vector< T > data; BinaryIndexedTree(int sz) { data.assign(++sz, 0); } T sum(int k) { T ret = 0; for(++k; k > 0; k -= k & -k) ret += data[k]; return (ret); } void add(int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] += x; } }; int main() { int N, A[100000]; cin >> N; for(int i = 0; i < N; i++) { cin >> A[i]; } sort(A, A + N); BinaryIndexedTree< int64 > bit(N); for(int i = 0; i < 3; i++) { BinaryIndexedTree< int64 > bit2(N); for(int j = 0; j < N; j++) { if(A[j] == A[i]) bit2.add(j, i==0?1:bit.sum(j - 1)); } swap(bit, bit2); } cout << bit.sum(N - 1) << endl; }
C. Really Big Numbers
問題概要
以下の正整数 のうち と の桁ごとの和の差が となるようなものは何個あるか求めよ.
解法
解けない(ア
方針が違っていて無限にバグった. 何でもかんでも桁DPを考えるのよくないね…
桁DPを考えると
上から 桁目まで見て, 今までで を下回る桁があったかどうかが で 差が のときの条件を満たす個数
となる. の状態数がアレなのでDPできてない気がするが闇をすれば通る.
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; int64 T; string S; unordered_map< int64, int64 > dp[19][2]; int64 dp2[19][2]; unsigned long long mod_pow[19]; int64 rec2(int idx, bool free) { if(idx == S.size()) return (1); if(~dp2[idx][free]) return (dp2[idx][free]); int end = free ? 9 : S[idx] - '0'; int64 ret = 0; for(int i = 0; i <= end; i++) ret += rec2(idx + 1, free | (i != end)); return (dp2[idx][free] = ret); } int64 rec(int idx, bool free, int64 ketasum, int64 oddsum) { if(idx == S.size()) return (oddsum - ketasum >= T); if(oddsum - ketasum >= T) return (rec2(idx, free)); if(dp[idx][free].count(oddsum - ketasum)) return (dp[idx][free][oddsum - ketasum]); if(oddsum + (mod_pow[S.size() - idx] - 1) - ketasum < T) return (0); int end = free ? 9 : S[idx] - '0'; int64 ret = 0; for(int i = 0; i <= end; i++) ret += rec(idx + 1, free | (i != end), ketasum + i, oddsum + i * mod_pow[S.size() - idx - 1]); return (dp[idx][free][oddsum - ketasum] = ret); } int main() { memset(dp2, -1, sizeof(dp2)); mod_pow[0] = 1; for(int i = 1; i < 19; i++) mod_pow[i] = mod_pow[i - 1] * 10; cin >> S >> T; cout << rec(0, false, 0, 0) << endl; }
D. Imbalanced Array
問題概要
長さ の数列 が与えられる.
ある数列の imbalance value を, 要素の最大値 - 最小値 と定義する.
数列の任意の subsegment について imbalance value を計算して, それらを足し合わたときの和を求めよ.
解法
実 家 の よ う な 安 心 感
だと思って解いたけど stack を使ったり分割統治したりする賢い解法があった. 悲しいね(?).
まず inbalance value の最大値と最小値は独立なので, 全体の最大値の和を計算して最小値の和を引く.
ぐっと睨むと subsegment の最小値を固定して考えたくなる. (最大値も反転させれば同様に求まる).
最小値として を含むような subsegment をそれぞれの について数える.
これは値 を含みつつ 未満の値を含まないものなので, 左右方向をみたときに 未満の値が出現する最も近い index が分かれば良い.
これは BIT でできるためうん.
あとははい.
ソース
#include<bits/stdc++.h> using namespace std; typedef long long int64; const int INF = 1 << 30; template< class T > struct BinaryIndexedTree1 { vector< T > data; BinaryIndexedTree1(int sz) { data.assign(++sz, -INF); } T sum(int k) { T ret = -INF; for(++k; k > 0; k -= k & -k) ret = max(ret, data[k]); return (ret); } void add(int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] = max(data[k], x); } }; template< class T > struct BinaryIndexedTree2 { vector< T > data; BinaryIndexedTree2(int sz) { data.assign(++sz, INF); } T sum(int k) { T ret = INF; for(++k; k > 0; k -= k & -k) ret = min(ret, data[k]); return (ret); } void add(int k, T x) { for(++k; k < data.size(); k += k & -k) data[k] = min(data[k], x); } }; template< class T > struct CumulativeSum { vector< T > data; CumulativeSum(int sz) : data(sz, 0) {}; void add(int k, int x) { data[k] += x; } void build() { for(int i = 1; i < data.size(); i++) { data[i] += data[i - 1]; } } T query(int k) { if(k < 0) return (0); return (data[min(k, (int) data.size() - 1)]); } }; int N, A[1000000], Latte[1000000], Malta[1000000]; int latte[1000000], malta[1000000]; vector< int > appear[1000001]; int main() { scanf("%d", &N); CumulativeSum< int64 > sum(N); for(int i = 0; i < N; i++) { scanf("%d", &A[i]); sum.add(i, A[i]); appear[A[i]].push_back(i); } sum.build(); BinaryIndexedTree1< int > bit1(1000001); BinaryIndexedTree2< int > bit2(1000001); BinaryIndexedTree1< int > bit3(1000001); BinaryIndexedTree2< int > bit4(1000001); for(int i = 0; i < N; i++) { Latte[i] = max(-1, bit1.sum(A[i])); bit1.add(A[i], i); } for(int i = N - 1; i >= 0; i--) { Malta[i] = min(N, bit2.sum(A[i] - 1)); bit2.add(A[i], i); } for(int i = 0; i < N; i++) { A[i] = 1000001 - A[i]; } for(int i = 0; i < N; i++) { latte[i] = max(-1, bit3.sum(A[i])); bit3.add(A[i], i); } for(int i = N - 1; i >= 0; i--) { malta[i] = min(N, bit4.sum(A[i] - 1)); bit4.add(A[i], i); } int64 ret = 0; for(int i = 0; i < 1000001; i++) { for(int j : appear[i]) { int64 L = Latte[j] + 1; int64 R = Malta[j] - 1; ret -= (R - j + 1) * (j - L + 1) * i; } for(int j : appear[i]) { int64 L = latte[j] + 1; int64 R = malta[j] - 1; ret += (R - j + 1) * (j - L + 1) * i; } } cout << ret << endl; }
E. Choosing The Commander
問題概要
個のクエリが与えられるので全て処理せよ.
- を 個集合に加える.
- を 個集合から消す.
- と集合の各要素の値と XOR をとった値が 未満であるものの個数を数える.
解法
Trieを貼ります(終わり)(これは罠でライブラリがないので終わらない).
クエリ に対しては値を 進数で表した時のあれを追加削除する.
クエリ に対してはいい感じにXORをとりながら上からくだっていく(解説になってないね).
雰囲気は の境界のノードをぐいーって感じでたどる.
ソース
なんか文字列を管理するTrieしかなかったので, 整数にしてたら時間がかかった.
#include<bits/stdc++.h> using namespace std; struct TrieNode { int nxt[2]; int exist; //vector< int > accept; TrieNode() : exist(0) { memset(nxt, -1, sizeof(nxt)); } }; struct Trie { vector< TrieNode > nodes; int root; Trie() : root(0) { nodes.push_back(TrieNode()); } virtual void direct_action(int node, int id) {} virtual void child_action(int node, int child, int id) {} void update_direct(int node, int id) { nodes[node].exist += id; } void update_child(int node, int child, int id) { nodes[node].exist += id; } void add(int str, int str_index, int node_index, int id) { if(str_index == -1) { update_direct(node_index, id); } else { const int c = (str >> str_index) & 1; if(nodes[node_index].nxt[c] == -1) { nodes[node_index].nxt[c] = (int) nodes.size(); nodes.push_back(TrieNode()); } add(str, str_index - 1, nodes[node_index].nxt[c], id); update_child(node_index, nodes[node_index].nxt[c], id); } } void add(int str, int id) { add(str, 29, 0, id); } int query(int str, int t, int str_index, int node_index, int mask) { if(str_index == -1) { return (0); } else { const int c = (str >> str_index) & 1; int next_mask = mask | (1 << str_index); int ret = 0; if(next_mask >= t) { if(c == 1) { if(~nodes[node_index].nxt[0]) ret += nodes[nodes[node_index].nxt[0]].exist; if(~nodes[node_index].nxt[1]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[1], mask); } else { if(~nodes[node_index].nxt[1]) ret += nodes[nodes[node_index].nxt[1]].exist; if(~nodes[node_index].nxt[0]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[0], mask); } } else { if(c == 1) { if(~nodes[node_index].nxt[0]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[0], next_mask); } else { if(~nodes[node_index].nxt[1]) ret += query(str, t, str_index - 1, nodes[node_index].nxt[1], next_mask); } } return (ret); } } int query(int str, int t) { return (nodes[0].exist - query(str, t, 29, 0, 0)); } }; int main() { int Q; scanf("%d", &Q); Trie trie; while(Q--) { int T, P, L; scanf("%d %d", &T, &P); if(T == 1) { trie.add(P, 1); } else if(T == 2) { trie.add(P, -1); } else { scanf("%d", &L); printf("%d\n", trie.query(P, L)); } } }