atcoder.jpまずは美味しい順にソートして上からK個取る。そこから、残りのN-K個のうちでどれかと交換することで満足度が上がるかどうかを見ていくわけだが、この時、すでに取っているネタの種類がi種類であれば、そこから種類を減らすことによって満足度は決…

・セグメント木 書きようによっては任意の区間のGCDを求めたりもできるっぽいけど、とりあえずは任意の区間の最小値を求めることにする。 n = int(input()) #配列の要素数をnと置く。 L = list(map(int,input().split())) #配列 t = 1 while t <= n: t *= 2 …

atcoder.jp逆元使ってn_C_k（を10**9+7で割った余り）を高速で求める、それはそうみたいな問題なんだけど、流石にテンプレをペタって貼り付けてn=10**5,kを1~10**5まで計算するのはしんどい（factorialの都合上）n_C_k-1からn_C_nまでを一気に求める問題であ…

atcoder.jp桁DP的な発想 解説読んでパッと理解できなかったatcoder.jpこれも桁DP的発想atcoder.jp提出した後で「2,8とかの組み合わせの時無理じゃね？」とか気付く。ちゃんと考察をしましょう。atcoder.jpグラフの用語を知った。 ・直径：一番遠い点間の距離…

atcoder.jp総和が不変であり、その約数がgcdの候補であることは気づけた。そしてその後に分配するフェーズで余りを横に並べて右側はプラスされる側、左側はマイナスされる側と分けてそれぞれをチェックするところまでは発想できた。 （例） 約数＝5で割った…

atcoder.jp数字が「ある」ところを探すんじゃなくて、「ない」ところを探すという発想の転換。難しい。atcoder.jp発想の問題じゃなくて、大きな数字を扱うときは注意しましょうねという話。基本的にpythonは大きな数字はメモリの許す限り扱えるけど、例えば …

atcoder.jps = 10**100とかいう良く分からん表現に振り回された感がすごいやることとしては、いっぱいつなげる方(s)に対し、sのi番目(iは0~len(s)-1、つまりsの各文字)の文字に対して、そこから数えてa,b,c....が次に最短でいつ出てくるかを数える（これをや…

クッソサボってた しょうがないねatcoder.jp s = 'AAA' s = 'B' + s #s = 'BAAA' 上の例みたいに、文字列の先頭に新たな文字をくっつけるのは、末尾にくっつけるよりもかなり時間がかかるので注意すべしatcoder.jpサイズ付きUF木で一撃 こういうのが普通にで…