精進メモ 2021/05/03~
最近は少しだけ忙しくて典型を埋めるので精いっぱいです(モンハンをしながら)
典型90 029 - Long Bricks（★5）
遅延セグ木で殴ります。
が与えられた際に、その区間の最大値を取得し、値 + 1を計算すれば答えです。
区間に対して、計算した値で再び更新することも忘れないようにすればOKです。
典型90 030 - K Factors（★5）
迷走して結構悩みました。
エラトステネスの篩と同じ感覚で、素因数の種類をカウントすれば間に合います。
典型90 031 - VS AtCoder（★6）
5乗オーダーが通ることを信じて投げると通ります。
4乗ってツイートを見かけた気がするのですがわからず…
については何も気にしなくてよくて、1つあたりのゲームのグランディ数がわかればxorをとっておしまいです。
は最大50、
が最大1325になります。ありうる
の組み合わせについて、グランディ数を求めれば良いです。
素直に遷移先のグランディ数を求め、そこに含まれない最小の整数を計算します。
状態が3乗分で、遷移はを減らすパターンが2乗分かかります。
ABC200
いまいちでした。Dでペナ出したのでEで落ち着こうと思ったのですが、Eももたつきました。
Fも間に合わず、コンテストが終わってかなり時間が経ってからの
のACになったので悔しいです。
D - Happy Birthday! 2
DPでごり押しです。
番目の値まで見て、総和
が
になるような組み合わせがある場合、最後に使用するID
として更新していくと、遷移先に既にIDが書かれていた場合、経路が二つあるので、答えが決まります。
復元を頑張ると通ります。コーナーっぽいケースに阻まれペナを出しました。
E - Patisserie ABC 2
に直して解き、最後に1足しました。
まずは総和を決め打ちます。
総和が0のパターンから順番にどれくらいあるか数えていきます。
Python/Ruby/PHP/Golang(Go)で上限のある重複組み合わせ - Qiita
こんな感じで包除すれば良いです。上記の記事は、最低1使う、としているので要注意です。コンビネーション部分は愚直ループで計算すれば良いです。ここがです。
総和が決まると、次は1つめの要素を決めます。
こちらも、を小さい方から見ていけば良いです。パターン数は上記と同様です。ここも
です。
1つ目の要素が決まると、あとは2番目の要素を決めたら3番目の要素が自動的に決まるので、2番目の要素を小さい方から順番に試していけば良いです。これもです。
ということで、一つ一つ決めていけば答えを出すことができます。
F - Minflip Summation
左端が1の場合、 10となっているような箇所を数えれば答えになります。左端が0の場合はその逆です。
と言うことで、左端を01の二通り試します。
10となっている箇所のカウントは、通り試して、
倍すればだいたいOKです。 先頭を最初に決め打っているので、その周辺だけ丁寧に場合分けをする必要があります。
それ以外は、2の、01以外の部分の?の個数乗を計算すればOKです。
のパターンもコーナーケースになりやすいので気を付けましょう。
ARC118
A問題で詰まりました。
A - Tax Included Price
↓の問題と同じ感じで、ある値までに、1つ飛ばしになった数字の個数が割り算で求められます。
なので、それを二分探索すれば、答えを知ることができます。
F - Modularness
B - Village of M People
maxminは二分探索、
は
にバラして最大値を求めても問題ない、
定数倍してもmaxの結果は変わらない、
の区間でそれぞれ選んで
にできるかどうかは
で判定、
と、典型を組み合わせていけば自然と解法が出てきました。
組み合わせの分、実装は少し大変だったかもしれませんが、丁寧にノートに書いていたのでなんとかなりました。
C - Coprime Set
↓の問題を解いていたので、この問題の解法はすぐに思いつきました。6,10,15の倍数で10000以下のものをひたすら詰めていけば良いです。
