2020/2/14

Codeforces 1301 B

最大値の最小化→二分探索をしたら実装量が大変なことに...

冷静になるとkは-1が隣り合っている数のminとmaxの平均にするのが最適

問題文読解時は意識して冷静にならないと適当な方針を生やしがち 注意

 

Codeforces 1301 C

なるべく0の連続を作りたくない

0を並べた列に1を挿入することを考える

算数をするといくつ置きに1を入れていけばいいかわかる(こういうのは式を書いて丁寧丁寧丁寧に)

式に使う文字と変数名は合わせる(a,bが紙上ではx,yみたいな対応になっていると頭が壊れるため...)

 

Codeforces 1301 D

パス構築

漸次決定的にやりたい(同じような状況を作り出して帰納的に貪欲を回す)

→上の行から埋めていくような経路を考えて実験をしていたら見つかった

 

f:id:Hyado:20200214034745p:plain

 

全ての矢印を通すパスの存在がわかっていれば考えやすいかもしれない?(うまく無向グラフとして捉えられれば、オイラーグラフであることを示すだけになる)

オイラーグラフ⇔グラフの全ての辺を一度だけ通る閉路が存在⇔全頂点の次数が偶数

オイラーグラフ⇔グラフの全ての辺を一度だけ通るパスが存在⇔次数が奇数である頂点が2つだけ

 

ICPC 2019-2020 North-Western Russia Regional H

数え上げ

t_iがすべてdistinctである場合を考える(結果をt_iの値ごとにメモしておけば、同じものが飛んできたときは定数時間で答えられる)

クエリとして1,2,3,4...10^6が与えられたとき、愚直に二分探索を繰り返して数え上げるときの最悪計算量はO((logN)*(sum/1 + sum/2 + ...sum/10^6) ) →O(sum*logN*log10^6)なので間に合う(計算量が調和級数で表される)

 

計算量評価は制約を細かく反映させようとすると複雑になってわからなくなりがちなので、ある程度割り切って最悪ケースを考えた方がやりやすそう(とりあえずクエリで全種類飛んでくることにすると考えやすい)

 

 

Codeforces 1303 E

可能不可能

分割位置を全探索することを考える

前から貪欲に採用していくのは必ずしも適切ではない→DP

dp[sをどこまで見たか][t1をどこまで作ったか][t2をどこまで作ったか]=true/false(実現可能か) (tの前半、後半をそれぞれt1,t2とする)

結局t1,t2を作りきることができるかどうかを調べたい、trueのときt2>0であるから

dp[sをどこまで見たか][t1をどこまで作ったか]=前からt2を作る時の実現可能な長さの最大値

とすれば間に合う(この最大値がt2の大きさと同じであればよい)

 

bool値のdpは定義を工夫することで次元を落とせることが多い

 

2019-2020 ACM-ICPC Brazil Subregional A

可能不可能

互いに重なる円を同じグループに、上下左右の壁と重なる円を各方向の壁と同じグループにした時、左と右、上と下、左と下、上と右が異なるグループに属するなら可能(Union-Findでがんばる)

図形の分断判定はUnionFindでできる

 

2019-2020 ACM-ICPC Brazil Subregional L

数え上げ

二項係数のうち奇数になっているものを数える

mod2でパスカルの三角形を書くとフラクタルになっているので再帰的に求められる

mod2でLucasの定理を考えると簡単にできる

 

 

前半が遅すぎる+ライブラリが貧弱であることがわかってきた