[PGBattle2021] ましゅまろ反省会
[Q] https://products.sint.co.jp/q_list_2021
30分くらい。
TOPSIC > 使い方 > 練習問題
https://pgbattle2022.topsic.org/practice
から提出ができました。
ライブラリ省略。
[A] 物理現象グラフィックバトル
文章通りの計算
int main() {
cincout();
ld X, Y, K;
cin >> X >> Y >> K;
cout << (Y - K / X) << endl;
}
[B] ゼロのない整数
'0'をみつけたら、以降をすべて'1'にする
見つからなかったらそのまま
int main() {
cincout();
string X;
cin >> X;
bool fin = false;
rep(i, (ll)X.size()) {
if (X[i] == '0') { // '0'が見つかったら、以降は'1'固定
fin = true;
}
if (fin) {
X[i] = '1';
}
}
cout << X << endl;
}
[C] 一点封鎖
全通りから、通っちゃいけない場所を通る組み合わせを除く。
MOD使えるかどうか試されるの、プログラマの素質とあんまり関係ない感じがする。
int main(){
cincout();
COMinit();
ll N, M, A, B;
cin >> N >> M >> A >> B;
mint all = COM(N+M, N);
mint dis = COM(A+B, A) * COM(N-A + M-B, N-A);
cout << (all-dis) << endl;
}
[D] 無双関数
・考察
1. i=0を固定したとき、j=1, j=2, j=3, ... を進めてシミュレートする。
2. 数字が1回でも重複してしまったら、以降のj<Nは何をとろうとも、f()は0になる。
3. しゃくとりで、重複がない限界まで進める。
4. tail - headの距離が、Sのとりうる範囲。
5. Sの累積和をとればO(1)で解答スコアを加算できる。
6. A[]について。1e9までとるので、配列にできない。数字がユニークかどうかだけ知りたいので、座標圧縮していい。
int main() {
cincout();
ll N;
cin >> N;
vector<ll> A(N);
ll S[N];
rep(i, N) { cin >> A[i]; }
rep(i, N) { cin >> S[i]; }
// Aの座標圧縮
comp(A);
// Sの累積和
mint acc[N]{};
acc[0] = S[0];
rep(i, N - 1) { acc[i + 1] = acc[i] + S[i + 1]; }
// しゃくとり
bool used[200020]{};
ll tail = 0;
mint ans = 0;
rep(head, N) {
while (tail < N && used[A[tail]] == false) { // おしりを進める
used[A[tail]] = true;
++tail;
}
ll d = tail - head - 1;
ans += acc[d];
used[A[head]] = false; // 先頭の削除
}
cout << ans << endl;
}
この記事が気に入ったらサポートをしてみませんか?