初回 -> はじめに
使っているマクロも初回の記事にあります。
レートが30も落ちました。大敗です。
簡単なはずの問題に時間をかけてしまって悔しいです。
記事にして記憶に留めて、次は速く解けたらいいなと思いながらこれを書いています。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 24min | 枝刈り全探索 | 32ms |
| B | 24min | 累乗と周期 | 11ms |
| C | 54min | 尺取り法 | 12ms |
| D | - | 数え上げ | 85ms |
まとめ
先にまとめを載せます。これ自体は最後に書いてます。
積の数え上げは枝刈り全探索をすると $\log$ のオーダーで計算できます。
ある数を累乗したときの1の位に注目すると、その数字には周期性があります。
さらに、10進数のときはその周期のLCMが $4$ になります。
自分で気づいてなかったけど、数え上げ苦手でした。。。
例の数え上げPDFを読もうかなって思いました。そしてこのPDF、奇遇にもARC113のWriterの方が作ったものでした。
A - ABC
int k;
cin >> k;
ll ans = 0;
for(int a = 1; a <= k; ++a) {
for(int b = 1; b <= k; ++b) {
if (a * b > k) break;
for(int c = 1; c <= k; ++c) {
if (a * b * c > k) break;
ans++;
}
}
} show(ans);
これは全探索ですね。
といっても $a, b, c$ をそれぞれ全範囲試すと $O(N^3)$ になってTLEしてしまいます。
そこで、 $ab$ または $ab*c$ が $k$を超えた時点で枝刈りします。そうすると、解空間にある点のみを列挙できます。
ループを1重減らしてさらに高速化もできるのですが、今回は計算が間に合うのでわかりやすさを優先しました。
計算量は$O(K \log^2{K})$ です。
なぜ $\log$ が出てくるかについては、「調和級数」で調べると分かります。
解空間については3次元空間になります。
今回の問題の解空間は $0 \leq x,\ 0 \leq y,\ 0 \leq z,\ xyz \leq k\ $ ですね。これをxyz空間にプロットすると曲面になります。
解答に直接役立つわけではないのですが、私はこのイメージを持って解きました。
B - A^B^C
// a^n % mod を計算する O(log n)
ll powmod(ll a, ll n, ll mod) {
ll ret = 1;
while (n > 0) {
if (n % 2 == 1) { ret = ret * a % mod; }
a = a * a % mod;
n /= 2;
}
return ret;
}
void solve()
{
ll a, b, c;
cin >> a >> b >> c;
a = a % 10;
if (b > 4) b = b % 4 + 4;
if (c > 4) c = c % 4 + 4;
a = powmod(a, pow(b, c), 10);
show(a);
}
これは $a$ の1桁目だけに注目すればいいですね。もう少し数学的に言うと、 $mod\ 10$ で考えればいいです。
また、 $mod\ 10$ の場合は $a^4$ をかけると1の位が元に戻ります。
数式で書くと $a^n\ \equiv a^{n+4}\ (mod\ 10)$ ですね。(私はこれをコンテストが終わってから知りました。)
ちなみに $0$, $1$, $5$, $6$ などは周期が4よりも小さいのですが、 $0$ ～ $9$ の周期のLCMをとって4で処理しています。
つまり $b$ と $c$ に $mod\ 4$ をすればこの問題を高速で解けます。
しかし１つ注意点があって、 $mod\ 4$ だと値の範囲が $0$ ～ $3$ になってしまいます。
このとき、 $b$ と $c$ のどちらかが $0$ になると値がおかしくなりますね。それを回避するために $+4$ しています。
$n$進数の場合、$n - 1$ と $ \sqrt{n-1}\ $ は特別な数字...みたいな話をどこかで聞いたことがあるのですが、それと関係あるのでしょうか。けっこう気になっているのですがこの話の大半がうろ覚えなので何もわからず、これだけ書いておくにとどめておきます。
計算量は $O( \log{ B }\ + \log{C} ) = O(\log{BC})$ ですね。
さらに、$4 \le B \le 7, 4 \le C \le 7$ なので実行時間はかなり短くなります。
C - String Invasion
string s;
cin >> s;
ll sz = s.length();
string ss = string(sz, '-');
char now = '-';
repi(i, 2, sz)
{
if (s[i - 2] == s[i - 1] && s[i - 1] != s[i] && s[i - 1] != now)
{
ss[i] = s[i - 1];
now = ss[i];
}
}
reverse(ALL(s));
reverse(ALL(ss));
now = '-';
ll ans = 0;
ll le = 0;
rep(i, sz)
{
if (ss[i] != '-')
{
ans += i + 1;
now = ss[i];
repie(j, le, i) if (s[j] == now) ans--;
i += 1;
le = i;
}
}
show(ans);
これ、苦手です。コンテスト後に振り返ってもまだよくわかっていないです。。。
解説が雑になっちゃってます。ごめんなさい。
入力文字列を前から見て、文字が変わる位置に印をつけます。
変わる後の文字が同じものは、一番最初に見つかった場所のみ印をつけます。
二番目以降に見つかった文字に印をつけた場合、 aabaabaabaab のようなときに答えが大きくなっちゃいます。
そのあと後ろから走査します (私は reverse して前から見ています) 。
印があったときはこれまでに見た文字がすべて同じ文字になるので、変わる文字数を加算します。
変わらない文字もあるので注意です。
これを文字列の先頭まで続けて、加算した結果が答えになります。
計算量について
初めの走査に$O(|S|)$
後ろからの走査に$O(|S|)$
変わる文字の判定に$O(|S|)$
かかるので、合計で$O(|S|)$ でこの問題が解けます。
D - Sky Reflector
ll n, m, k;
cin >> n >> m >> k;
if (n == 1 && k == 1)
{
show(k);
return;
}
if (n == 1)
{
cout << mint(k).pow(m) << endl;
return;
}
if (m == 1)
{
cout << mint(k).pow(n) << endl;
return;
}
mint ans = 0;
repi(i, 1, k + 1)
{
// 最小値の最大値が i
// かける
// 最大値が i 以上
ans += (mint(i).pow(n) - mint(i - 1).pow(n)) * mint(k - i + 1).pow(m);
}
show(ans);
こちらの mint を利用しています。
数え上げの問題ですね。自力では解けず、解説ACしました。悔しい。
解答への思考回路として、まず入力例１を見ます。
$N,M,K = 2$ なので、そのような数字の並べ方は縦が $2^2$ 通り、横が $2^2$ 通りで、全部で $2^2 * 2^2 = 16$ 通りありますね。
そのなかで問題の条件に合うものは$7$通りです。ここで、条件に合わないものを考えます。
これは実際にやってみると分かるのですが、条件に合わないものはどこかのマスが矛盾しますね。
もう少し考察を進めると、全マスで $A_i \le B_j$ が成り立っている必要があることがわかります。
その他にも条件はありそうと感じることもあるかもしれませんが、この問題は上の条件で必要十分です。
つまり、
①： $A_i$ の最大値が $k$
かつ、
②：$B_j$ が $k$ 以上
であるものの組み合わせを数え上げれば答えになります。
ここで、①が「$A_i$ が $k$ 以下」という条件ではなく、②が「$B_j$ の最小値が $k$」という条件でもないことに注意です。
①の組み合わせは
「$k$ 以下の数字からなる数列の組み合わせ」$-$ 「$k-1$以下の数字からなる数列の組み合わせ」
で求まります。
②の組み合わせはそのままですね。
そのうえで①の組み合わせと②の組み合わせを掛ければ、$A_i$ の最大値が $k$ かつ、$B_j$ が $k$ 以上なものの組み合わせの個数がわかります。
あとは $k$ について $1$ から $K$ まで変えながらその総和を計算すれば答えになります。
数式で表すと
①：$(k^N - (k - 1)^N)$
②：$(K - k + 1)^M$
なので、
$\sum^{K}_{k=1}(k^N - (k - 1)^N)*(K - k + 1)^M$
が答えになります。
また、 $N$ または$M$ が $1$ のときは式が壊れます。場合分けが必要です。
それに注意すればOKです。
解けると面白い問題でした。
ただ、数え上げが苦手なことが分かったので、例の数え上げPDFを読もうかなって思いました。
以上です。ありがとうございました。
以下は本番で書いたコードです。載せておいてなんですが参考にはなりません。自省の意味合いが10割です。
本番で通したコード
A - ABC
int n;
cin >> n;
ll ans = 0;
for (ll a = 1; a <= n; ++a)
{
ll bc = n / a;
for (ll b = 1; b <= min(bc, a); ++b)
{
ll cc = bc / b;
for(ll c = 1; c <= min(cc, b); ++c)
{
if (a == b && b == c) ans+= 1;
else if (a == b || a == c || b == c)
{
ans += 3;
}
else ans += 6;
}
}
}
show(ans);
B - A^B^C
// a^n % mod を計算する O(log n)
ll powmod(ll a, ll n, ll mod) {
ll ret = 1;
while (n > 0) {
if (n % 2 == 1) { ret = ret * a % mod; }
a = a * a % mod;
n /= 2;
}
return ret;
}
void solve()
{
ll a, b, c;
cin >> a >> b >> c;
a %= 10;
ll fa = a;
ll num = 0;
while(true)
{
fa *= a;
fa %= 10;
num++;
if (fa == a) break;
}
ll base = powmod(b, c, num);
ll ans = a;
rep(i, (base + num - 1) % num) ans = (ans * a) % 10;
show(ans);
}
C - String Invasion
string s;
cin >> s;
ll sz = s.length();
string imos = string(sz, '-');
repi(i, 2, sz)
{
if (s[i - 2] == s[i - 1] && s[i - 1] != s[i])
{
imos[i] = s[i - 1];
}
}
char now = '-';
ll minus = 0;
vector<ll> sum(sz, 0);
rep(i, sz)
{
if (imos[i] != now && imos[i] != '-')
{
sum[i] = 1;
now = imos[i];
ll idx = i + 1;
while((imos[idx] == '-' || imos[idx] == now) && idx < sz)
{
if (s[idx] == now)
{
minus++;
}
idx++;
}
i = idx - 1;
}
}
repi(i, 1, sz)
{
sum[i] += sum[i - 1];
}
repi(i, 1, sz)
{
sum[i] += sum[i - 1];
}
show(sum.back() - minus);