[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;
}