CPSCO 2019
全部解いたので略解と感想メモ
Session1
A: 算数
B: 各文字の出現回数を数える
C: binom(32, 6) の全探索
D: 8*5n-1
E: 各数は高々1回しか消されないのでsetとかで愚直に書いてもok
F: 最小値の最大化と言われたので二分探索を考える
満足度を決めると各果物を食べられる区間がわかる
区間でN日間を覆えるか？の判定を貪欲にする
G: dpの遷移を見る必要がある場所が少ないのでインラインDPをする
dpの遷移で区間minになるのでセグメント木でdpテーブルを持つとできる
H: 分割統治でl,m,rに制限をつけたやつを解くのを再帰的に繰り返す
mにずっと注目してたけどlに注目すると簡単になる
Session2
A: 算数
B: +したあとに*をする
C: +1/-1に置き換えたあと累積和取って大きい方からK個
D: ゲームなので実験すると両方奇数が条件
E: 木DPしてくださいと問題文が言っている
制約が二乗の木DPですと言っている
dp[部分木i][切った辺がj本] = 必要な操作回数 をしようとするとできるのでする
F: 各マスのコインを取る方法はロボットを横に動かすか縦に動かすかの二通り
各マスがどちらに属するか二分割する && 縦/横で取れるマスに依存性がある
グラフをつくって最小カット問題に帰着する(燃やす埋める)
G: クラスカル法の要領で考える
任意のxで使う辺を予め全部つないでおく
コストが小さい辺から見ていき非連結 → その辺をつなぐ and xの辺の本数を少なくする
xの値がw[i]のときの 定数の辺の重み と xの辺の本数 が求められる
Session3
A: 文字列処理
B: 降順ソートして上からM個取る
C: s,tを2倍してimos
D: s[0]='R' && s[n-1]=='B' && 部分文字列にRB/GGがない → Yes
E: bitごとに独立で考えられる 累積xorと0/1の数を持っておけばいい
区間xorの遅延セグ木貼ったらTLEしてつらい
F: P[i] = i は無視してあとで binom(n, a+b) を掛ければいい
あとは箱根駅伝のDP
G: 各アイドルについて賞金を増やしたときに目的関数が減少する量を考える
減少量は単調非減少なのでx_i=0から順番に見ていってもok
各アイドルについて減少量はX/Aを超えるタイミングで3通りしか取らない
3N通りの減少量を求めて大きい方から取る
Session4
A: 算数
B: 全探索
C: r[i]+D以下の人が何人いるか二分探索
D: 退屈さ決め打ち二分探索
E: ox/xoのどちらか
oxが交互の列に分割できる
先頭と末尾が同じ列ならox/xoのどちらかを優先すると取れる数が増える
取れる数が増える方を優先して貪欲に取る
F: 根を決めると残りの頂点をどのように子に分割するかが決められる
再帰的に構築
