Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】AtCoder プログラミングコンテスト2024（AtCoder Beginner Contest 382） - 参加記 | 茶コーダーが解くAtCoder

AtCoder コンテストまとめ ABC プログラミング

コンテスト時間: 2024-11-30(土) 21:00 ~ 2024-11-30(土) 22:40 (100分)

Difficulty: 10

解答時間: 1:50

横一列に並んだ $N$ 個の箱のいくつかの箱にクッキーが入っており、その状態は文字列 $S$ によって与えられる ( $S_i =$ @ならば、左から $i$ 番目の箱にクッキーが1枚入っている) 。これから $D$ 日間、箱のいずれかに入ったクッキーを1枚選んで食べることを1日1回行う。 $D$ 日間経過後、空き箱であるものの個数を求めよ。
$S$ 内の@の数を $c$ とすれば、 $N - c + D$ が答え。

Difficulty: 24

解答時間: 2:37

A問題とほぼ同じ条件で、今度はこれから $D$ 日間、その時点でクッキーが入っている箱のうち最も右にある箱のクッキーを選んで食べる。 $D$ 日間経過後、各箱にクッキーが入っているかどうか答えよ。
実際にシミュレーションしていくだけ。 $S$ をいったんreverseしてやると、実装が楽になるかもしれない。

C - Kaiten Sushi

Difficulty: 476

とある回転寿司に $N$ 人が訪れ、人 $i$ の美食度は $A_i$ である。今からベルトコンベア上を $M$ 個の寿司が流れ、 $j$ 番目に流れる寿司の美味しさは $B_j$ である。それぞれの寿司は人 $1,2,\cdots,N$ の前をこの順に流れていき、それぞれの人は美味しさが自分の美食度以上である寿司が自分の前に流れてきたときはその寿司を取って食べ、それ以外のときは何もしない。 $M$ 個の寿司それぞれについて、その寿司を誰が食べるか、あるいは誰も食べないかどうかを求めよ。
一瞬、 $A$ をソートして二分探索か、とも考えたが、今回は $A, B$ の順序は崩せないことに気づき、うまい解法が思いつかなかった。
累積 min をとってやることが重要らしい。

D - Keep Distance

Difficulty: 685

整数が与えられる。以下の条件をすべて満たす長さの整数列を辞書順にすべて出力せよ。
- $1 \leq A_i$
- $i = 2, 3, \cdots, N$ に対して $A_{i - 1} + 10 \leq A_i$
- $A_N \leq M$
$N$ が小さいので、再帰全探索が使えそう。
...と思いつつ書いていたらなぜか TLE 。どうやら次の値を決める際の探査範囲を $A_i + 10$ から $M$ までにしてしまっていたからのようだ。たしかに $i+1$ 番目の項の範囲は $A_i + 10 \leq A_{i+1} \leq M - 10(N-i)$ で十分だった。これは気づきたかった。

結果

Performance: 533

Rating: 710 → 693 (-17)