初回 -> はじめに
ABC101を解きました。
3完です！
Dは難しくて解けていません。
| 問題 | 時間 | アルゴリズム | 実行時間 |
|---|---|---|---|
| A | 2min | - | 8ms |
| B | 3min | - | 6ms |
| C | 9min | - | 7ms |
A - Eating Symbols Easy
string s;
cin >> s;
int ans = 0;
for(const auto& c : s)
{
if (c == '+') ans++;
if (c == '-') ans--;
}
cout << ans;
+がきたら1増やして、-がきたら1減らせば答えがわかります。
B - Digit Sums
int n;
cin >> n;
int num = n;
int a = 0;
while(num > 0)
{
a += num % 10;
num /= 10;
}
cout << (n % a == 0 ? "Yes" : "No");
%10の値を足して、10で割ることを繰り返せば各桁の和が求まります。
nの元の値は後で使うので、二次変数numで受けています。
C - Minimization
ll n, k;
cin >> n >> k;
if (n == k) cout << 1;
else cout << 1 + (n - k - 1) / (k - 1) + 1;
入力は数列 $A_i$ もあるのですが、結論から言うと不要です。
NとKだけで答えがわかります。
$A_i$ は $1,2,...,N$ を並び替えたものなので、 $1,2,...,N$ をそれぞれちょうど1つずつ含みます。
つまり、数列内の最小値は必ず1になりますね。
数列の要素をすべて等しくすることが目的で、最小値が必ず1なので、最後は1がN個つづく形になります。
ここで、連続したK個の要素でN個の要素をカバーすることを考えます。$A_i$ の値についてはいったん忘れます。
最小個数でカバーする場合、N / K個の範囲でカバーできますね。
ですが、ここではK個のそれぞれの範囲は隣の範囲と1要素分だけ重複するようにします。
こうすると、ある範囲内を最小要素で置き換えた場合、となりの範囲にもその結果を影響させられます。
この形にしたら、あとは置き換え処理の順番を考えます。
目的は全要素を1に書き換えることでしたね。$A_i$ のうち1が現れるのは1か所だけです。
そのため、Kの範囲のうち1を含むもの1番目に、あとは隣接する範囲から順に処理していきます。
そうすると、最小手順で1がN個つづく形になります。
この個数は1 + (n - k) / (k - 1) ですね。
割り算の部分は切り上げです。切り上げに対応するため、コードでは少し違う処理もしています。
N要素のうち、初めの1回はKの範囲をとって、残りのn-k要素はk-1の範囲ずつ取っていく計算です。
以上より、$A_i$ の順番に関係なく、NとKだけで答えを出すことができました。
以上です。ありがとうございました。