期待値でも遷移さえわかれば 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…

解けなかった。 発想１．(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 の移動をメモ…

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

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 : ] ) になります。 そして、その…

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

解法１ dp[ i ][ j ][ k ] : i 行 j 列まで見たときに差が k になれるかどうか、なれるなら１、なれないのなら０を記録する。遷移は c = abs(a[ i ][ j ] - b[ i ][ j ]) として (dp[i+1][ j ][k+c] = 1, dp[i+1][ j ][abs(k-c)] = 1 if dp[ i ][ j ][ k ] =…

NOMURA プログラミングコンテスト 2020 A,B,C の3完 ABC170 A,B,C,D の4完でした。 土曜日の方はまずまず。C は直ぐセグ木じゃん楽勝と思った割に、実装をバグらせまくり時間をロスしすぎました。いもす法は知らなかったので、セグ木で毎回リスト A をみて 1…

タイトルからして dp だと思ったら解説は全探索だった。本質的には dp もメモ化全探索みたいなところあるけど。 w_i の制約が特徴的で max(w_i) - w_1 dp[ i ][ j ][ k ] で i 番目の荷物まで見たときに、j 個の荷物を入れて、 重さが j * w_1 + k となって…

まんまこれ。 区間に含まれる区間の数をカウントするクエリにたくさん答えたい - 問題解決の宝石箱 終点でソートすることにより、それまでに出てきた区間の終点が、今見ている区間の終点よりも小さいことが保証され、始点の位置だけセグ木で保管すれば、クエ…

Eまで5完。Fが形式的冪級数だと気づきさえすれば６完できたのに。 Bは０が後ろにあるケースがサンプルにあったからすぐ修正できた。sort したら前から10**18 を超えたら -1 を出力するようにプログラミングしてよい。python は10**18の計算をしてもエラー吐…

0完。カス。これが最後のレートつくAGCだったと思うとまあ残り５分で迷いながらもBを提出したのは良かったかも知れない。レート変動ないものを頑張る意味はないのでAGCは今後出ないでしょう。 今日学んだこと。 math.ceil は 15 桁以上の数字は勝手に丸める…

1,...,n のうちの頂点 i から bfs をはじめて最短何回で全頂点辿れるかを計測しつつ、i から１回で通れる頂点, 最短２回で通れる頂点,,, をリストに入れておく。 答えが -1 にならない条件は i から同じ回数で辿りつける任意の２頂点が辺を持たないことであ…

文字列操作の問題２問。両方いけた。同じコンテストで連続して似たような題材を出すのはABCにはない感じがする。 どちらも操作回数の最小値を求めるものであるが、数え方が違った。Bは操作を行う必要がないものについて考えると上手くいく。 少なくとも文字…

自力AC。解説は dp しとるな。これが bitDP ってやつか？ 制約が N=12 だったので bit 演算関係あるんかなと考えると、とりあえず入力される鍵を 例えば N=6 で 2 3 5 を開ける鍵だとすると、key1 = 2**(2-1)+2**(3-1)+2**(5-1) とかはできるなあと思った。 …

自力AC。解説とは若干違った。むしろ解説がよく分からん。 ぱっと見で01ナップザック問題じゃんとなり、dpするだけなのかと普通の (N*T) の二次元dp を実装したらサンプル３が合わず考えると、T-1 秒までなら T 秒を超えても注文ができるのが原因だと分かる…

i 文字目を A にした時の文字列の作り方の総数を f(i,0) = dp[i-1][0] として f(n) = sum(dp[n-1]) を求める。 例えば７文字の作り方の総数 f(7) を考えるときは新たに条件を満たさなくなるのは、 ○○○○AGC、○○○○GAC、○○○○ACG、○○○A○GC、○○○AG○C、 となるもの…

a[p]+b[q]+c[r] の最大値を k 個求める問題。 取り合えず逆順でソートすれば、最大値は a[0]+b[0]+c[0] になるのは確定で、その次に最大になるのが、a[1]+b[0]+c[0], a[0]+b[1]+c[0], a[0]+b[0]+c[1] のどれかだと分かれば後は heap で k 回ぶん回すだけ。気…

a として実装した。 import sys input = sys.stdin.readline n,m = map(int,input().split()) chk = [] for i in range(n): a,b = map(int,input().split()) if a <= m: chk.append((a,b)) from heapq import heappop, heappush from operator import itemge…

数列を前から見ていって、二分探索でその数字が今の数字の色の種類のどれに上書きできるかをを探して、上書きできる奴で、一番数が大きいものにその数字を上書きする。 貪欲法の練習問題で箱を入れていくやつと同じ考え方。 D - プレゼント0 なら色の種類を …

文字列をアルファベットのリストに入れていって二分探索したらいいやつ。 s = contest, t = cc みたいなときに 一つ目の c と二つ目の c が同じ答えにならないように 見ている t の位置が更新するたびに ans += 1 してデバッグするのに 15 分ほどで気づけた…

b より大きく、a 以下の数字の積の約数の数の個数を求めればいいのだけれど、b,a が大きすぎてそのまま掛け算をするとオーバーフローする。 なので一つずつ素因数分解して、個数分だけ素数をリストに入れていって、あとで collections.Counter で数えた。 a,…

158 E を解いたことがあるのに関わらず、d が解けずに敗戦。a の羊を半分と誤読し続けたせいでパフォも最悪でした。失敗を二つもしたらそうなる。 考え方は int( s[ i: j+1 ] ) が2019の倍数 ⇔ int( s[ i : ] ) - int( s[ j : ] ) %2019= 0 (2019と10が互い…

ワーシャルフロイド法で解く問題 街の通り方は順列で全探索した 計算量は最大(200**3 + 8!) くらいで pypy3 で 330ms def warshall_floyd(d): #d[i][j]: iからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j…

Union-find の練習 何回でもスワップできるので、結局 i と p[i]-1 が同じ木にいるかどうかで求まる。 import sys input = sys.stdin.readline n,m = [int(i) for i in input().split()] p = [int(i) for i in input().split()] p = tuple(p) chk = [[set(),…

Union-find木 の練習 Union-find のライブラリーはじゅっぴーさんのをそのまま使わせていただいております。 蟻本 python Union-Find木 競技プログラミング - じゅっぴーダイアリーUnion-find はつなげることしかできないので、入力を逆向き (append でなく …