久しぶりに熱測って37.2。上がりすぎ。上がったぶん空回りしただけ。またlowestを更新した。まだまだ下がる余地があるんだなあ。
A - Painting
min((n + h - 1) / h, (n + w - 1) / w)。もう少し短く書けないかなあと思いながら出した。（解説放送を聞いて）Fのパロディかあ。
B - Robot Arms
めちゃくちゃ難しい。区間を右端が左にある順に見ていく、というのはよくあるので思いついたが、それをどう利用するれば100%正しいと言える解法になるのか考えるのに時間がかかった。えーと、一番左の右端が占める場所で1個しか生き残れないのだけど、一番左のを選んでデメリットがない。その場所の左側を考えると既に被ってるやつしかいない（デメリットがない）し、右側は明らか（メリットしかない）。ということで左から貪欲に取っていく。生き残ったやつの右端の場所を更新していって、左端がそこにかかるやつを落としていく。右端でソートしてあるので、現在見ている場所より左端が左な区間は必ず被る。この解法で全部上手くいくんだけど、全部確認する必要があって難しい。
C - Subarray Sum
楽しい構築。制約を見て、KがN以下なので、N=5,K=4,S=9みたいなケースで9,9,9,8,1を思いつく。S=1だとこれができないので、1,1,1,1,4とかする。どうも、Sが大きいときも小さいときも簡単なので、その2つの解法を組み合わせれば解けそうだと思った。もう少し考えて、S,S,S,S+1,S+1とかでいいと気づく（代わりにS-1を使うとそれらの和がSになるかもしれない、S+1なら心配ない）。これができないのはS=10^9のときだけなので、場合分けしてS,S,S,1,1にする。10^9はNより十分に大きい。
終了後にジャッジをどう書くか考えていて気づいたが、ジャッジはしゃくとりで書けて、正の数しか出てこないので1つの開始地点に対し和がSになる区間は高々1つしかなく、だからK>Nのときは構成できない。なぜK<=Nなのかコンテスト中はわかってなかった。
D - Swap and Flip
解けなかった。カードiが裏になるかどうかで2^N通り探索し転倒数を数えるというところまでは行ったが、同じ数がたくさんあるときの処理がわからなかった。
最初、広義単調増加となったときの一番左と一番右のカードの数を固定することを考えた。少しして、数ではなくどのカードが来るかで考えたほうがいいと気づく。これだと何もわからなくて、しばらくして、1回の操作でカードは距離1だけ動き裏表が入れ替わる、つまりあるカードについて最終的な位置から裏表がわかると気づいた。なんか普通にDFSしてもしっかり枝刈りすれば通るのではとか思い始める。しかし計算量が全くわからないので困っていると、裏表の2通りを全探索する（2^N回）ことを思いつく。裏表は1回の操作で2回変わるので裏なカードの枚数は偶数。全カードの裏表を決めれば使う数がわかり最終的な数列がわかる！と思っていたが、なんか最終的なカード位置での裏表を考えていて、そもそも裏表を固定しなくてもその位置に来る数は高々N通りで、固定することで半分になる。で、その選ばれうるシーケンスをソートして組み合わせればいいかと思いきや、全部でN*2個ある数の中からN個しか使わないわけで、全部使わないのでは最終的な数列もわからない。難しすぎてめちゃくちゃ時間食った。残り30分くらいになってやっと、単にカードiの最終的な裏表全探索じゃんと気づく。これで、使える数が決まった。だから最終的な広義単調増加な列も一意に定まる。あとは、これが実現可能か。最初はソート前とソート後の数列を持っていたが、単にカードぐしバブルソートすればいいと気づく（Nが小さいのでNlogNもN^2も変わらん）。swapされた回数を各カードに保存しながらバブルソート。ソートが終わって裏表が合ってればそれ（全体のswap回数）が答え。合ってなくて全部違う数のときは-1。そうでないとき、同じ数の区間で追加で最小のswapをして合わせる必要があるが、ここが難しくて残り時間もわずかしかなく、書ききれなかった。ただ、ここはかなり難しく、時間があってもダメだったかもしれない。swap回数の偶奇が合わないもののうち一番左のものに注目する。これはswapする必要があるけど、だからといって他をswapする前にやってもいいのかがわからない。そもそも、もう少し考えると、カードをswapすることで一番左の合わないカードを左のカードとswapすることもありえる。偶奇は位置じゃなくてカードにかかるから、カードをswapすればまた話が変わる。一番左のものより左まで巻き込む可能性があるんじゃどうしようもない。
