JOI open2019

32+100+0=132pt 19位

一問目を解きたかったが行き詰まった。一順序に複雑なものが乗っかっているタイプの問題をよく理解していないので、それを勉強する。

くだらない部分点はやる気が皆無なので取らなかった。

本番のフロー

すべての問題を読む。

参加表明のために一問目の5点を取る。

他の小課題１は実装が重いので逃げる。

1:00くらい-5pt(+5)

一問目が楽しそうなので、考える。

O(N^2)解がいくつか分かるが、満点に繋がらないので実装しなかった。

小課題３(Q=1,L=1,R=N)が満点に繋がりそうなので考える。

ずっと観察をしていると、大きい方からlogN+α個のものがすべて選ばれないことがないことがわかるので、実装する。

3:02-32pt(+27)

満点解法を考えるが、適当な当てずっぽうしかできないので解けない。

4:12-32pt(+0)

一問目を諦めて二問目を考える。

これはJOIではない。

気合いを出すと解ける。

4:55-132pt(+100)

一問目のO(N^2)を書こうとするが間に合わない。

5:00-132pt(+0)

反省

一順序に複雑なものが乗っかっているタイプの問題に対する知見を深める（分割統治とバケット、区間を端でソートして走査するやつなど）。結果を求めなければいけないときはくだらない実装だけ重い部分点も取る意志をもつ。