【PGBATTLE2021_かつおぶし】

48min。2まで解きました。
3と4を30分ほど粘って挫折。

1.階乗の桁数

log10で和をとればよさそう

Q. 4

log10(2 * 3 * 4)
= log10(2) + log10(3) + log10(4)
= 2.3802112417

整数に切り捨てして、
A. 2

実装

int main(){
 cincout();
 
 ll N;
 cin >> N;
 ld d=1;
 for(ll i=2; i<=N; ++i){
   d += log10(i);
 }
 ll ans = d;
 cout << ans << endl;
}

https://atcoder.jp/contests/typical90/submissions/26747142

2. 桁と数列

1. あたえられた桁について、最小値と最大値を足していく。
2. 解答候補として、最小値をいれておく。
3. Sが、minsum <= S <= maxsum の範囲に含まれるなら、解答がありそう
4. Ｓが余っているので、もう一度index 0 から走査。できるだけmaxsumに近い値におきかえてく。

Q.
3 1000
3 2 1

1. 最小値と最大値の下準備。
mins[1] = 1
mins[2] = 10
mins[3] = 100

maxs[1] = 9
maxs[2] = 99
maxs[3] = 999

2. ans[]の仮入れ。
ans[0] = 100 // 3
ans[1] = 10 // 2
ans[2] = 1 // 1

minsum = 100 + 10 + 1 = 111
maxsum = 999 + 99 + 9 = 1107

3. 解答があるか確認。

  111  <= 1000 <=  1107   なので、うまく振り分ければ解答を得られそう。
minsum     S       maxsum

ans に minsum を入れているので、
s = 1000 - 111 = 889 が消費しないといけないポイント。

4. ans[0] の再代入。
1) いったん解除して
s += ans[0]
ans[0] = 0

2) maxsに近い値をいれてみる。
ans[0] = min(maxs[d], s) // 889
s -= ans[0] // 0

s == 0になったのでおしまい。

A. 889 10 1

実装

ll ans[110];
ll D[110];
ll mins[11];
ll maxs[11];

int main(){
 cincout();
 
 ll N, S;
 cin >> N >> S;
 mins[1] = 1;
 maxs[1] = 9;
 for(ll i=1; i<9; ++i){
   mins[i+1] = mins[i]*10;
   maxs[i+1] = maxs[i]*10 + 9;
 }
 
 ll low = 0;
 ll high = 0;
 ll s=S;
 rep(i, N){
   ll d;
   cin >> d;
   D[i] = d;
   s -= mins[d];
   low += mins[d];
   high += maxs[d];
   ans[i] = mins[d];
 }
 // min~maxにはいっていればok
 if (S<low || S>high){
   cout << -1 << endl;
   return 0;
 }
 rep(i, N){
   ll d=D[i];
   s += ans[i];
   ans[i] = 0;
   ans[i] = min(maxs[d], s);
   s -= ans[i];
   if (s==0) break;
 }
 rep(i, N-1) cout << ans[i] << " ";
 cout << ans[N-1] << endl;
}

https://atcoder.jp/contests/typical90/submissions/26747115