Codeforces Round #653 (Div. 3) 感想
Dashboard - Codeforces Round #653 (Div. 3) - Codeforces
感想
5完。
今回はA,B,Dが割り算関連の問題だった。こどふぉ、割り算とか約数・倍数が好きすぎやろ。
unratedなのでカフェインを入れずに参加したら、眠すぎてバグを出しまくった。
ほんとうはratedでもカフェインを入れずに参加したいけど、ダメそうだ。
A - Required Remainder
を整数として
と置ける。よって、
を満たす最大の
を求めればよくて、それは
。
提出コード
void solve() {
int Q;
cin >> Q;
while (Q--) {
ll X, Y, N;
cin >> X >> Y >> N;
ll p = (N - Y) / X;
cout << p * X + Y << "\n";
}
}
B - Multiply by 2, divide by 6
が2と3以外に素因数を持っていたらダメ。2と3以外に素因数を持たないとき
とおける。
できる操作は2を掛けるか6で割るかの2つで、前者をすると2の指数が1増えて、 後者をすると2と3の指数がそれぞれ1下がる。
なので、
だとアウトで、
のとき答えは
となる。
提出コード
void solve() {
int Q;
cin >> Q;
while (Q--) {
ll N;
cin >> N;
ll q2 = 0, q3 = 0;
while (N % 2 == 0) {
++q2;
N /= 2;
}
while (N % 3 == 0) {
++q3;
N /= 3;
}
bool ok = true;
if (N > 1) {
ok = false;
}
if (q2 > q3) {
ok = false;
}
if (ok) {
cout << q3 + (q3 - q2) << "\n";
}
else {
cout << -1 << "\n";
}
}
}
C - Move Brackets
「まず、 の各文字を
(と)の数を数えながら左から右に見ていったときに、
(の数より)の数の方が大きくなる回数 を求める。
次に、今度は逆に右から左に見ていったときに、
)の数より(の数の方が大きくなる回数 を求める。
そして、
を出力する。」
というエスパーを無証明で投げるとなんか通った（懺悔）
提出コード
void solve() {
int Q;
cin >> Q;
while (Q--) {
ll N;
string S;
cin >> N >> S;
ll ans = L_INF;
ll cur = 0;
ll cnt = 0;
for (ll i = 0; i < N; i++) {
if (S[i] == '(') {
++cur;
}
else {
--cur;
}
if (cur < 0) {
++cnt;
cur = 0;
}
}
ans = cnt;
cur = 0;
cnt = 0;
for (ll i = N - 1; i >= 0; i--) {
if (S[i] == ')') {
++cur;
}
else {
--cur;
}
if (cur < 0) {
++cnt;
cur = 0;
}
}
ans = min(ans, cur);
cout << ans << "\n";
}
}
コンテスト後によく考えると、方針はあってたけど と
は必ず同じ数になることが分かった。
を左から右に見て、貪欲に
(と)のペア（ただし、(は)より左になければならない）を作り、
ペアを作れた括弧を「良い括弧」、作れなかった括弧を「悪い括弧」と呼ぶことにする。
上の は悪い
)の数と同義である。
また、操作の目的は悪い)（または(）の個数を0にすることである。
で、どのように操作しても新たにできるペアの個数は高々1つで、かつ、
悪い括弧に対して操作を行うと必ず1つ新たにペアができるから、答えは に等しい。
貪欲にペアを作る方向を逆にすると同様にして答えが であることも示せるから
。
コンテスト後提出コード
void solve() {
int Q;
cin >> Q;
while (Q--) {
ll N;
string S;
cin >> N >> S;
ll cur = 0;
ll cnt = 0;
for (ll i = 0; i < N; i++) {
if (S[i] == '(') {
++cur;
}
else {
--cur;
}
if (cur < 0) {
++cnt;
cur = 0;
}
}
cout << cnt << "\n";
}
}
D - Zero Remainder Array
と
は
で置き換える。そして、最初から
のものは以下では無視する。
は各操作ごとに0～k-1をぐるぐる回っていく。
とおいて、各
にはそれぞれ
を当てればいいことになるけど、
の値が同じものがあるとき、それらを処理するためには
はその重複した個数の分だけ0~k-1をぐるぐる回らなければならない。
を「
を満たす
の個数」として、
を最大化する
の中で最も大きいものを
としたとき、
答えは
となる。
を管理するのにunordered_mapを使ったらTLEしてびっくり。
mapに変えると無事にACした。unordered_mapの最悪計算量は ！！！！！
提出コード
void solve() {
int Q;
cin >> Q;
map<ll, ll> ns;
while (Q--) {
ll N, K;
cin >> N >> K;
ns.clear();
for (ll i = 0; i < N; i++) {
ll a;
cin >> a;
if (a % K != 0) {
++ns[K - a % K];
}
}
ll idx_mx = -1, mx = -1;
for (const auto& [a, v] : ns) {
if (v > mx) {
idx_mx = a;
mx = v;
}
else if (v == mx && a > idx_mx) {
idx_mx = a;
}
}
ll ans;
if (mx == -1) {
ans = 0;
}
else {
ans = (mx - 1) * K + idx_mx + 1;
}
cout << ans << "\n";
}
}
E1 - Reading Books
「AliceもBobも好きな本を読む数」さえ固定してしまえば、あとは全て貪欲に決められる。
提出コード
void solve() {
ll N, K;
cin >> N >> K;
Vl abs, as, bs;
for (ll i = 0; i < N; i++) {
ll t, a, b;
cin >> t >> a >> b;
if (a == 1 && b == 1) {
abs.emplace_back(t);
}
else if (a == 1) {
as.emplace_back(t);
}
else if (b == 1) {
bs.emplace_back(t);
}
}
sort(abs.begin(), abs.end());
sort(as.begin(), as.end());
sort(bs.begin(), bs.end());
ll nab = (ll)abs.size();
ll na = (ll)as.size();
ll nb = (ll)bs.size();
Vl cumab(nab + 1), cuma(na + 1), cumb(nb + 1);
for (ll i = 0; i < nab; i++) {
cumab[i + 1] = cumab[i] + abs[i];
}
for (ll i = 0; i < na; i++) {
cuma[i + 1] = cuma[i] + as[i];
}
for (ll i = 0; i < nb; i++) {
cumb[i + 1] = cumb[i] + bs[i];
}
ll ans = L_INF;
for (ll i = nab; i >= 0; i--) {
ll x = max(K - i, 0ll);
if (x > na || x > nb) {
break;
}
ll t = cumab[i] + cuma[x] + cumb[x];
ans = min(ans, t);
}
if (ans != L_INF)
cout << ans << "\n";
else
cout << -1 << "\n";
}
E2 - Reading Books (hard version)
解けなかったし、まだACしていない。これも「AliceもBobも好きな本を読む数」を固定すれば解けそうな雰囲気があるけどどうだろ（わからん）。
F- Cyclic Shifts Sorting
読んでない。
