2019/10/28

ICPC2019 Asia Jakarta Regional Contest H

一つの島に二棟建てる場合は全探索できる

二つの島に建てる場合、短辺の長さでソートして、短辺が大きい島から見ることで漸次決定できる(二変数なので片方を固定したくなる、するともう一つの変数は貪欲に決められる)

 

ICPC2019 Asia Jakarta Regional Contest E

数列構築

必要条件から構築することを考える

左→右、右→左の順で取りうる値の範囲を各項について求めたとき、下限の数列が答え

 

ABC144 F - Fork in the Road

期待値の最小値

根から木DPをすることで各頂点の期待値はO(m)で計算できる

削除する辺を全探索しても間に合わないねとなる

ある頂点から出ている辺に関して、行先の期待値が最も高い辺を削除すればよい→削除する辺の数が頂点数になるので間に合う

 

Codeforces 1096 C

幾何

円周角の定理を思い浮かべながら条件式をたてる

サンプルのコーナーに注意

 

考察の中でわかっていることを整理しながら進めていくと全体の見通しがはっきりしてよかった

 

Codeforces 1096 D

最小値

探索を考える 部分文字列として、hardを左から何文字目まで作れるかの状態を持ってDP

勝手にmodを取ってWAを出していた(は?)

 

コンテスト中でも時間を取って実装を簡単にするべき