JOI 2012-2013 予選 問題4 : 暑い日々 (Hot days)

JOI 2012-2013 予選 問題4

D: 暑い日々 (Hot days) - 第12回日本情報オリンピック 予選(オンライン) | AtCoder

id:keidaroo さんのblogに触発されてどんなもんじゃろと解いてみました。
JOIの問題は解いたことがないので…。

keidaroo.hatenablog.com

解いてみる

今何日目か前日何を着ていたかが分かれば
その中で最大化しても問題ないことが分かる
(前日より前に何を着ていたかは関係しないため)。
状態dn、遷移nのO(d n^2)DPを組む。

Submission #1356723 - 第12回日本情報オリンピック 予選(オンライン) | AtCoder

最初同じ服を連続して着てはいけないと誤読して
サンプル不一致になる。

なお、日については今と前にしか着目する必要はないので、
dpテーブルの次元は1つ減らせます(int dp[n], next[n]でいい)。

id:keidaroo さんのblogを読んで

解法が違う…。どうなっているんだ。

maxi[i] := 最高気温がiのときに着れる一番派手な服の派手さ
mini[i] := 最高気温がiのときに着れる一番派手でない服の派手さ
これで一日ごとに「最大」を取るか「最小」を取るかで遷移させていく
再帰関数のmaiが0のとき最大を取って、1のとき最小を取っている)。
O(d)。

なるほどすごい…。
でもイマイチこれで最適解が求まる理由がよく分からない…。
中間の値を持っておいたほうが得するということはないのだろうか。

f:id:arukuka:20170616183212p:plain

・・・ウーン確かにどう動かしても、
差の絶対値なので☆のところを取ったほうが良いということはなさそう。

解説

JOI 2012-2013 予選 問題4 解説
id:keidaroo さんの解き方が発展課題の方で、
私の方が愚直に解いたものになる。

解いてみて

今でこそ何とか解けるものの、
JOI予選のときに解けたものではないです
(私は高専2年のときPCK2011予選で0完、JOI2011-12予選未参加です)。

素直に、すごいなあと思うばかりです。

ポエムはできる限り避けたいですが

※はじめに言っておきますが、皆さんにとってはこの問題は楽勝だというのは知っているので、決してイキリとかそういう風に思わないでください。誰だって自分が解けなかった問題が解けるようになると嬉しいのです。(たとえどんなに簡単な問題であろうと)

暑い日々AC - keidaroo’s diary

こういう言葉を出させるコミュニティって非常に残念ですね。

同じ問題解いているお前はどうなんだという話もありますが(まあごもっとも)
競プロを始めたばかりの頃を回想したくて解いたので攻撃的な意味合いはないです。
不快に思ったら申し訳ないです。