2020-06-01から1ヶ月間の記事一覧
4完 パフォ1412 でした。最近パフォが1400 くらいで安定している。今はいいけど水色になってからは困るなあ。 コンテスト後に F を通しました。考察はあと一歩だったけど、実装の場合分けは無理でした。まず、Nim の必勝法は A1^A2^...^An = 0 なら 後手が必…
区間dp の問題。区間dp とは、dp[ i ][ i+j ] = list[ i : i+j ] での最大(最小)値として、最大値の遷移を考えるもの。 今回は、dp[ i ][ j ] = ケーキが i+1 番から i+j+1 番まで残っているときの JOI 君の取り分の最大値 として問題を解く。 ケーキが円状…
python だと難易度が爆上がりするやつ。 E - Exclusive OR QueriesCPSCOのsession1のEをPythonで通そうと頑張ってみたけどダメそうということがわかった(はい)(ごめんなさい)— てんぷら (@tempura_cpp) May 12, 2019 本編まで飛ばしていいよ。 やるべき動作…
これの下位互換。 F - Absolute Minima abc 127 F - Absolute Minima (python) - aacord’s memo import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline class Bit: def __init__(self, n): self.size = n self.tree = [0] * (n + 1…
BIT木。初見で解いているときは BIT木を知らなくて TLE を出し続け、諦めて解説読んでナニコレとなった。 BIT木の使いどころは、BIT木を2本持つことで、小さい方から i 番目の値の探索を log(N) を行える点である。値の追加、探索、削除を log(N) でできるの…
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 となって…
bit dp の問題。ゴールした順に bit を作っていくとうまく dp が作れる。 例えば 1 よりも 2 が早くゴールしているときは、今ゴール済みの人を s で表すと、 s & 1 == 0であれば、まだ１がゴールしていないので s から s | 1 n,m = map(int,input().split())…
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の計算をしてもエラー吐…
