5分ツイートシェアはてブLINEPocket3度目のコンテストです。前回の天下一プログラマコンテストでもD問題が解けなかったので、今回こそは......!という意気込みで臨みました。相変わらず仕事から帰ったあと、日をまたいでから明け方までの時間を毎日費やしてきて、おかげで過去問はABCのA問題が全て、B問題が半分終わりました。枚ずつビスケットを生産します。ビスケット生産装置を起動してから秒後までに生産されるビスケットの合計枚数を求めてください。回生産されると考えることができて、これにを掛ければOKです。0.5秒ってのは「TがAの倍数だったらそのタイミングで生産されるのか?」的な話を明確化するために付けたものだと考えられるので、この考え方であれば無視でもOKですね。番目の宝石の価値はです。あなたはこれらの宝石の中からいくつかを選んで手に入れます。このとき、つも選ばなくとも、全て選んでも構いません。番目の宝石を手に入れる場合コストを支払わなければいけません。手に入れた宝石の価値の合計を、支払ったコストの合計をとします。最大値を求めてください。https://atcoder.jp/contests/abc125/tasks/abc125_b要するに、一番得をするように宝石を買えば良いわけですね。利益が正になるものを購入すれば自然と最大になります。Blackboard個の整数が黒板に書かれています。以下の好きな整数に書き換えます。元の整数と同じ整数に書き換えても構いません。書き換えた後の個の整数の最大公約数の最大値を求めてください。最大をもとめる」でOKなわけです。求めるプロセスは以前まとめましたね。求めたいとき【AtCoder】しかし、普通にやるとオーダーが多分になって計算が爆発して死ぬと。死んだコードがこちら。死んだので高速化の方針はつあって。自分は後者が分からないので前者でなんとかできないか試行錯誤しましたが、まぁできずに終了。なんで合ってるのかはわからないけどなんで間違ってるのか反例が思いつかないです。いう方法を使うといけるっぽい。求めるプロセスの方でした。何なのかはわかりませんが、東大の先輩に教えてもらった感じこういう方針で計算量を削減できます。累積的に求めれば良いのか!天才の発想ですねこれをふまえてコード書いたらこうなりました。Signs個の整数が並んでおり、順にです。あなたはこの整数列に対して次の操作を好きなだけ行うことができます。操作:を満たす整数を選ぶ。操作終了後の整数列をとします。最大値を求めてください。つの数は自由に選べる事がわかります。わけで絶対値をとってあげて、絶対値が一番小さいのを負の数にしてあげればOK。まともに過去問解いてないのでなんとも言えないのですが、かなりカンタンめな印象を受けました。2)サトゥーやっと色が付きました。早く水色になりたいです。次こそ全完を目指したいです。コメントをキャンセルメールアドレスが公開されることはありません。date*日本語が含まれない投稿は無視されますのでご注意ください。