概要
AtCoder キーエンスプログラミングコンテスト2020に参加して、 問題BをDPで解こうとしたがTLEなどが出て撃沈、問題A/Cしか解けずに点数がいまいちだった。
問題Bについて正解者の提出を見ていると「貪欲法」で簡単に解けることが判明。自分でも書いてみたら一瞬で終わって愕然（提出#9585045）。
「プログラミングコンテストチャレンジブック（第２版）」(以下「蟻本」)）でも「貪欲法」はみていて、「そういうのがあるのね。でも解の厳密性が納得いかんなぁ。どういうときならOKかよくわからん」と放置していた。しかし今回のようなケースで点数をおとしていてはいかんので自分なりに今回のケースで貪欲法で解の厳密性が保証されているのか、考えてみた。
結論としては今回のケースでは貪欲ほうで解いても解の厳密性は保証されることに納得ができた。
経緯
貪欲法で解く場合 X_i + L_i ロボットをソートして、その順番で
- すでに使うと決めたロボットと、腕が動く範囲が共通部分を持たなければ使うと決定する。
- すでに使うと決めたロボットと、腕が動く範囲が共通部分を持てば使わないと決定する。
を判別するだけである。超簡単。
ただこれだと。「ロボットiを使わない方がよい場合が最適化になる場合があるかもしれない、なんでこの方法で最適解がもとまると保証できるのか？」ということが直感的に咀嚼できなかった。
「蟻本」 P.45にも以下のような記載がある。
本のこの部分を読んだ時は、「うーんどういう時に貪欲法を安心して使えるか、よくわからんな。まぁいいかぁ」と思いスルーしていた。しかし、今回の問題は「蟻本」のP.43にある区間スケジューリング問題と実質的には全く同じ。ここでちゃんと理解していれば簡単に解けていた問題と思われる。
考察
なのでこの場合貪欲法で最適解が必ず求まるか考えてみた。結論としては最適解が必ず求まることは確認はできた。しかし考えるの結構面倒臭い。
添字が多くQiitaの書式では書ききれないのでOverleafで作成してPDFにしてみた。
次回同じパターンなら安心して使えるが、違うパターンで貪欲法で出来そうな時に
解法として正しいか、正しくないのか確信をもって短時間に判断できるか不安がのこる。まだまだ修業が必要。