尺取り法のめも import sys input = sys.stdin.readline n = int(input()) a = list(map(int,input().split())) s = sum(a)/10 a += a now = [0,0] f = False for i in a: if now[0] < s: now[0] += i elif now[0] == s: f = True break else: v = now[1] fo…

bit全探索、横の列を固定して、縦ごとに見る、defaultdict の操作、などのメモ import sys input = sys.stdin.readline from collections import deque, defaultdict h,w = map(int,input().split()) s = [list(map(int,input().split())) for i in range(h)…

""" query_0 が Σ A[i] (l≤i≤r-1) を出力 query_1 が l≤i≤r-1 について A[i] を A[i]*b + c に更新する X[l,r): Σ A[l,r) lazy[i] (更新を保存しておく配列) の２つの配列をもち、 ・op_data: X＊X →X (X[l≤i

数列から等差数列を引いていって [0]*n にできるかを答える問題 n = 5 の場合、引く候補は [1,2,3,4,5], [2,3,4,5,1], [3,4,5,1,2], [4,5,1,2,3], [5,1,2,3,4] の 5 つあるが、 どれも総和は 15 であり、引ける回数 k は sum(a) // 15 になる 引いた後の遷移…

気づくこと 一回でも x を操作する途中で２倍した後は、二回連続で +1, -1 を使わない。 理由 p 回 +1 した後に、２倍して q 回 +1 すると、 (x + p)*2 + q = 2x + 2*p + q q ≧ 2 のとき 2x + 2*p + q = 2x + 2*p + 2*s + t(s ≧１, t は 0 or 1) となり p + …

期待値でも遷移さえわかれば dp で求まるというやつ。 dp と メモ化再帰の両方で解いてみた。 a,b,c = map(int,input().split()) dp = [[[0]*101 for _ in range(101)] for i in range(101)] for i in range(100,a-1,-1): for j in range(100,b-1,-1): for k…

久しぶりに bfs やら ord を書いたのでメモ。 import sys input = sys.stdin.readline h,w = map(int,input().split()) s = [list(input().rstrip()) for i in range(h)] to = [[] for i in range(26)] for i in range(h): for j in range(w): if 96 < ord(s…

知らないと解けないなと思ったのでメモ。参考 CODE FESTIVAL 2014 あさプロMiddle : B - 枕決め - kmjp's blogN人の人とM個の枕がある。 N人はそれぞれ高さがX[i]以上Y[i]以下の枕が好みであり、そのような枕を１個使いたい。 M個の枕の高さA[0] ~ A[m]が与…

"「ある頂点の子孫でない頂点に xを足す」は、 「根の子孫に xを足す」と「ある頂点の子孫に -xを足す」に分けることができるので、 全てのクエリを「ある頂点の子孫に x を足す」の形に帰着することができます。"かしこい。は？となりながら解説の言うとお…

解けなかった。 発想１．(Xi + Xj + Xk) + (Yi + Yj + Yk) + (Zi + Zj + Zk) を (Xi + Yi + Zi) + (Xj + Yj + Zj) + (Xk + Yk + Zk) とみて考える。 これは添え字が同じになるように移項するのと同じ発想なので思いつくべきだった。 発想２．- (Xi + Xj + Xk…

ずっとほったらかしていた問題。 dfs で全探索するのだけど、愚直に計算すると間に合わない。 • 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。 • 中途半端に解く配点があるなら、それは完全に解く配点以外の配点…

３次元 dp するときに、r,c,k のうち k だけ、計算量が小さいときは、 dp = [[[0]*c for _ in range(r)] for _ in range(k)] と書いた方が実行時間が短くなるという知見を得た。というかこう書かないと TLE するのだがなぜ？ def main(): import sys r,c,k =…

atcoder 再開。水色になった。 01-bfs というやつらしい。+0 を append で、+1 に遷移するものを appendleft でdeque に入れてあげると、O(1) で heap みたいなことができる。heap で回したら TLE した。 よくある bfs や今回初めて書いた 5*5 の移動をメモ…

ほぼこれ。abc 137 E - Coins Respawn (python) - aacord’s memo 頂点１からNまでに通りうる経路だけ抜き出して、その中で bellman-ford を使う。更新回数が m 回をこえたら inf を出力する。 from collections import deque def belman(s,n,w,es): d = [-fl…

連続する部分列→累積和を取る 累積和をとって、差を考える 余りの種類は m 個あるけど、数列の長さから高々 n 個に座圧できる。 基本テクの詰め合わせ。 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.std…

サンプルを使ってワーシャルフロイドした結果が、サンプルと一致していなければ答えは -1 となる。 そうでない場合は存在する道の和を出力しないといけないが、それは i から j に道が引かれているとき == min( d[ i ][ k ] + d[ k ][ j ] ) > d[ i ][ j ] …

場合分けが無限にある。 条件がきつい順に 全部０の場合→０ ５が含まれていない場合→ No 全部５以下の場合→１ min(h, w) > 1 なら 最大値 9 → 4 最大値 8 → 3 最大値 6,7 → 2 となり、 そして上記以外で、h or w = 1 のときは、５の左右の列で最大値ごとに計…

久しぶりに拡張ダイクストラの問題 day2 にも拡張ダイクストラが出ていたりする。 ダイクストラといっても、距離は一切出てこなくて、休憩回数の最小値を求める問題。 heap で (累計の休憩回数、前の隙間、今いる頂点）を保管して、今いる頂点から次の頂点に…

結局、フェルマーの小定理から x = i のとき 1 で、それ以外の時に 0 となるような p-1 次式が作れてしまうというだけの問題。賢い。 あとは a[ i ] = 1 のときに毎回 1 - (x-i)^(p-1) の係数を二項定理で作るだけ。 p = int(input()) a = list(map(int, inp…

一つでもpath上に黒がある個数を、総数ーpath上がすべて白く塗る個数と置き換えて包除原理を使う。 m 個の path の中から i 個を選ぶ方法は itertools.combinations を使い、1つの path が通る辺の集合を辺１つずつに番号を座圧の要領でつけていき、2進数表…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

c を降順ソートすると、c [ i ] を新しく頂点に書き込むとき、スコアが c [ i ] になる回数は高々 i 回で、それまでに一つの辺でスコアを c [ i ] 以上獲得している回数は高々 i - 1 回あるので、求める最大値は sum( c [ 1 : ] ) になります。 そして、その…

結局注目する点は、隣り合う2数を足したときに、繰り上がって桁数が変化しない時は、全体の数の和が9減るということのみ。桁数が減る時は繰り上がりがないため、全体の和は変化しない。 なので求める回数は、全体の和を S, 桁数を T とすると、T-1 + (S-1)//…

stack, dict, set 全部使った。盛りだくさん。 まず、降順ソートしてｋ個選んだ時に、L 種類の寿司が含まれているとき、当然それはL 種類の寿司を選ぶ美味しさの中での最大値となる。同様にして、k > L なら種類が被っている寿司を食べているので、k =L にな…

始点ソートして、L ≦ i ≦ R でd[ i ] = min( d[ i ], d[ L ] + c ) で更新していけば終わり。 答えは d[ n-1 ] で、d[ n-1 ] = INF なら -1 を出力する d[ i ] の一点取得、L ≦ i ≦ R の区間更新なのでセグ木を使えば簡単。 import sys read = sys.stdin.buf…

まず、根になる頂点は、Bには含まれておらず、そのような点 a がただ一つ存在することが分かる。 そして、次に Ai = a となっている辺を全て取り除くと、Bに含まれない点 b が新たに1個以上現れる。その点は、a しか親になりえないので b の親は a とわかる…

dp の巻き戻しするやつ。dfs をして頂点を探索する際に、stack (deque) に次の頂点を入れる前に、dp を変更する前の要素を入れておくことで、dfs順に頂点を探索するときに、行き止まりについてから、一つ前の頂点に戻る時にその時点での dp を再現することが…

約数系の包除原理の問題として解いたけど、どう帰着するのかわからなかった。 まず lcm ではなくて最大公約数 gcd で考える。 lcm( i,k ) = i*k//gcd( i,k ) で求まる。 すると、1 ≦ i ≦ n, k なので、k の約数の集合を g とすると、g = gcd( i,k ) になる i…

172 4完 パフォ1421 173 4完 パフォ1319 まあ失敗ではないけど大成功でもない感じ。次で水色なりたいね。 172は包除原理の一般法則を知らなかったのが原因。Fは難しかった。 #172 E import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.re…

頂点１を根として、dfs をしていき、それまでの xor 和を defaultdict (D) で管理して、現在のxor和 = X^a を満たす a が今までの xor和に含まれていればいいので、dfs 順に D [ 現在のxor和^X ] を足していけばいい。根からの xor和がちょうど X になるとき…