Dまで
A. Divisibility Problem
問題文
正の整数aとbが与えられる
一回の操作でaをa+1に変更できる
aがbで割り切れるようにするのに最小で何回操作が必要か
解法
aをbで割ったときの値を切り上げたものからaを引いたものが答え
int main(){ cin.tie(0); ios::sync_with_stdio(false); int Q; cin >> Q; while(Q--){ ll a, b; cin >> a >> b; if(a % b == 0) cout << 0 << endl; else{ ll cnt = (a + b - 1) / b; cout << b * cnt - a << endl; } } }
B. K-th Beautiful String
問題文
n-2個の'a'と2個の'b'からなる文字列がある
この文字列を並び替えて作れる文字列のうち、辞書順でK番目のものを出力せよ
解法
aaa...bbが最小で、
aaa...bab, aaabaab, ..., のように左側のbを跨ぐaの個数を考えると、aの数に応じて辞書順は1 + 2 + 3 + ...のように増えていく
なので等差数列の和を考えてKを超えない最大の整数を求めてあげて、後は差分で愚直にやればおっけー
int main(){ cin.tie(0); ios::sync_with_stdio(false); int Q; cin >> Q; while(Q--){ ll n, k; cin >> n >> k; ll cnt = 0; for(ll i = 1;i*(i+1)/2<k;i++){ cnt = i; } k--; string ans = ""; ans += string(n - 2 - cnt, 'a'); k -= (cnt * (cnt + 1) / 2); ans += 'b'; if(cnt - k > 0) ans += string(cnt - k, 'a'); ans += 'b'; if(k > 0) ans += string(k, 'a'); cout << ans << endl; } }
C. Ternary XOR
問題文
Ternary number であるxが与えられる
ternary XOR operation ⊙を2つのternary number aとbを用いて次のように定義する
𝑐=𝑎⊙𝑏 , 𝑐𝑖=(𝑎𝑖+𝑏𝑖)%3
この時、𝑎⊙𝑏 = x かつ max(a, b)が最小となるようなaとbを出力せよ
解法
先頭から見ていって'1'が出てきたかどうかで場合分け
'1'が初めて出てきたらaの方に'1'をつけてあげる
その後はbの方に数字を押し付けて上げていけば達成できる
int main(){ cin.tie(0); ios::sync_with_stdio(false); int Q; cin >> Q; while(Q--){ int n; string s; cin >> n >> s; string a = "", b = ""; bool one = true; REP(i,n){ if(s[i] == '2'){ if(one){ a += '1'; b += '1'; } else{ a += '0'; b += '2'; } } else if(s[i] == '1'){ if(one){ a += '1'; b += '0'; one = false; } else{ a += '0'; b += '1'; } } else{ a += '0'; b += '0'; } } cout << a << endl; cout << b << endl; } }
D. Carousel
問題文
n個の動物の絵が環状に並んでいる
i番目の動物の絵の種類はである
n個の絵に対し次の条件を満たすように色を塗っていく
・隣合う絵のうち、絵の種類が異なる場合、異なる色で塗る
この条件を満たすように色を塗っていく時、最小の色の数を出力し、その塗り方の一例を出力せよ
解法
本番で解けなかった
多くても3色で十分なのは良かったけど場合分けが上手く出来なかった
まず、絵の種類が1個なら1色で塗れる
nが偶数なら2色を交互に塗っていくことで達成できる
nが奇数のとき、同じ種類の絵が連続して並んでいる箇所があれば、そこを基準にnが偶数のときに帰着出来るので2色で塗れる
そうでなければ3色で塗る必要がある
int main(){ cin.tie(0); ios::sync_with_stdio(false); int Q; cin >> Q; while(Q--){ int n; cin >> n; vector<int> t(n); REP(i,n) cin >> t[i]; bool monotone = true; REP(i,n-1) if(t[i] != t[i+1]) monotone = false; if(monotone){ cout << 1 << endl; REP(i,n) cout << 1 << " "; cout << endl; } else{ if(n % 2 == 0){ cout << 2 << endl; REP(i,n) cout << (i % 2) + 1 << " "; cout << endl; } else{ int same = -1; REP(i,n) if(t[i] == t[(i+1)%n]) same = i+1; if(~same){ cout << 2 << endl; REP(i,same) cout << (i % 2) + 1 << " "; for(int i=same;i<n;i++) cout << ((i + 1) % 2) + 1 << " " ; cout << endl; } else{ cout << 3 << endl; REP(i,n-1) cout << (i % 2) + 1 << " "; cout << 3 << endl; } } } } }
おわりに
Dギャグっぽい?ギャグが解けない
Eぱっと見た感じ良さそうな問題だから解いておきたい