ABC267E 最大値の最小化は, binary search が典型． しかし，解法から攻めるのは王道とは言えない． まずは性質を考える． 単調性 \(\cdots (*)\)取り除く作業を繰り返してく． ある時点でコスト \(y\) 以下の vertex は，それ以降もずっと コストが \(y\) …

インタラクティブな問題． 解法Binary search と同じで，区間を半分ずつにしていく． 行を 2つの区間に分けたとき，区間の行の個数より駒が少ない区間が存在する． そちらの区間に正解の行がある． 列も同様． 実装入力と出力を一緒に行う関数を用意すると楽…

ABC270E 解法は2つある． いずれにせよ，まずは 1周を一塊で考える． 解法0: Binary search\(K\) を固定する．(\(m\) 周できるか) \(\in Bool\) は単調．\(m\) 周すると，各 \(i \in N\) に対して \(min(a_{i},m)\) 個食べるので， その合計が \(K\) 以下か…

ABC271E 通る道の長さの最小を求める．最小の長さの合計ではない． 良いpath良いpath とはどういうものかを考えると， \(E\) を先頭から見ていくことで判定できる． そこで \(E\) を基準に考える．また，良いpath 自体は多くなりうるので，Dijikstra などで …