CODE FESTIVAL 2016 qual A. C - 次のアルファベット / Next Letter
解き方
この操作をして, 辞書順を小さくするためには, 'b'より大きいものを一周させて'a'にする以外ない.
辞書順最小にするためには, 手前から見ていって, 'a'にできるものは'a'にして, それ以外は無視する と言った処理をすればよい.
この処理は, 回必ず行わなければならないので, 余ったやつも必ず処理をしなければならない。
まず, アルファベットを何周もさせることができるので, 残ったやつから'z'-'a'+1分だけMODを取った値にすることができる.
さらに残ったものは, 後ろから回していく.(後ろの1文字だけ変更になるはず)
SourceCode
void solve() { string S = in(); ll K = in(); REP(i, S.size()) { if (K <= 0) break; ll cost = 'z' - S[i] + 1; cost %= ('z' - 'a' + 1); if (K - cost >= 0) { S[i] = 'a'; K -= cost; } } if(K > 0) K %= ('z' - 'a' + 1); RFOR(i,0,S.size()) { if (K <= 0) break; ll cost = min((ll)K, (ll)('z' - S[i])); S[i] += cost; K -= cost; } cout << S << endl; }
Codeforces #712 Div.2 D. Memory and Scores
要約
が与えられる.
: Memoryさんの初期点数
: 相手の初期点数
: 1ターンにの点数を得ることができる
: 2tターン行う
Memoryさんがかつことができるのは何通りか(MOD 1e9+7)
以下のようなdpを組む
その時間(time)で, Memoryさんのスコア-相手さんのスコアがdiffのときの場合の数
更新方法は簡単で,
- sumはしゃくとり的にやって計算量を減らす.
- 要素数は なので注意する(1敗)
最終的に, の部分がMemoryさんが勝つ場合の数なので,
が答えになる
配列の最大要素, くらいとっとけばいいと思ったけどなんかうまくいかなかった.
また, このままだと負の要素にアクセスすることになるので適当にオフセットかける
SourceCode
const int MOD = 1e9+7; void solve() { ll A, B, K, T; cin >> A >> B >> K >> T; //dp[time][diff] := cnt vector<vector<ll> > dp(2, vector<ll>(2*1000*(210) + 1)); int offset = 1000*(210); int cur = 0, tar = 1; if (A - B + offset <= 0) { cout << 0 << endl; return; } dp[tar][A-B+offset] = 1; for (int i = 0; i < 2 * T; ++i) { //REP(i, dp[tar].size()) cout << dp[tar][i]; //cout << endl; ll sum = 0; //全範囲更新 TLEしそうだったら頑張る しゃくとり的に REP(j, 2 * K+1) sum = (sum+dp[tar][j])%MOD; FOR(j, K, dp[cur].size()-K-1) { dp[cur][j] = sum; sum = (sum-dp[tar][j - K] + MOD)%MOD; sum = (sum+dp[tar][j + K + 1])%MOD; } swap(cur, tar); } //REP(i, dp[tar].size()) cout << dp[tar][i]; //cout << endl; ll res = 0; //REP(j, dp[tar].size()) { FOR(j,offset+1,dp[tar].size()){ res = (res + dp[tar][j]) % MOD; } cout << res << endl; }
謝辞, 参考
arrogantldiotさんのソースコードを参考にさせていただきました
codeforces.com
Codeforces #712 Div.2 C. Memory and De-Evolution
要約
正三角形2つが与えられる.
それぞれの辺の長さは, [tex:x, y (y
やること
非縮退三角形とは, 以下の条件を満たす三角形(つまり普通の三角形) 三角形の辺の長さを とすると,
少し変形して, 辺に着目すると, 以下のような式になる
辺の長さを減らしていく方向に考えると, 他の辺を減らす量が減ってしまうことがあり, 貪欲に考えることができない.
しかし, 辺の長さを増やしていく方向に考えると, 増やせば増やすほど他の辺もいっぱい増やせるので貪欲に増やすことができる
不等号が含まない不等号なのに注意して,
となるようにする.
同様に, をから初めて順に大きくしていってになった時点で終了
SourceCode
void solve() { //y -> x int x, y; cin >> x >> y; vector<int> vx(3, y); vector<int> vy(3, x); ull cnt = 0; ull ok = 0; for (ull i = 0;; ++i) { int tar = i % 3; if (vx[tar] != x) { vx[tar] = min(vx[(tar + 1) % 3] + vx[(tar + 2) % 3] - 1, x); ++cnt; } else ok |= 1 << tar; if (ok == (1 << 3) - 1) break; } cout << cnt << endl; }
Codeforces #712 Div.2 B. Memory and Trident
要約
R,L,U,D (Right, Left, Up, Down)の4つからなる文字列が与えられる. それぞれの方向に1ずつ移動する
Memoryさんは, 文字を書き換える能力がある.
文字を書き換えて, 最終的に原点に戻ってくるようにしたい.
なん文字書き換えればよいか. 無理のときは-1を出力する
やること
各文字の出現回数を数える.
RとL, UとDが両方共それぞれ偶数同士, 奇数同士ならばOK
また,
RとL, UとDが両方共それぞれ偶数奇数同士ならば, 一文字書き換えると上記の条件に当てはまるのでOK
それ以外の場合は-1を出力する.
偶数奇数同士の時は, max(R,L) -> min(U,D) に変化させてやる.
最後に, max(R,L) - ave(R,L) + max(U,D) - ave(U,D)の個数+前処理の変化回数(1か0)が答えになる
SourceCode
void solve() { string str = in(); int mapping['Z']; mapping['R'] = 0; mapping['L'] = 1; mapping['U'] = 2; mapping['D'] = 3; vector<int> cnt(4); int res = 0; REP(i,str.size()) ++cnt[mapping[str[i]]]; if (cnt[0] > cnt[1]) swap(cnt[0], cnt[1]); if (cnt[2] > cnt[3]) swap(cnt[2], cnt[3]); int lsb[4]; REP(i, 4) lsb[i] = (cnt[i] & 1); if (lsb[0] != lsb[1] and lsb[2] != lsb[3]) { --cnt[1]; ++cnt[2]; ++res; } else if(not(lsb[0] == lsb[1] and lsb[2] == lsb[3])){ cout << -1 << endl; return; } cout << cnt[1] - (cnt[0] + cnt[1]) / 2 + cnt[3] - (cnt[2] + cnt[3]) / 2 + res << endl; }
Codeforces #712 Div.2 A. Memory and Crow
要約
数列 が与えられる.
を満たすような を求めよ
SourceCode
今回からSolve関数のみとなります
void solve() { int N = in(); vector<int> b = in(N); vector<int> res(N); int add = 0; res[N - 1] = b[N - 1]; add += res[N - 1]; RFOR(i, 0, N-1) { add *= -1; res[i] = b[i] - add; add += res[i]; } REP(i, N) cout << res[i] << (i == N - 1 ? "\n" : " "); }
c++でpython風のinput()を作った(戻り値型推論的なやつ)
Motivation
int i = input();
string s = input();
みたいなのをしたい気分になった
SourceCode
以下のやつをコピペすれば動きます
struct input_returnner { template<typename T>operator T() const { T t; cin >> t; return t;} }; input_returnner input() { return input_returnner(); } /// ---template--- int main(void) { string a = input(); cout << a << endl; return 0; }
簡単な解説
変換演算子を持つ独自クラスを返すクラスを作って, input_returnner{}
とかでもかけるんだけどクッソ気持ち悪かったので関数で囲ってやった
あとがき
でも
vector<int> v(N); for(auto &a:v) cin >> a;
って普段やってるしあまり活躍しなさそう
参考文献
AGC002 D. Stamp Rally
問題
やること
- 二分木探索で, 最大のスコアを探索する
- midまでの辺のfromとtoのノードを, union_findでuniteする
- union_findでは同じグループの数をuniteするときに一緒に計算しておく
- を含むグループの数と, を比較し, high, lowを更新する
これを 回処理すると, 間に合わないので並列に行う.
以降実装とコツ
- 多分再帰で実装したほうが良い.
- f(depth, low, high, その範囲で計算する人たち) みたいな感じで実装する
- depthがなぜ必要なのかは後で
- と が同じグループに属している時, 片方のグループのみで数える
- 重複は数えないため
- カウントして, 同じグループに属していたら2で割るみたいな処理をすれば良い
- 0人のグループになれば, 計算をしないようにする(1敗)
- union_findは, あらかじめ個作っておいて, 再利用する
- コンストラクタもかかるためかかる時間がバカにならない
- 再帰をかける順番を工夫して, midが小さい方から探索するようにする
- それぞれの深さで使用するunion_findを分ける. 深さはくらいなので, それをあらかじめ用意しておく
ソースコード
今回のソースコードは特にやばい
#include <iostream> #include <queue> #include <map> #include <list> #include <vector> #include <string> #include <stack> #include <limits> #include <cassert> #include <fstream> #include <cstring> #include <cmath> #include <bitset> #include <iomanip> #include <algorithm> #include <functional> #include <cstdio> #include <ciso646> using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define inf 0x3f3f3f3f #define INF INT_MAX/3 #define PB push_back #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define SET(a,c) memset(a,c,sizeof a) #define CLR(a) memset(a,0,sizeof a) #define pii pair<int,int> #define pcc pair<char,char> #define pic pair<int,char> #define pci pair<char,int> #define VS vector<string> #define VI vector<int> #define DEBUG(x) cout<<#x<<": "<<x<<endl #define MIN(a,b) (a>b?b:a) #define MAX(a,b) (a>b?a:b) #define pi 2*acos(0.0) #define INFILE() freopen("in0.txt","r",stdin) #define OUTFILE()freopen("out0.txt","w",stdout) #define in scanf #define out printf #define ll long long #define ull unsigned long long #define eps 1e-14 #define FST first #define SEC second class union_find { private: vector<int> par; vector<int> rank; vector<int> count; public: union_find(int N):par(N), rank(N, 0), count(N, 1) { for (int i = 0; i < N; ++i) { par[i] = i; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) { count[y] += count[x]; par[x] = y; } else { count[x] += count[y]; par[y] = x; if (rank[x] == rank[y]) rank[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int getCount(int x) { return count[find(x)]; } void clean() { par = vector<int>(par.size()); } }; struct Edge { int from; int to; Edge(int f, int t) :from(f), to(t) {} }; vector<int> res; vector<Edge> e; int memo_f[100001] = {}; int N, M, Q; vector<tuple<int, int, int> > q; vector<pair<int, union_find> > uf; void f(int depth, int low, int high, vector<int> people) { if (depth == uf.size()) uf.push_back({ 0,union_find(N) }); if (depth < uf.size()) assert(1); if (high - low <= 1) { for (auto &p : people) { res[p] = high; } return; } int mid = (high + low) / 2; FOR(i, uf[depth].first, mid) uf[depth].second.unite(e[i].from, e[i].to); vector<int> OKPeople; vector<int> NGPeople; for (auto &p : people) { int x, y, z; tie(x, y, z) = q[p]; int div = (uf[depth].second.same(x, y) + 1); if ((uf[depth].second.getCount(x) + uf[depth].second.getCount(y))/div >= z) OKPeople.push_back(p); else NGPeople.push_back(p); } uf[depth].first = mid; if(not OKPeople.empty()) f(depth+1, low, mid, OKPeople); if(not NGPeople.empty()) f(depth+1, mid, high, NGPeople); } int main() { memset(memo_f, -1, sizeof(memo_f)); cin >> N >> M; REP(i, M) { int a, b; cin >> a >> b; --a; --b; e.emplace_back(a, b); } int Q; cin >> Q; res.resize(Q); REP(i, Q) { int x, y, z; cin >> x >> y >> z; --x, --y; q.push_back(make_tuple(x, y, z)); } vector<int> people; REP(i, Q) people.push_back(i); f(0, 0, M, people); for (auto &a : res) { cout << a << endl; } return 0; }
感想
最近はあまり時間がないので解けた問題+1って感じだけどこの問題を解いた
永続配列を使ってunion_find解もあるらしく, 研究が辛くなったら実装しようと思う