精進メモ 2021/08/23~ - ツバサの備忘録

構造化束縛が便利なので、これを使ってちょっとした3つ以上の構造体は全部Tupleに任せてしまうのもいいかもしれないです(可読性と要相談)。
久々に1日10問とか解いた気がします。やっぱりやると楽しい。

AOJ-ICPC
ABC216

AOJ-ICPC

10万点いきました。ちょうど300問。
f:id:emtubasa:20210828212201p:plain

1389 - Digits Are Not Just Characters

比較関数を頑張って実装します。

1306 - Balloon Collecting

$dp[x] =$ 今バルーンを受け取った時刻に個数が $x$ になるような動き方の中で、距離が最小になるもの、として計算していけばOKです。

1315 Gift from the Goddess of Programming

時刻をパースして、"000"と一緒にいる時間が一番長い人を求める問題です。
"000"が入るタイミングで、今いる人は今の時刻分値をマイナス、"000"かほかの人が抜けるタイミングでその時刻分値をプラスしていけばいいです。

1248 The Balance

ダイクストラをしました。
個数と重さの合計で大小を定義し、現在はかれる重さに+a, -a, +b, -b, +(a-b),+(b-a)の6通りを計算するパターンを遷移としました。

2166 Erratic Sleep Habits

$dp[i][j] = i$ 日目にサイクルが $j$ 番目になるようなパターンの中で、カフェイン摂取回数の最小値
として計算していきます。

1326 Stylish

$R,C,S$ を全探索すればOKです。
括弧の個数は累積和を取ればいいです。
構文解析に見えて構文解析はいりませんでした。

2730 Line Gimmick

最初は面白いと思いましたが細かい計算で頭を使いました。
ある>をスタートにするとき、その>から左にある>の個数と、それより右にある<の個数の大小で、最終的に右と左どちらに行くかがわかります。
最終的に取り除いたパネルは、どちらかの端を含む区間になるので、端でない側がどこまで到達できるかを求められれば答えがわかります。

1380 Medical Checkup

$i$ 番目の人のインターバルは、 $\max(h_{j})$ になります。
開始時刻は $\displaystyle\sum_{j = 1}^{i-1} h_{j}$ になります。
あとはこれを計算すればいいです。

1390 Arithmetic Progressions

$(i,j)$ のペアを高々一度だけ見るようにすればよいです。
先頭の2つを決めたら、その後に続く列は自動的に決まります。先頭ができるだけ小さい方から見ていき、既にチェックしたペアは先頭に持ってこないようにすればOKです。

1391 Emergency Evacuation

最初に距離を計算し、あとは入れられるところに詰めていけばいいです。適当に空いている要素を全部setに挿入し、使うたびにsetから削除していけば、二分探索で次の人の時間を決められます。

2906 Santa's Gift

サイズを人数で割ると、全ての $1 \leq k \eq M$ の総和は $O(M \log M)$ です。
よって、あとは $1/k$ した状態でナップサックを解いていけばいいです。

2912 Sum of QQ

$(\sum_{i = a}^{b}i) \times (\sum_{j = c}^{d}j)$ が $S$ になるような $(a,b,c,d)$ を探せばよいです。
$(a,b)$ と $(c,d)$ は独立に探せます。
$a,b$ の組み合わせは $1$ から $10^{5}$ まで愚直に探しても間に合うので愚直にメモしていけばOKです。
よって、 $pq = S$ となるような $(p,q)$ について、先ほどのメモしたカウントの積を足していけばおしまいです。

2847 Ninja Map

頑張って左上から順に復元していきます。
隣接する辺を決まったところから削除していくと、あとは残っている辺を選ぶだけになります。

1280 Slim Span

辺を重みでソートして、ある辺を最小値としたときに、必要な辺の重みの最大値の最小値を二分探索で求めます。判定部分は、Unionfindを用いればできます。

2320 Infinity Maze

右手法をダブリングします。
$L$ が小さいと思って最初は愚直にシミュレートしていました…

ABC216

得意セットでした。

C - Many Balls

+1と×2で構築する問題です。いつものビットを見ながら後ろから決めていく形でOKです。

D - Pair of Balls

1問目に開いたのですが、すごくてびっくりしました。
愚直に取り出せるところを取り出していけばOKです。
取り出せる色をqueueに入れ、シミュレートしていきます。
どの筒にそれぞれの色が入っているかをメモしておけば、筒から取り出して先頭の色がどうなっているかも簡単にわかります。

E - Amusement Park

大きい方から愚直に選んでいけばいいです。今一番大きい値が複数同時にあるとき、まとめて計算するようにすれば、 $N$ 回の計算で終わります。0を配列に入れておくのがポイントです。計算がしやすくなります。

F - Max Sum Counting

Eより先にニコニコしながら解きました。 $(A,B)$ を $A$ の昇順でソートしておくと、ナップサック問題と同じような形のDPに落とせます。総和が $S$ になるようなパターン数を数え上げ、最後に使った $i$ についての $A_{i}$ が $S$ 以上であれば、今数えた部分を答えに加算します。総和は5000まで見ればOKです。
面白かったです。

G - 01Sequence

区間スケジューリングで構築していけばOKです。
$R$ が小さい方から見ていき、右詰めしていきます。今見ている条件についてあといくつ置くべきかはBITで区間和との差分を見れば良いです。右詰めパートは、まだ使ってないものを適当にsetに入れておけば、set上の二分探索で一番右が求まります。
実装は軽めでした。面白かったです。
~~Online Judge toolを使うと、実はサンプルアウトプットの最後に空白があることがわかります~~