C,D問題を通しての2完で322位でした。
レートは1325から1308へ。完全に停滞している。
すっかり忘れててchokudaiさんのツイートを見てからの参加だったので11分遅れでのスタートでした。
C問題 『Factors of Factorial』
最初約数の個数を求めるのはじゃなくてだと思い込んでしまったのでだから素数は37まで容易すればいいかな〜と気軽に考えていたけど、サンプル合わないところでやっと気づいた。どうしようか悩んだけど、結局ググッて997までの素数をコピペしてきて凌ぐことに。その際にが大きい素数になった時のこと考えてではにするみたいな意味不明な処理を消し忘れていて1WA出してしまった。
#include <bits/stdc++.h>
using namespace std;
const int MOD = pow(10, 9) + 7;
int m[168] = {0};
int p[] = {2 ,3 ,5 ,7 ,11 ,13 ,17 ,19 ,23 ,29 ,31 ,37 ,41 ,43 ,47 ,53 ,59 ,61 ,67 ,71, 73 ,79 ,83 ,89 ,97 ,101 ,103 ,107 ,109 ,113 ,127 ,131 ,137 ,139 ,149 ,151 ,157 ,163 ,167 ,173, 179 ,181 ,191 ,193 ,197 ,199 ,211 ,223 ,227 ,229 ,233 ,239 ,241 ,251 ,257 ,263 ,269 ,271 ,277 ,281, 283 ,293 ,307 ,311 ,313 ,317 ,331 ,337 ,347 ,349 ,353 ,359 ,367 ,373 ,379 ,383 ,389 ,397 ,401 ,409, 419 ,421 ,431 ,433 ,439 ,443 ,449 ,457 ,461 ,463 ,467 ,479 ,487 ,491 ,499 ,503 ,509 ,521 ,523 ,541, 547 ,557 ,563 ,569 ,571 ,577 ,587 ,593 ,599 ,601 ,607 ,613 ,617 ,619 ,631 ,641 ,643 ,647 ,653 ,659, 661 ,673 ,677 ,683 ,691 ,701 ,709 ,719 ,727 ,733 ,739 ,743 ,751 ,757 ,761 ,769 ,773 ,787 ,797 ,809, 811 ,821 ,823 ,827 ,829 ,839 ,853 ,857 ,859 ,863 ,877 ,881 ,883 ,887 ,907 ,911 ,919 ,929 ,937 ,941, 947 ,953 ,967 ,971 ,977 ,983 ,991 ,997
};
int main()
{
int N;
scanf("%d", &N);
for (int j = N; j >= 2; j--) {
N = j;
for (int i = 0; i < 168; i++) {
while (N % p[i] == 0) {
m[i]++;
N /= p[i];
}
}
}
long long ans = 1;
for (int i = 0; i < 168; i++) {
ans *= m[i] + 1;
ans %= MOD;
}
printf("%lld\n", ans);
}
D問題 『Walk and Teleport』
普通に貪欲やるだけでは? と思って提出したらWA。理由は同士の掛け算によるオーバーフローなんだけど、このときには気づかず「一番大きいギャップにあたったら一度一番右までテレポートしなきゃいけないんだ」とかわけのわからない考察を始めてしまい、めちゃくちゃ時間かかってしまった&3WA。変数をとりあえずlong long
で取る癖をつけておいた方が(競プロ的には)いいんだろうなぁ。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N, A, B;
vector<int> X;
scanf("%d%d%d", &N, &A, &B);
X.resize(N + 1);
for (int i = 1; i <= N; i++) {
scanf("%d", &X[i]);
}
long long ans = 0;
for (int i = 1; i <= N - 1; i++) {
ans += min((long long)A * (long long)(X[i + 1] - X[i]), (long long)B);
}
printf("%lld\n", ans);
}
E問題 『Grouping』
さっぱり方針がわからなかった。配点から見てそんなに難しくはないのかなと思ったけど、逆に典型題みたいな感じだと僕にはわからないと思ってほぼ諦めてしまった。
解説読んだら「DP[i][j] = i人以下のグループのみでj人使っている場合の数」というDPを考えるとのこと。DPで考えるなら最終的な[N]]などが答えになっているはずで、どういうものか全然思いつかなかったんだけど、なるほどこうするものか。2次元的なDPを解いた量が圧倒的に少なすぎて発想が出てこないな。の大きさ制限からなんとなく察し取れたりするものなんだろうか。
F問題 『Yakiniku Restaurants』
おそらく通すことはできないとわかってはいたけど、E問題よりもこっちのほうが考えてるふりができるので問題のページを開いて眺めていた。なにもわからなかった。