プログラミング ABC230_E – Fraction Floor Sum
ABC230_E - Fraction Floor Sum 問題 提出 3回目くらいで解けた 以下、解法を書いていく。 $\lfloor \frac{N}{i} \rfloor$を$1$から$N$まで愚直に計算すると$O(N)$になってしま...
KOKI
プログラミング プログラミング ABC219_D – Strange Lunchbox
ABC219_D - Strange Lunchbox 問題 提出 3回目くらいで解けた。 2回くらいACできず、解説をみた。 今回、ACできた。 3次元のdpで解いた。 dp配列は以下のように定義する。 $$dp: i番目の弁当まで見た時...
プログラミング ABC204_D – Cooking
ABC204_D - Cooking 問題 提出 3度目で解けた 2度ほど解けず、解説を確認後3度目の挑戦。 2つのオーブンを使って、料理を作る時、N品の料理を全て作るためにかかる時間の最短を求める問題。 各料理にかかる時間は$T_i$分。...
プログラミング ABC218_C – Shapes
ABC218_C - Shapes 問題 提出 1回目 WA : 感想 1回目 解けなかった。 問題をうまく認識できていなかった。 「回転と並行移動の繰り返しでS,Tが一致できるかどうか」という問題だと思って解いてしまった。 この認識だと、...
プログラミング ABC194_D – Journey
ABC194_D - Journey 問題 提出 3度目けた 2度ほど解けず、解説を確認後3度目の挑戦。 成功確率pの事象が成功するまでの期待値$e$は、期待値の定義から、確率回数となるので、以下のような式になる。 $$ e = p1 + ...
プログラミング ABC177_E – Coprime
ABC177_E - Coprime 問題 提出 解けた 以下、解法を書く。 setwiseに関しては、全ての$A_i$に対して順にgcdしていけば良い。 gcdの計算量は、2つの数を$a,b$とおくと、$\log(\min(a,b))$に...
プログラミング ABC156_D – Bouquet
ABC156_D - Bouquet 問題 提出 解けた 以下、解法を書く。 それぞれの花において選ぶ/選ばないの2つがあり得るので、花束の種類としては$2^N-1$になる(全て選ばないの選択は除くため1少なくなる)。 これから、$_NC_...
プログラミング ABC313_C – Approximate Equalization 2
ABC313_C - Approximate Equalization 2 問題 提出 解けた 操作では$sum(A_i)$の値は変わらない。 また、最小値と最大値の差を1以下にするには、最大値を$\lfloor sum(A_i)/N \r...
プログラミング ABC312_C – Invisible Hand
ABC312_C - Invisible Hand 問題 提出 解けた りんごの値段が0の時、売り手の人数は0人、買い手の人数はM人になる。 $x円の時の売り手の人数-買い手の人数をf(x)$とすると$f(0)=-M$である。 $A_i,B...
プログラミング ABC258_D – Trophy
ABC258_D - Trophy 問題 提出 解けた 以下、解法を書く。 1度目のステージクリアには$A_i+B_i$時間がかかり、2度目のステージクリアには$B_i$時間がかかる。 X回ステージクリアするまでにあり得るパターンとしては、...