https://csacademy.com/contest/ioi-2016-training-round-2/summary/
$N$要素の整数列が与えられ、この数列の要素を1つ選んで1増やす操作を考える。この数列のすべての連続な部分列のなかで、$M$回以下の操作(0回を含む)で広義単調増加にできるものの数を出力せよ。
区間$[l, r]$で表せる部分列が$M$回以下の操作で広義単調増加にできるとき、$[l, r-1]$も必ず可能である。このことから部分列の始点$l$を固定したとき、各終点$r$に対して$M$回以下の操作で部分列$[l, r]$を広義単調増加にできるかどうかということには単調性がある。以下、各始点$l$について、$r$番目以前の要素を終点にでき、$r+1$番目以降の要素を終点にできないような$r$を探すことを考える。
はじめに$l=N-1$(末尾)を考える。このとき、明らかに$r=N-1$であり、ここから$l$をデクリメントしていく過程はdequeを使ってシミュレートできる。広義単調増加な区間$[l, r]$に操作を行って$[l-1, r]$を広義単調増加にするためには、$[l, r]$に含まれる$A_{l-1}$未満の要素をすべて$A_{l-1}$に書き換えればよい。ここで、区間$[l, r]$に含まれる(操作後の)整数のなかで、各整数のうち最初に現れるものの(index, value)をdequeに保持する。たとえば単調増加な(操作後の)数列$[l, r]$が $$1, 1, 1, 2, 2, 4, 5, 5, 6$$ であればdequeの中身は $$\{ (0, 1), (3, 2), (5, 4), (6, 5), (8, 6) \}$$ のようになる。この数列の左端に$A_{l-1}$を加えるとき、dequeの左側からvalueが$A_{l-1}$以下の要素をすべて取り出したあと、左側から$(l-1,\ A_{l-1})$を入れればよい。
$next[i]=i+1$番目以降で$A_{i}$より大きい要素が最初に現れるindex
を前計算しておけば、$[l-1, r]$での操作の合計回数を高速に計算できる。
$l$のデクリメントによって区間内の操作回数が$M$を超えたとき、操作回数が$M$以下になるまで$r$をデクリメントする。このとき、操作回数はdequeの右端のvalue$-A_r$だけ減少する。$r$がdequeの右端のindexを下回るとき、dequeの右側から要素を1つ取り出す。
以上の方法で、すべての始点に対して可能な終点の最大値をしゃくとり法で求めることができる。
解説AC。各始点について終点を二分探索することを考えたり、しゃくとりも考えたりしたがどちらも実装できず。
cographとは、以下のような性質のうち1つ以上を満たす無向グラフのことである。
各頂点に重みがあるcographが与えられるので、重みが最大となるクリークを構築し、重みとクリークに含まれるノードを出力せよ。
任意のcograph $G$について、$G$およびその補グラフ$\bar{G}$のうち少なくとも1つは非連結である。この性質を用いて、与えられたcographの各連結成分について(辺を反転させる→さらに連結成分に分解する)を繰り返せば、最終的には頂点ひとつずつに分解できる。
与えられたグラフ$G$の最大クリークは、$G$の各連結成分の最大クリークの最大値である。ここで、$G$の各連結成分の最大クリークを求めることを考える。
$G$の連結成分のうちのひとつを$C$とする。グラフの最大クリークはその補グラフの最大独立点集合と同値なので、$C$の最大クリークは$\bar{C}$の最大独立点集合に等しい。前述の理由から$\bar{C}$は(頂点数が1でないかぎり)必ず2つ以上の連結成分に分けることができて、$\bar{C}$の各連結成分の最大独立点集合の和が$\bar{C}$の最大独立点集合となる。
以上のようにして、与えられたグラフから辺を反転させながら再帰的に最大クリークと最大独立点集合を求めていくことで、この問題が解ける。
解説AC。惜しい。
$N$頂点からなる多角形(凸多角形とは限らない)と$M$個の点が与えられる。$M$個の頂点のうち、多角形の内側もしくは辺上にあるものの数を出力せよ。
平面上で閉曲線と点が与えられたとき、点が閉曲線の内部にあるかを判定するためには、点を始点として任意の方向に半直線を伸ばし、その半直線が閉曲線と奇数回交差しているかどうかを調べればよい。今回の問題では、各点から下向きに半直線を伸ばしたときにいくつの辺と交差するかを調べればよい。
多角形を構成する頂点の位置する$x$座標で平面を縦縞状に分割すると、$y$軸に垂直な辺を除いたすべての辺は、ある領域に対して完全に横切っているか全く干渉しないかのどちらかになる。
すべての領域について、その領域を横切る辺のリストを作り、高さでソートしておく。辺は交差することがないので、領域の左右の境界を横切る高さ$(l_y, r_y)$でソートすればよい。このとき、ある点から下向きに伸ばした半直線が横切る辺の数を数えるためには、点がどの領域に所属しているかを二分探索で探し、その領域を横切る辺のうち点より下にあるものがいくつかを二分探索すればよい。
クエリ点の座標を受け取った時点で垂直な辺や多角形を構成する頂点と重なっている点をカウントして除いておけばその後の判定がスムーズになる。垂直な辺との重なりは各$x$座標に存在する垂直辺を区間として管理して二分探索すればよく、垂直でない辺との重なり判定は簡単な幾何の問題である(二分探索と同時にできる)。
解説AC。幾何っぽい問題は大体手が出ない。editorialでは点の上にある辺を数えているが、下を数えるほうがやりやすいと思う（ソート的な意味で）。