教えて!gooで見かけた問題。
出題の元ネタはAtCoderのモノ、らしい。
ぶっちゃけ、初見じゃ問題の言ってる意味がサッパリ分からんかった(笑)。
多分、問題文の作成者はプログラマだろう。さすが国語力が低い(笑)。
さて、このテの問題を見ると、直接は関係無いがナップサック問題を思い出す。何らかの取りうる個数に対して最大値を求める問題、だよな。
個人的にはあまりアルゴリズムの世界に入りたくはない人なんだけど、ナップサック問題は教養として知ってて良いアルゴリズムだと思う(※1)。ソーティングは今時、プログラミング言語が提供している機能なんで「学ぶ」必要性は著しく低下してるが、一方、ナップサック問題の「解き方」なんかは覚えておけば色んな局面で応用が効くんじゃないか。
さて、この問題で把握しておかなければならないのは、誰が「どこまで」攻撃出来るのか、だ。
問題の要請としては、例えば勇者B0は0番目と1番目の街のモンスターを攻撃出来ても2番目の街のモンスターは攻撃出来ない、と言う事だ。仮に1番目の街のモンスターを勇者B0が殲滅して余力があったとしても2番目の街のモンスターに手出しは出来ない。それを上の図の矢印が示している。
逆に、勇者B0は弱いヤツ、あるいは0番目の街のモンスター数はB0の攻撃力を上回った数がいるとして、勇者B0が力尽きた、としよう。しかし、勇者B1は０番目の街のモンスターの殲滅に力は貸せない。あくまで勇者B1は１番目の街と２番目の街の２つでしか戦えない、んだ。
これがこの問題の縛り、となる。
後者の例としてあからさまなのが、AtCoderの問題のページに掲げられてる入力例3だ。
こういう状態だよな。
勇者0は非力で攻撃力が1しかない。1攻撃力1殺なんで、０番目の街には100体のモンスターがいるけど、結果１匹しか殺せずそこで力尽きるわけだ。０番目の街に残ったモンスターは99匹もいるが、勇者1はそこには手を出せない。
勇者1は100の攻撃力を持つ優秀な男だけど、1番目の街にはモンスターが1匹、2番めの街にもモンスターは1匹しかいない。結果、勇者1が討伐出来るモンスターの総数はたった2匹だ。余力が98もあってもこれで打ち止め、だ。
結果、無情にも、モンスターの総数は99匹残っていても、最大可能討伐数はたった3匹、って事になる。
これがルールによる結果だ。お分かり頂けただろうか。
さて、プログラミングの大枠を考えると、モンスターのリストAがあり、勇者のリストBがある、と。そして勇者のリストBの先頭要素から順次値を取り出していっては、それを使ってリストAを先頭から順次加工していく、と言う枠組みが見えるだろう。
もうこうなれば分かるよな。例によってfold/reduceの出番、だ。
(foldl なんらかの処理 A B)
っぽくなりそうなのは分かる。
ただし、もうひと工夫必要だ。しかしながらもういい加減慣れただろ、ってテクニックを使う。
確かにプログラム上、リストBから引っこ抜いてきた要素を使ってリストAを加工していく、って方針は正しい。ただし、同時に、本当に欲しいデータは討伐数なんだ。
つまり、リストAだけ、ではなくって、0から始まる累積値(アキュムレータ)も加工対象として欲しい。
こういう「加工対象が2つ欲しい」なんつー場合は、単に、それら2つを合わせたコンパウンド・データ(合成データ)をfoldlの第2引数にしちまえばいい、ってだけだ。
つまり、`(,A 0)を初期値として与えちまえば解決する、って事だな。
(foldl なんらかの処理 `(,A 0) B)
僕らにはパターンマッチがあるんで、「なんらかの処理」内で、コンパウンドデータは自在に分解可能だ。分解して処理してはまた合成して返す。それだけでラクチンにプログラムを書く事が出来る。
ではその「なんらかの処理」を書いていこう。
疑似コード的には次のようになる。
- 引数はyとxの2つとする。xはfoldlの第2引数、yは第3引数とする。 => 引数順序が逆になってるように見える為。
- xはリストAと討伐数のコンパウンドデータなんで、これをlstとaccと言う2つのデータに分解する。
- (- y (car lst))を計算してval0と言う変数に束縛する。 => yは勇者の攻撃力、(car lst)は街に存在するモンスターの数だ。この減算で負の数を得たらその街のモンスターは殲滅出来なく、勇者は力尽きた、と言う事になる。逆に0以上だったらまだ余力があり、次の街へ向かう事が出来る、と言う事だ。
- val0が負の数なら`(,(cdr lst) ,(+ y acc))と言うコンパウンドデータを返す。 => 繰り返すがval0が負の数なら勇者はそこで力尽きたと言う事で、モンスターがまだいようが次の勇者はどうにも出来ない。そこで今戦ったモンスターの残党をlstから削除し、アキュムレータ(acc)にyを加算する。勇者の持ってた攻撃力(y)がそのままモンスターの討伐数を表すから、だ。
- val0が0以上だったら勇者はまだ余力があるんで、(- val0 (cadr lst))を計算し、val1に束縛する。 => val0が勇者の戦闘力の余力なんで、次の街のモンスター((cadr lst))との差を取る。これが負の場合、勇者はその街で力尽きた、と言う事だ。逆に0以上だったら余力まだアリ、って事だが、戦闘自体はそこで終了、となる。
- val1が負の数だった場合は、勇者はそこで力尽きる。全力を出した、と言う事で、返り値は`(,(cons (- val1) (cddr lst)) ,(+ y acc))となる。 => val1の絶対値は逆に言うと「残ったモンスターの数」でもある。よって、lstの先頭の要素2つを削除して、val1を正の数に反転させたブツをconsしておけば、最初の街は次の勇者の討伐対象になる、って事が表現可能だ。また、この時点でy(勇者の攻撃力)は討伐モンスター数と同値だ、って事なんで、アキュムレータ(acc)に加算しておく。
- val1が0以上の場合、その勇者は2つの街にいたモンスターを全滅させた、と言う事だ。返り値は`(,(cons 0 (cddr lst)) ,(+ (car lst) (cadr lst) acc))となる。 => (cddr lst)に0をconsするのを忘れないようにしよう。あくまでこの時点での「街」は次の勇者が最初に討伐するモンスターがいる街、なんで0だろうと先頭にデータは残しておかないとならない。また、(car lst)と(cadr lst)はそれぞれ街にいたモンスター数だが、「全滅した」以上これらはまるっと「掃討数」って事になる。アキュムレータに加算しておこう。また、この時点で、いくら勇者に余力があろうとここで退場だ。次の勇者の出番だ。
と言うカンジで、モンスター対象のリストAの、最大で先頭要素２つ、を対象に計算していって、リストAの状態を遷移させるのが、この「なんらかの処理」の役割だ。
理解した?
Racketでこのまんま実装すると次のようになるだろう。
(define (foo y x)
(match-let ((`(,lst ,acc) x))
(let ((val0 (- y (car lst))))
(if (negative? val0)
`(,(cdr lst) ,(+ y acc))
(let ((val1 (- val0 (cadr lst))))
(if (negative? val1)
`(,(cons (- val1) (cddr lst)) ,(+ y acc))
`(,(cons 0 (cddr lst)) ,(+ (car lst) (cadr lst) acc))))))))
あとはmain関数を書くだけ、だ。
(module+ main
(let ((N (string->number (read-line))))
(let ((A (map string->number (string-split (read-line) " "))))
(let ((B (map string->number (string-split (read-line) " "))))
(when (and (<= 1 N (expt 10 5))
(= (length A) (add1 N)) (every (lambda (x)
(<= 1 x (expt 10 9)))
A)
(= (length B) N) (every (lambda (x)
(<= 1 x (expt 10 9)))
B))
(printf "~a~%" (last (foldl foo `(,A 0) B))))))))
原作はC/C++/Javaを想定してるため、範囲チェックが煩い事になってるが(Lispはハードウェアが許す限り、どんなデカい数でも扱う事が出来る)、本当だったら勇者の数を指し示すNが決まれば街の数がN + 1になってるかどうか、また、勇者リストの長さがNに一致するだけか、調べれば充分だろう。
また、入力はread-lineに頼ってて、それが返す文字列を加工している。string-splitは区切り文字で文字列を分割する。ここでは、スペースを区切り文字にしている。
まぁ、こんなカンジだろう。全体的なソースコードはこのようになる。
またPythonで書くとこのようになるだろう。ロジックは全く同じだ。
とまぁ簡単だが、今回は以上、だ。
fold/reduceの練習問題としては丁度エエやろ、ってぇんで取り上げた次第だ。
※1: 個人的には、もう一つ面白いな、って思うアルゴリズムが遺伝的アルゴリズムだ。
