ACPCVC20200615 復習メモ - tinumu's reminder

https://kenkoooo.com/atcoder/#/contest/show/de1c2a21-407e-41a6-bc64-deb6570852f3

3問目のJOI感に少しの興奮を覚えた

A - パズル

$HW-1$ パズルになっていて、ステップ数も $24$ ステップ以内とあまり大きくない。
onlinejudge.u-aizu.ac.jp
この問題を解いていると、これは IDA*で通るなという確信が付いているので数字が規定の位置から離れているマンハッタン距離をヒューリスティック値にしてやると、通る。
潜るにしろ、的はずれなところに $12$ 回くらいいく事とかなさそうなので (ヒューリスティック値が増える方向に進むとステップと合わせて $+3$ とか上がったりする)、かなり小さくなるんじゃないかなっていう感じにはなっている。ちゃんと計算量解析したいけど難しそう…

B - 擬二等辺三角形

細かい計算が必要でかなり精神を使う
$2$ 辺を $a, a+1$ みたいに書くとすると、もう $1$ 辺を使って三角形になるのは、 $\lbrack 2, 2a \rbrack$ である。あと、途中で $L-2a-1$ の長さまでしか使えなくなってくる。
しかも、 $a, a+1, a+2$ みたいになっていると、重複して計算してしまうところが出てきたり、そもそも、最後の辺の長さについては $a, a+1$ は使えないとか色々とめんどくさい制約がある。
とりあえず、 $\lbrack 2, \min(2a, L-2a-1) \rbrack$ の中に $a, a+1$ がある場合を考えると、 $a+1\leq L-2a-1$ みたいな制約が出てくるので、解くと、 $a \leq \frac{L-2}{3}$ まではそうらしいことがわかる。
そこで分けて、あとは数列が定められるのでこれらを $\mathrm{O}(1)$ で求めて終わり
数列を頑張る処理は場合分けとか重複部分の排除とか嫌な気持ちになることが多々あるので精神力を使って頑張って殴って解く。
一般化の式とか書くと多分頭がイカれてきそう()

C - 映画の連続視聴

$1$ 次元のDPとかがかなり浮かびやすい。 $H$ の累積和を取っておいて、連続した試聴に対して直接エッジを張ることを考えると、状態 $\mathrm{O}(N)$ , 遷移 $\mathrm{O}(N)$ の $\mathrm{O}(N^2)$ のDPが出来そうで、 $N \leq 3000$ よりかなり現実的
これはもちろん主要な時間だけ取り出す事で実現できているので座標圧縮が必要になる。
ところで、エッジの貼り方はどうすればいいだろうかということになる。
ある特定の時間からある特定の時間まででできるだけ同じ種類の多くの映画を見れば、できるだけ大きい得点になるので、そのような最適なスケジューリングをしてエッジを張って行くことが必要になる。
そこで、まず種類別にする。そして区間の終点でソートする。ソートした後、貪欲に映画を見ていくのが最適になる(これは蟻本とかに書いてある)。このような見方をするたびに、所定の位置にエッジを張っていくと、グラフが完成するので、それをDPで最大化すると、この問題は解ける。
こういうたくさん組み合わさっている系の問題ってJOIみがないかな(わからない)

感想

何回も思っているが、考察はできるだけ詰めておこう出来そうになかったらサンプルをたくさんためそう