kwm_t

kwm_tのメモ

ARC169

■A - Please Sign
寄与を考える。
グラフとしてみると、rootからの深さと二項係数が関係ある。
係数になる二項係数は単調なので深さを深い方から見て符号を見る
■B - Subsegments with Small Sums
iから見たときどこまでが塊になるかを考慮して後ろからdp
■C - Not So Consecutive
dp[i][j]:=iまでを埋めた最後はj
ただし重複を許さないために、i+1番目はjでは埋められないとする
これは区間更新一点取得で出来るので双対セグ木でと言いたいが
TLEしてしまうので真面目にlogを落とす

Starters 111 Division 1 (Rated till 6 Stars)

■Beautiful Strings
Π各文字の出現回数+1
■Prefixing
Setで適当に管理した上で貪欲
■LCM Mania
nが2冪だと不可能
(2^n,2^n,2^n*p)のような形
■Prime Range Game
只のnim
■ODI Cricket
後から貪欲
■Component Count
i*jに全てが収まってk個が塗られているかつ
連結かつ、上下左右の行、列は最低でも一個は塗られていると前計算する
■Square Count
わからん

Educational Codeforces Round 159 (Rated for Div. 2)

■A. Binary Imbalance
"111111"ならダメ
■B. Getting Points
最終日から出席をする二分探索
■C. Insert and Equalize
差のgcdを取って適当に
■D. Robot Queries
lower_boundを左右から適当に
■E. Collapsing Strings
Trie木
■F. Trees and XOR Queries Again
HLD*SparseTable

ABC331

■A - Tomorrow
やる
■B - Buy One Carton of Milk
dp
■C - Sum of Numbers Greater Than Me
mapで管理
■D - Tile Pattern
面倒枠
2D累積和＊繰り返しを省略
■E - Set Meal
二分探索
■F - Palindrome Query
セグ木に載せてハッシュにして比較
■G - Collect Them All
解けるわけ無いだろと思ったが
解説読むと確かに、そのとおりですねぇとなって感動

PAST16

PAST16
■A - ツバメ
if
■B - スロット
setにいれる
■C - コンテスト
配列
■D - 相対評価のスコア
long longで適当に
■E - 10 の n 乗
1000000かどうか
■F - 式の評価
やるだけ
文字列の最後に'*'を追加すると楽
■G - N個の三角形
next_permutationで列挙し
n!で割る
■H - 休暇
dp[i][j][k]:=i日まで見た、j回宿題、直前の状態
■I - アメ
難しくないですか？
二分探索してまずシュミレートして端数をあとでやる
■J - 除夜の鐘
差のGCDの約数を全部試す
■K - マス目
ダイクストラをn回する
計算量をちゃんと解析すると間に合うことがわかる
実装はdpテーブルを使い回すと楽
■L - 平均クエリ
隣接する項目だけ見ればいのでsetで管理
■M - 線分の交差判定
ライブラリにしましょう
■N - ソートと関数
セグ木に乗る
■O - 数列の足し算
dpしながらdpテーブルをimos法っぽく更新する感じ。