ABC405
Rated !
A - Is it rated?
Xが1のときと2のときで場合分けして条件分け
とてもシンプル
int R, X; cin >> R >> X;
if (X == 1) {
if (1600 <= R && R <= 2999)
cout << "Yes" << endl;
else cout << "No" << endl;
}
else {
if (1200 <= R && R <= 2399)
cout << "Yes" << endl;
else cout << "No" << endl;
}
B - Not All
C問以降と比べ自由度が高過ぎて悩んでしまった
forループでもとのリストの長さを短くしていき、
1-Mの数字で0個のものを更に2重ループで探した
流石に3重ループは避けられるなら避けたい
解説見たうえで考えるなら頭からその数字が過去に出たかboolリストを作って
全部trueになる＝trueにする行為をN回行う（それを数えれば良さそう
↓は時間内に提出したものなので3重ループ
int N, M; cin >> N >> M;
vector<int> A(N); for (auto &x : A) cin >> x;
for (int i = N; ; i--) {
for (int j = 1; j <= M; j++) {
int c = 0;
for (int k = 0; k < i; k++) {
if (A[k] == j) c++;
}
if (c == 0) {
cout << N - i << endl;
return 0;
}
}
}
C - Sum of Product
解説のように$S_{i}=\sum_{k=1}^{i}A_{i}$としたときに$\sum_{i=2}^{N}A_{i}S_{i-1}$となるのはわかったうえでちょっと違う手を取った
値の合計を2条したとき個々で掛け算したものとして表にする
例えば$(5+3+7+4)^2$を考える
| 5 | 3 | 7 | 4 | |
|---|---|---|---|---|
| 5 | 25 | 15 | 35 | 20 |
| 3 | 15 | 9 | 21 | 12 |
| 7 | 35 | 21 | 49 | 28 |
| 4 | 20 | 12 | 28 | 16 |
すると今回必要なのは以下の数字部分だとわかる
| 5 | 3 | 7 | 4 | |
|---|---|---|---|---|
| 5 | O | X | X | X |
| 3 | 15 | O | X | X |
| 7 | 35 | 21 | O | X |
| 4 | 20 | 12 | 28 | O |
不要であるOの部分は要素の2乗の合計で求められ
Xの部分は必要な部分と同じである
そのため合計の2条から要素を2条したものの合計を引き2で割れば出すことができる
int N; cin >> N;
vector<int> A(N); for (auto &x : A) cin >> x;
int64_t Sum1 = 0;
for (auto x : A) Sum1 += x;
Sum1 *= Sum1;
int64_t Sum2 = 0;
for (auto x : A) Sum2 += x * x;
Sum1 -= Sum2;
Sum1 /= 2;
cout << Sum1 << endl;
D - Escape Route
わかりやすくBFS
Queueに座標とどの方向から来た保存すれば大丈夫
複数queueに入る可能性があるのでqueueにいれるときだけでなくqueueの処理が始まる前に処理済みでないかをチェック
↑なぜか忘れていて1度WRを食らった
最近思っていた上下左右に1列ずつ挿入して範囲外エラー処理分岐を減らすあんがかなりうまく行った
vector<int> dh = {0, 1, 0, -1}, dw = {1, 0, -1, 0};
int H, W; cin >> H >> W;
vector<vector<char>> S(H + 2, vector<char>(W + 2, 'x'));
for (int h = 1; h < H + 1; h++) {
for (int w = 1; w < W + 1; w++) {
cin >> S[h][w];
}
}
queue<vector<int>> Q;
for (int h = 1; h < H + 1; h++) {
for (int w = 1; w < W + 1; w++) {
if (S[h][w] == 'E') {
Q.push({h, w, 0});
}
}
}
vector<char> DL = {'<', '^', '>', 'v'};
while (Q.size()) {
int h = (Q.front())[0];
int w = (Q.front())[1];
int d = (Q.front())[2];
Q.pop();
if (!(S[h][w] == '.' || S[h][w] == 'E')) continue;
if (S[h][w] != 'E') {
S[h][w] = DL[d];
}
for (int i = 0; i <= 3; i++) {
int th = h + dh[i];
int tw = w + dw[i];
if (S[th][tw] != '.') continue;
Q.push({th, tw, i});
}
}
for (int h = 1; h < H + 1; h++) {
for (int w = 1; w < W + 1; w++) cout << S[h][w];
cout << endl;
}
E - Fruit Lineup
苦手な 何通り・あまり問題
しかし！おそらく解説通りの方法で実装に成功
条件は
リンゴ＜バナナ
リンゴ＜ブドウ
オレンジ＜ブドウ
Aリンゴ Bオレンジ Cバナナ Dブドウ
自分はまずリンゴとブドウの関係に注目して、
この2つだけを見ると必ず1パターンになる
（種類と個数を表す
| リンゴ | バナナ |
|---|---|
| A | C |
ここにバナナをいれるのだが、オレンジをいれるときに一番左のブドウが重要になるのでそれだけ区別して考える
| リンゴ | バナナ | 左ブドウ | (ブドウ)と(バナナ)の混合 |
|---|---|---|---|
| A | i | 1 | (D-1) (C-i) |
バナナとブドウを混ぜたときにいくつかのバナナは一番左のブドウより左にあるだろう それをiとして表した形だ
ここにオレンジを追加するとブドウより左にあるものと混ざる
| (オレンジ)と(リンゴとバナナ)の混合 | 左ブドウ | (バナナ)と(ブドウ)の混合 |
|---|---|---|
| (B) (A+i) | 1 | (D-1) (C-i) |
左のリンゴとバナナというのは必ず左が全部リンゴであり右がバナナであるので1種類として考えると
2種類の順列として考えると$\frac{\left(B+A+i\right)!}{\left(B\right)!\cdot\left(A+i\right)!}$になる
同じように右のバナナとブドウの混合は$\frac{\left(D-1+C-i\right)!}{\left(D-1\right)!\cdot\left(C-i\right)!}$と表せる
つまり$\sum_{i=0}^{C}\frac{\left(B+A+i\right)!}{\left(B\right)!\cdot\left(A+i\right)!}\cdot\frac{\left(D-1+C-i\right)!}{\left(D-1\right)!\cdot\left(C-i\right)!}$これを求めればいい
値は100万未満なのでiでループかけそれぞれで計算を行い合計を出せば良い
998244353で割ったあまりであることと階乗をいちいち計算すると間に合わないので事前に全部計算することだけ気をつければ問題なし
モッドの割り算はとても難しいので事前に作ったのを引っ張り出してきた
（整理できてない範囲だったので危うく間に合わないところだった、、
int64_t mod (int64_t a) {
return (a % MOD + MOD) % MOD;
}
int64_t modinv (int64_t a, int64_t b) {
if (a % b == 1) return 1;
return (1 - b * modinv(b , a % b)) / (a % b);
}
int64_t mdiv (int64_t a, int64_t b) {
return mod(a * modinv(b, MOD));
}
int64_t A, B, C, D; cin >> A >> B >> C >> D;
int64_t Sum = 0;
vector<int64_t> fact(10000000, 1);
int64_t f_tmp = 1;
for (int64_t i = 1; i < 10000000; i++) {
f_tmp *= i;
f_tmp %= MOD;
fact[i] = f_tmp;
}
for (int64_t i = 0; i <= C; i++) {
int64_t a = mdiv(mdiv(fact[C - i + D - 1], fact[C - i]), fact[D - 1]);
int64_t b = mdiv(mdiv(fact[B + A + i], fact[B]), fact[A + i]);;
int64_t c = (a * b) % MOD;
Sum = (Sum + c) % MOD;
}
cout << Sum << endl;
まとめ
5冠達成できてよかった！
が、タイムが102分とだいぶ遅かった(1ペナ)
一応スコア1234と水パフォ
出てレート上がったがもう少し頑張れたのでは？と思うが3ヶ月空きの復帰戦だから仕方ないか、
5月10日