結果
100+6+12=118pt
日程内7位(unique)
A:AとBの個数が等しい単調増加列をひとつ構成、難易度9
B:4つの点を長方形の中にいれる、難易度12
C:点がワイパーで移動する、難易度12
経過
□9:00(0+0+0=0pt)
コンテスト開始
Aを眺める
誤読防止のためA-1のDPの11点を実装する
方針を固めずに実装したら途中で手が止まったのでやめる
A-2を考えるが、何もわからない
□9:17(0+0+0=0pt)
Bを眺める
配点がふざけているので、簡単枠を疑う
B-満点を考えるが、わからない
B-1のK=1のケースの2点を提出する
□9:37(0+2+0=2pt)
Cを眺める
C-2のSegtreeの10点まで考える
C-1の1点を提出する
□9:50(0+2+1=3pt)
C-2のSegtreeを実装する
途中で実装に疲れたのでやめる
□10:01(0+2+1=3pt)
A-満点を考える
問題をより簡単な問題に言い換えることに成功
□10:34(0+2+1=3pt)
Bを考える
簡単枠だと信じているので、{左端の最大値,右端の最小値}×{下端の最大値,上端の最小値}の4点を出力するがWA
K=2のとき(左端の最大値,下端の最大値)と(右端の最小値,上端の最小値)の二つを出力するコードを提出するとACとWAが交互に出る
なので、もう一種類のペアの組み方も試すとK=2のケースに正解する
□11:00(0+6+1=7pt)
A-満点を考える
前の考察を見直すと、言い換えた後のより簡単な問題が解ける
実装が重いので丁寧にレジュメを作ってからコードを書く
想定解・多くの人の解とはまったく異なる方針で解いており、実際は難易度9だが、難易度11相当が解けたと思って喜んでいる
□12:58(100+6+1=107pt)
C-3のSegtreeの11点を実装する
□1:21(100+6+12=118pt)
C-4の53点を考える
慣れていないデータ構造を使って領域処理をしなければいけないことがわかるので、やめる
□1:40(100+6+12=118pt)
C-2のSegtreeの10点を実装し提出するが、WA
□1:58(100+6+12=118pt)
□2:00(100+6+12=118pt)
考察
天才っぽい見た目の問題でも部分点を固めることが満点につながる
A問題 Building4の解法
(1)左右から最善の単調増加列を伸ばして、それに乗らないものにバツをつける。両方にバツがついた箇所があったら解なし。
(2)片方にバツがついたところを挟んで左右は独立なので分ける。
(3)両方マルの箇所が隣り合っているとき、a[i],b[i]の大きい方からa[i+1],b[i+1]の小さい方に行けないことがある。そうでないとき、iまでとi+1は独立なので分ける。(1)の操作の性質より、a[i],b[i]の小さい方からa[i+1],b[i+1]の小さい方にいけなかったり、a[i],b[i]の大きい方からa[i+1],b[i+1]の大きい方にいけなかったりということはない。
(4)iの大きい方からi+1の小さい方に行けないということは左下の図のように表せ、左からいくつかは小さい方を選んで、それより右は大きい方を選ぶ必要がある。また、そのような選び方がいつもできる。
(5)一旦全て大きい方を選ぶことにして、左のいくつかを小さい方に変えることを考えると、左下の図のように累積和の最小値から累積和の最大値までAの個数を変化させることができる。
(6)すべての区間で累積和の最小値を取ったり累積和の最大値を取ったりしてもAの個数がNにならないなら解なし。そうでなければ、それぞれの区間で累積和の値を指定して、累積和が指定した値になるように反転すると具体的な解が得られる。
計算量はO(N)、実装は面倒(index、反転or反転しないなど)