bit dp の問題。dp[ i ][ k ] = (a,b) として、今まで通った頂点を表す bit i と今いる頂点 k が入りその時の最小値 a と最小値をとりうる通り方の総数 b が保管されている。 k から次の頂点 j に行けるのは i の j の位が０であるときで、 かつ、dp[ i ][ k…

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

k = 0 から順番に (A[k*2],B[k*2]), (A[k*2+1],B[k*2+1]) を (A[k*2]+B[k*2])*A[k*2+1]+B[k*2+1] と計算していく問題。 セグ木を使うと、(A[k*2]*A[k*2+1], B[k*2]*A[k*2+1]+B[k*2+1]) の結果を (A[k], B[k])に保存できるので、求める答えは sum(A[1]+B[1]) …

セグ木の練習。木というているけど、使いどころはグラフ問題ではなく、ソートされた数列で、特定の区間の最小値や公約数を求めたり、特定の区間の値を変更するときに使う。 愚直にやると N^2かかるが、heap を使おうとすると頭が痛くなるときに便利。 今回の…

M回握手をして出来る幸福度の最大値を、１回の握手で幸福度がｘ以上上がるような握手の回数がM回出来るｘの最大値を求める問題と考えれば、二分探索でｘを求めて、左手 i を固定したときにｘ以上の握手ができる手の数は、 a を昇順ソートしておけば k = n - …

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は操作を行う必要がないものについて考えると上手くいく。 少なくとも文字…

AGC に備えてAGCの緑 diff を８問くらい解いた。 印象としては気づくかどうか系が半分くらいで正答率も半分くらいだった。 数え上げ問題が多く、やたら Counter 使っている気がする。 一番大事なのは問題の題意をちゃんとと把握することだと感じた。 これは…

経過時間*P 枚コインを失い、辺を通るのに１分かかり、辺上でC枚のコインを得るので、 辺を通ったときにかかるコスト（-コインの数）を －C＋P 枚とすれば、最短路問題に帰着できる。今回は負の辺があるのでベルマンフォード法を使う。 面倒なのは、頂点１か…

4完。Eは難しかった。Dが bfs するだけなのは分かったが一から実装するのに手間取った。dfs だけライブラリとして持っていたのに... bfs も作りました。 # 木(辺のリスト作成) n, m = map(int, input().split()) g = [[] * n for i in range(n)] for i in ra…

自力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 秒を超えても注文ができるのが原因だと分かる…

自力AC。差の絶対値の総和を求める。 こういうときは | n - m | = max(n,m) - min(n,m) なので、a より小さいものの数、大きいものの数を x 座標と y 座標で別々に求めたらよい。これの一次元版を解いたことある気がする。 1 そして X座標が x となる頂点の…

XOR の知識 1．a^a = 0, a^b^a = a^a^b = b（交換法則） 2．n%4 = 1 のとき 1^2^...^n = 1, n%4 = 3 のとき 1^2^...^n = 0 (ABC121 D)2. から 1^2^...^2**m-1 = 0 となり、1. から k 1^2^,...,^k-1^k+1^,...,^2**m-1 = k となる。 考察はできたが実装が手こ…

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 回ぶん回すだけ。気…

100分フルに消費して4完。レート微増。参加者のレベルも上がっている気がする？自分の成長速度があまり感じられない。二連続ぐらいで水パフォ取れると安定しそうだけどなぁ ｃは2回続けて全探索に殺されてたので流石にできた。c は numpy で行ごとに足せれる…

diff が一つ上がるごとに発想が一つ増える感じがする。 緑なら一つ、青diff なら二つといったイメージ 今回の問題は橙diff で実験から３つのことが分かるかどうかみたいな問題だった。1. ボール i が衝突を考慮しないで t 秒たったときの位置には 1 ~ n まで…

XOR っぽいけど本質はそこじゃない感じの問題。 本質は s = 0011100... と並んでいたら、s[0 : ], s[2 : ], s[5 : ] で操作する回数が異なっている必要があるということ。 なので s[2], s[5] で区切る必要があり、これを満たす最大の長さは min( max(2,len(s…

女子の選びだけ itertool で nCp 通り全列挙して男子の選び方を貪欲に選んでいく。 collection.Counter で most_common(q) とかして選んでいたら TLE したので普通にリストに入れていって上から q 番目まで取ったらいけた。 import sys input = sys.stdin.re…

R XOR操作が出てくるので i を２進数表示したときの n 桁目を (i>>n)&1 であらわす。 全探索は行ごとでするのに、総和は列ごとに数えるのが面倒くさい。 numpy を使って転置するか、A.sum(axis=0) で列ごとに和を取っていくとよい。 np.count_nonzero(A,axis…

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 分ほどで気づけた…

abc で冷えた後なのでこういう問題は冷静に瞬殺できる。 明らかに全探索するわけがなく、数学的要素が強そうなので素晴らしい。 x,y に至るまで (+1,+2) を i 回、(+2,+1) を j 回したとすると、 x = i + 2*j, y = 2*i + j となって 答えが０でないためには …

３完。負け。いつも愚直に全探索するだけの問題を難しく考えすぎてそこで詰まる。 全探索するかとは一回は思うのだけど、今いち全探索しても間に合う制約なのかどうかが全く分からず結局他の方法を考える→時間切れみたいになっている。 Dも最初から因数分解…

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

C - Align数列を並び替えて隣り合う２数の差の最大値を求める問題。 直観的に一番小さいものと一番大きいものが隣り合うように、出来るだけ真ん中に置くように並べるのがいいと予想できるが、単にそれを実装するのではなく、 隣り合う２数の差 = 大きいもの…